[dictionary] 지도와 사전의 차이점은 무엇입니까?

프로그래머가 복잡하다이 질문에 대답하는 것은 그들이 사용했던 특정 언어 나 시스템의보다 구체적인 의미를 주어진 조건을 볼 수 있지만, 문제는 내 말을 데려 갈거야 “이론”언어 무신론자 비교를 요구 한 컴퓨팅 과학의 관점에서 .

용어 설명

컴퓨터 과학 의 옥스포드 대학 사전 목록 :

요소의 삽입 및 삭제를 지원하고 멤버쉽을 테스트 할 수있는 요소 세트를 나타내는 모든 데이터 구조 사전

• 예를 들어 삽입 할 수 있고 삭제를 시작할 수있는 {A, B, C, D …} 요소 세트가 있으며 “C가 있습니까?” 를 쿼리 할 수 ​​있습니다. .

맵 의 컴퓨팅 과학 개념은 옥스포드 사전이 다음과 같이 정의 하는 수학 언어 용어 매핑을 기반으로합니다 .

맵핑 주어진 세트 (도메인)의 각 요소를 두 번째 세트 (범위)의 하나 이상의 요소와 연관시키는 조작.

• 이와 같이, 맵 데이터 구조는 맵 에서 ” 키 “로 알려진 주어진 세트의 요소에서 관련 ” 값 (들) “으로 알려진 두 번째 세트에서 하나 이상의 요소 로 이동하는 방법을 제공합니다 .
• “제 세트 … 이상의 요소가” 형태는 구현에 의해 지원 될 수있는 것은 두 가지 방법이다 :
  • 많은 맵 구현은 키의 고유성을 강화하고 각 키를 하나의 값과 연관시킬 수 있지만이 값은 더 간단한 데이터 유형의 많은 값을 포함하는 데이터 구조 자체 일 수 있습니다 (예 : {{1, { “one” , “ichi”}, {2, { “two”, “ni”}}}은 문자열 쌍으로 구성된 값을 보여줍니다.
  • 다른 맵 구현에서는 각 키가 동일하거나 다른 값으로 매핑되는 중복 키를 허용합니다. 이는 기능적으로 “associates … each [key] 요소 … with … more [하나 이상의] [value] 요소”의 경우를 만족시킵니다. 예를 들어 {{1, “one”}, {1, “ichi”}, {2, “two”}, {2, “ni”}}입니다.

사전과지도 대조

따라서 위의 엄격한 Comp Sci 용어를 사용하여 인터페이스가 모든 사전에 필요하지 않은 추가 작업을 지원하는 경우 사전은 맵일뿐입니다 .

• 고유 한 키 및 값 구성 요소로 요소를 저장하는 기능

• 키만 주어진 값 을 검색 하는 기능

사소한 비틀기 :

• 맵 인터페이스는 {key, value} 쌍이 컨테이너에 있는지 여부에 대한 테스트를 직접 지원하지 않을 수 있으며, 이는 요소가 {key, value} 쌍인 ​​사전의 요구 사항입니다. 맵에는 키를 테스트하는 기능이 없을 수도 있지만 최악의 경우 키별로 값 검색 시도가 성공 또는 실패했는지 확인할 수 있으며 관심이있는 경우 키가 예상 값을 검색했는지 확인할 수 있습니다.

청중에게 분명하게 의사 소통

⚠ 위의 모든 내용에도 불구하고 위에서 설명한 엄격한 컴퓨팅 과학의 의미로 사전 을 사용하는 경우 잠재 고객이 처음에 나를 따르거나 용어를 공유하고 방어 할 때 감동을받지 않을 것으로 기대하십시오. 이 질문에 대한 다른 답변 (및 그들의 투표)은 “사전”이 대부분의 프로그래머의 경험에서 “지도”와 동의어가 될 가능성을 보여줍니다 . 보다 광범위하고 명확하게 이해 될 수있는 용어를 선택하십시오. 예 :

• 연관 컨테이너 : 키로 값을 검색하고 지우는 키 / 값 쌍을 저장하는 컨테이너
• 해시 맵 : 연관 컨테이너의 해시 테이블 구현
• 고유 키를 적용하는 해시 세트 : 요소 / 값을 별개의 키 / 값 구성 요소를 포함하는 것으로 취급하지 않고 요소 / 값을 저장하는 사전의 해시 테이블 구현. 요소의 복제본을 삽입 할 수 없음
• 중복 키를 지원하는 균형 이진 트리 맵 : …

특정 구현과의 상호 참조 Comp Sci 용어

C ++ 표준 라이브러리

• 지도 : map, multimap, unordered_map,unordered_multimap
• 다른 사전 : set, multiset, unordered_set,unordered_multiset
• 참고 : 반복자를 사용하거나 std::find요소를 지우고 멤버 자격을 테스트 할 수 있습니다array , vector, list, deque요소를 찾는 것은 O (N)에서 화려 비효율적이기 때문에 등,하지만 컨테이너 인터페이스는 직접 어떤 경우에는 삽입 / 삭제에서입니다, 그것을 지원하지 않습니다 비효율적이며 이러한 작업을 지원하는 것은 컨테이너가 암시하는 의도적으로 제한된 API를 약화시킵니다. 예를 들어 deques는 일부 키의 관점이 아니라 앞 / 뒤의 지우기 / 팝만 지원해야합니다. 검색을 조정하기 위해 코드에서 더 많은 작업을 수행해야하므로 프로그래머는보다 효율적인 검색을 통해 컨테이너 데이터 구조로 전환 할 수 있습니다.

… 나중에 다른 언어를 추가하거나 편집 할 수 있습니다 …

답변

(a (n (d t)) n d )