Map & Dictionary

개요

탐색이 용이한 {키: 값} entry의 collection. 

 

맵은 중복 키를 허용하지 않고, 딕셔너리는 중복 키를 허용한다.

 

 

맵과 딕셔너리의 Entry ADT

{키: 값} 쌍을 저장한다.

 

다음 네 가지 메소드를 지원한다.

• key(): 키 반환
• value(): 값 반환
• setKey(k): 키를 k로 변경
• setValue(v): 값을 v로 변경

 

맵, 딕셔너리 ADT

두 ADT는 공통적으로 다음 메소드를 지원한다.

• find(k): 키가 k인 entry를 탐색해 포인터를 반환한다. 존재하지 않는 경우 iter::end를 반환한다.
• put(k, v): 키가 k, 값이 v인 entry를 삽입한다.
• erase(k): 키가 k인 entry를 삭제한다.
• 추가로 size, empty, begin, end를 지원할 수 있다.

딕셔너리의 findAll(k)는 키가 k인 entry의 포인터를 모두 반환한다.

 

 

리스트 기반 맵

Unsorted list를 이용하여 구현할 수 있다.

 

Doubly-linked list를 이용하며, 선형탐색으로 삽입 삭제 탐색을 한다.

 

 

해시 테이블 기반 딕셔너리

충돌을 Separate chaining에 기반하여 처리할 수 있다.

 

각 cell의 리스트 기반 딕셔너리에 대하여 operation들을 할 수 있다.

 

 

Search Table 

Sorted array를 이용하여 구현한 딕셔너리이다.

 

키에 대해서 정렬하며, 키의 비교를 위해 external comparator를 사용한다.

 

탐색은 이진탐색을 이용해 O(log N)에 가능하다.

 

삽입과 삭제는 array가 그렇듯 O(N)에 가능하다.

 

 

Implementation

아래는 리스트 기반 맵을 적당히 구현한 것인데 별로 좋은 내용은 아니다.

 

#include <bits/stdc++.h>
using namespace std;

struct pii {
	int k, v;
	pii() { k = v = -1; }
	pii(int K, int V) { k = K, v = V; }
};

struct Map {
	int sz;
	vector<pii*> entry;
	
	Map() { sz = 0; }

	pii* find(int k) {
		for (pii* e : entry) {
			if (e->k == k) return e;
		}
		return nullptr; // should return entry.end() instead
	}
	pii* put(int k, int v) {
		for (pii* e : entry) {
			if (e->k == k) {
				e->v = v; return e;
			}
		}
		entry.push_back(new pii(k, v));
		sz += 1;
		return entry.back();
	}
	void erase(int k) {
		for (int i = 0; i < sz; ++i) {
			if (entry[i]->k == k) {
				entry.erase(entry.begin() + i);
				sz -= 1;
				return;
			}
		}
	}
	int size() { return sz; }
};

int main() {
	Map T;
	int TEST; cin >> TEST; while (TEST--) {
		string oper; int k, v; 
		cin >> oper;
		if (oper == "find") {
			cin >> k;
			pii* req = T.find(k);
			if (req) cout << T.find(k)->v << "\n";
			else cout << "NULL\n";
		}
		if (oper == "put") {
			cin >> k >> v;
			cout << T.put(k, v)->v << "\n";
		}
		if (oper == "erase") {
			cin >> k;
			T.erase(k);
		}
	}
}