이번 포스팅에서는 map의 ADT에 대해 살펴보겠습니다.
ADT : Abstract Data Type
자세한 설명을 위해 위키피디아 링크를 참조하겠습니다. https://ko.wikipedia.org/wiki/%EC%B6%94%EC%83%81_%EC%9E%90%EB%A3%8C%ED%98%95
추상 자료형 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 추상적 자료형(Abstract Data Type, 줄여서 ADT)은 컴퓨터 과학에서 자료들과 그 자료들에 대한 연산들을 명기한 것이다. 추상적 자료형은 구현 방법을 명시하고 있지 않다는 점에서 자료 구조와 다르다. 비슷한 개념의 추상적 자료 구조는 각 연산의 시간 복잡도를 명기하고 있지만 추상적 자료형에서는 이것조차 명기하지 않는다. 추상적 자료형은 인터페이스와 구현을 분리하여 추상화 계층을 둔 것이다. 예를 들어, 전기
ko.wikipedia.org
abstract data type이란 우리가 알고 있는 int, float, long, char과 같은 데이터 타입이랑 뭐가 다를까요?
ADT는 어떤 data type(자료형)이나 data structure(자료구조)의 설명서와 같은 개념입니다.
그 data structure가 제공하는 기능(fucntion)에 대한 설명이고, 구체적인 구현(implementation)은 하지 않습니다.
(data structure는 구체적인 구현을 제공합니다.)
그래서 사용자는 해당 자료구조(data structure)의 사용법만 알면 내부 구현을 몰라도 자료구조를 사용할 수 있습니다.
그럼 본격적으로 Map이라는 자료구조의 ADT를 살펴보겠습니다.
[ MAP ]
- map은 key-value 엔트리들의 집합(collection)
- position : 맵에서 entry를 참조(reference)할 수 있게 하는 특수한 포인터 오브젝트
- iterator : C++ STL과 일관되게 하기 위하여 iterator라는 좀 더 일반적인 객체를 정의함. iterator를 통해 맵에서 entry들을 이리저리 옮겨 다닐(navigate) 수도 있고 참조(reference)할 수도 있다.
- iterator p가 주어졌다면 p가 가리키는 entry를 *p로 dereference하여 접근할 수 있다.
- 개별 key와 value는 p->key()와 p->value() 로 접근
- 맵에서 모든 entry들을 열거하기 위해, p를 M.begin()으로 initialize하고, M.end()와 같아지기 전까지 반복적으로 p를 증가한다(incrementing operator사용 ++p ).
- end : 특별한 sentinel iterator이다. M.end()로 얻는다. 맵의 마지막 원소 바로 뒤에 위치한 가상 원소를 가리킨다. '그러한 오브젝트(엔트리)가 없다'라는 것을 지시할 때 사용한다.
sentinel은 유의미한 원소를 저장하고 있진 않지만, 특별한 위치를 나타내는 깃발같은 노드/position이라고 생각하면 될 것 같습니다.
[ MAP ADT functions ]
M은 map type 객체, p 는 맵의 iterator
size () : M에 저장된 entry수를 반환
empty() : M이 비었으면(empty) true를 반환. 그렇지 않으면 false를 반환
find(k) : M이 e=(k,v)에 해당하는 엔트리를 갖고 있으면, 그 엔트리를 참조하는 iterator p를 반환한다. key가 k와 같은 entry가 없으면 iterator end를 반환한다.
put(k, v) : 만약 M이 key가 k와 같은 엔트리를 갖고 있지 않다면 entry (k,v)를 M에 추가한다. 만약 key가 k인 엔트리가 이미 존재한다면, 그 엔트리의 value를 v로 대체한다. 이렇게 삽입되거나, 수정된 엔트리에 대한 iterator를 반환한다.
erase(k) : M에서 key가 k인 entry를 지운다. 그런 entry가 없으면 error condition이 발생한다.
erase(p) : M에서 iterator p가 참조하는 entry를 지운다. p가 end sentinel을 가리키고 있다면 error condition발생
begin() : M의 첫번째 entry반환
end() : M의 마지막 entry바로 뒤의 가상의 position을 가리키는 iterator 반환
Map에서 entry를 제거(remove)하는 두 가지 방법
1. key - based : argument로 key를 받아 해당하는 entry제거
2. iterator - based : argument로 iterator를 받아 그 iterator가 참조하는 entry 제거
key 'k'로 부터 해당 엔트리를 참조하는 iterator 'p'를 얻을 수 있다. (find함수 이용)
p=M.find(k)
그리고 M.erase(p)
방법 2의 장점 : map에서 해당 key의 entry를 찾는 일을 반복할 필요가 없다! => 더욱 효과적
Map update
'put'을 이용하여 맵에서 entry를 삽입하거나 수정할 수 있다.
put은 아주 명시적으로 디자인되었다. 왜냐하면 우리는 key값이 unique하길 바라기 때문이다. 즉, 서로 다른 value에 대하여 같은 key값을 갖는 것을 허용하지 않는다. 하지만 좀 더 나중에 살펴볼 section 9.5에서는 같은 key값을 갖는 여러 instances를 허용한다.
entry의 value가 변해도 iterator는 같은 entry와 계속해서 연관된다.
MAP ADT Operation
'전자공학 > 자료구조(정보시스템프로그래밍)' 카테고리의 다른 글
| ch7.2 Tree Traversal Algorithm (0) | 2019.06.15 |
|---|---|
| ch.7 Tree 자료구조 (0) | 2019.06.15 |
| 9.1 Map : 맵과 맵의 엔트리, 자료구조 맵 맛보기 (0) | 2019.05.10 |
