[42서울] ft_containers[4] - 맵 구현

서론

key-value의 형태의 pair를 정렬된 순서로 저장하는 컨테이너. 각 key는 전부 고유한 값을 가지며, 검색과 삽입 삭제가 전부 O(log n)으로 효율적이다.

 

내부의 자료구조가 tree(주로 rbtree)로 구현되어있다. 서브젝트에서 얘기하듯이 배열 같은 ‘적합하지 않은’ 자료구조로 구현해서는 안되며, 20배 이상 차이가 나면 안 된다고 되어있기 때문에 BST 같은 지나치게 단순한 tree를 선택해도 안되고 자체적으로 밸런싱 기능이 있는 tree를 자료구조로 사용해야 한다.

 

맵의 항목들을 보면서 필요한 함수들을 트리에 구현하면 조금 더 편하다.

 

 

들어가야 하는 구성요소

Member types

• key_type: 맵의 키(Key) 유형
• mapped_type: 맵의 값(Value) 유형
• value_type: **std::pair<const Key, T>**로 구성된 요소의 유형
• key_compare: 맵에서 사용되는 비교 기능의 유형
• value_compare: 맵에서 **value_type**에 대한 비교 기능의 유형
• allocator_type: 맵에서 사용하는 할당기(allocator)의 유형
• reference: **value_type**에 대한 참조자 유형
• const_reference: **value_type**에 대한 상수(const) 참조자 유형
• pointer: 할당된 객체에 대한 포인터(pointer) 유형
• const_pointer: 할당된 상수(const) 객체에 대한 포인터(pointer) 유형
• difference_type: 두 반복자(iterator) 간 거리 차이의 유형
• size_type: 객체의 크기를 저장하는 unsigned 정수형 유형

Member functions

• (constructor) : 기본생성자, 채우기 생성자, 복사 생성자 세 개 구현
• (destructor) : 모든 요소들을 삭제하고 컨테이너는 allocator에 의해 deallocate 됨
• operator= : 기존 컨테이너의 값을 복사해서 새로 만듦

Iterators:

• begin(): 맵의 첫 번째 요소를 가리키는 반복자(iterator)를 반환합니다.
• end(): 맵의 마지막 요소 다음을 가리키는 반복자(iterator)를 반환합니다.
• rbegin(): 맵의 마지막 요소를 가리키는 역순 반복자(reverse iterator)를 반환합니다.
• rend(): 맵의 첫 번째 요소 앞을 가리키는 역순 반복자(reverse iterator)를 반환합니다.

Capacity:

• empty(): 맵이 비어 있는지 여부를 반환합니다.
• size(): 맵에 저장된 요소의 수를 반환합니다.
• max_size(): 맵이 최대로 저장할 수 있는 요소의 수를 반환합니다.

Element access:

• at(): 주어진 키(key)에 해당하는 값(value)에 접근하며, 값이 없는 경우 out_of_range 예외를 throw 합니다.
• operator[]: 주어진 키(key)에 해당하는 값(value)에 접근하며, 값이 없는 경우 해당 키의 새 요소를 삽입하고 그 참조를 반환합니다.

Modifiers:

• insert(): 맵에 새로운 요소를 삽입합니다. pair 단일 요소를 삽입하거나, 반복자 위치를 같이 입력받거나(단, 그 위치에 입력되는 것은 아님), 이터레이터 두 개를 받아서 여러 개의 값을 입력할 수 있다.
• erase(): 맵에서 요소를 제거합니다. 이터레이터, key 로 삭제가 가능하고, 이터레이터 두 개로 범위를 삭제할 수도 있다.
• swap(): 두 맵의 내용을 교환합니다.
• clear(): 맵의 모든 요소를 제거합니다. 당연히 deallocate 도 실행되어야 함

Observers:

• key_comp(): 맵에서 키(key)를 비교하는 데 사용되는 이진 함수 비교자(binary function comparator)를 반환합니다. 해당 함수는 map을 만들 때 3번째 템플릿으로 받을 수 있으며 기본값은 less<key_type>이므로 첫 번째 인자가 두 번째보다 작은 지를 확인함
• value_comp(): 맵에서 값을 비교하는 데 사용되는 이진 함수 비교자(binary function comparator)를 반환합니다.

Operations:

• find(): 주어진 키(key)를 가진 요소를 검색합니다.
• count(): 맵 내에 주어진 키(key)가 몇 번 등장하는지를 반환합니다.
• lower_bound(): 주어진 키(key) 보다 크거나 같은 첫 번째 요소를 검색합니다. 단 upper_bound 와는 다르게 key_comp를 사용하기 때문에 map의 compare가 달라지면 다른 값이 나올 수 있음.
• upper_bound(): 주어진 키(key) 보다 큰 첫 번째 요소를 검색합니다.
• equal_range(): 주어진 키와 관련된 이터레이터의 pair를 반환함. pair의 첫 번째 값은 호출된 key와 같은 반복자, 두 번째 값은 다음 반복자로, 해당 key가 없으면 둘 다 end를 가리키게 됨

Allocator:

• get_allocator(): 맵에서 사용하는 allocator를 반환함

Non-member functions

• relational operators: map 객체 간의 관계를 비교하는 연산자들
• swap: 두 개의 map 객체를 바꿉니다

 

추가 구현 요소

pair, make_pair

• pair는 다른 타입 두 개의 값을 하나의 객체로 관리하기 위해 사용되는 클래스인데, map에서 key와 value를 보관하기 위해 사용된다. make_pair는 그러한 pair를 만들기 위해 사용되는 함수이다.

 

테스트

#include <time.h>
#include <iostream>
#include "map.hpp"
#include <map>
#include <fstream>
#include <time.h>

static void printmap(ft::map<std::string, int>& m, std::ofstream& ftFile) {
	ftFile << '{';
	ft::map<std::string, int>::const_iterator b = m.begin();
	ft::map<std::string, int>::const_iterator e = m.end();
	while (b != e) {
		ftFile << b->first << ':' << b->second << ' ';
		b++;
	}
	ftFile << "}\n";
}

static void ft_test(std::ofstream& ftFile) {
	clock_t g_start = clock();

	ft::map<std::string, int> mp1;
	mp1["something"] = 21;
	mp1["anything"] = 42;
	mp1["that thing"] = 121;
	mp1["whatever"] = 555;
	ftFile << "mp1: ";
	printmap(mp1, ftFile);

	ft::map<std::string, int> mp2(mp1.find("anything"), mp1.end());
	ftFile << "mp2: ";
	printmap(mp2, ftFile);

	ft::map<std::string, int> mp3(mp1);
	ftFile << "mp3: ";
	printmap(mp3, ftFile);

	ftFile << "mp3[anything] with []: " << mp3["anything"] << std::endl;
	ftFile << "mp3[non_existing] with []: " << mp3["non_existing"]
						<< std::endl;
	printmap(mp3, ftFile);

	ft::map<std::string, int>::reverse_iterator rvrIt = mp3.rbegin();
	ftFile << '{';
	for (; rvrIt != mp3.rend(); rvrIt++) {
		ftFile << rvrIt->first << ':' << rvrIt->second << ' ';
	}
	ftFile << "}\n";

	ftFile << "mp3 empty: " << (mp3.empty() ? "true" : "false") << std::endl;
	ftFile << "mp3 size: " << mp3.size() << std::endl;

	ftFile << "mp3 clear\n";
	mp3.clear();
	ftFile << "mp3 size: " << mp3.size() << std::endl;
	ftFile << "mp3 insert (from mp2)\n";
	mp3.insert(mp2.begin(), mp2.end());
	ftFile << "mp3 size: " << mp3.size() << std::endl;
	ftFile << "mp3: ";
	printmap(mp3, ftFile);

	ftFile << "erase 'that_thing'\n";
	mp3.erase(mp3.find("that thing"));
	ftFile << "erase 'non_existing'\n";
	mp3.erase("non_existing");
	ftFile << "mp3: ";
	printmap(mp3, ftFile);

	mp3.swap(mp2);
	ftFile << "mp3: ";
	printmap(mp3, ftFile);

	ftFile << "mp3 == mp2: " << (mp3 == mp2 ? "true" : "false") << std::endl;
	ftFile << "mp3 < mp2: " << (mp3 < mp2 ? "true" : "false") << std::endl;
	ftFile << "mp3 >= mp2: " << (mp3 >= mp2 ? "true" : "false") << std::endl;

	ft::map<int, int> mp4;
	for (int i = 0, j = 100; i < 300000; i++, j++) {
		mp4.insert(ft::make_pair(i * 2, j));
	}
	ftFile << "count 41: " << mp4.count(41) << std::endl;
	ftFile << "count 50: " << mp4.count(50) << std::endl;
	ftFile << "count 300005: " << mp4.count(300005) << std::endl;
	ftFile << "find 26: " << mp4.find(26)->first << std::endl;
	ftFile << "lower bound 127: " << mp4.lower_bound(127)->first << std::endl;
	ftFile << "upper bound 244: " << mp4.upper_bound(244)->first << std::endl;

	clock_t g_end = clock();
	ftFile << "ft_map_Execution time (ms): " << (double)(g_end - g_start) / CLOCKS_PER_SEC * 1000 << "ms" << std::endl;
}


static void printMap(const std::map<std::string, int>& m, std::ofstream& stlFile) {
	stlFile << '{';
	std::map<std::string, int>::const_iterator b = m.begin();
	std::map<std::string, int>::const_iterator e = m.end();
	while (b != e) {
		stlFile << b->first << ':' << b->second << ' ';
		b++;
	}
	stlFile << "}\n";
}

static void stl_test(std::ofstream& stlFile) {
	clock_t g_start = clock();

	std::map<std::string, int> mp1;
	mp1["something"] = 21;
	mp1["anything"] = 42;
	mp1["that thing"] = 121;
	mp1["whatever"] = 555;
	stlFile << "mp1: ";
	printMap(mp1, stlFile);

	std::map<std::string, int> mp2(mp1.find("anything"), mp1.end());
	stlFile << "mp2: ";
	printMap(mp2, stlFile);

	std::map<std::string, int> mp3(mp1);
	stlFile << "mp3: ";
	printMap(mp3, stlFile);

	stlFile << "mp3[anything] with []: " << mp3["anything"] << std::endl;
	stlFile << "mp3[non_existing] with []: " << mp3["non_existing"]
	<< std::endl;
	printMap(mp3, stlFile);

	std::map<std::string, int>::reverse_iterator rvrIt = mp3.rbegin();
	stlFile << '{';
	for (; rvrIt != mp3.rend(); rvrIt++) {
		stlFile << rvrIt->first << ':' << rvrIt->second << ' ';
	}
	stlFile << "}\n";

	stlFile << "mp3 empty: " << (mp3.empty() ? "true" : "false") << std::endl;
	stlFile << "mp3 size: " << mp3.size() << std::endl;

	stlFile << "mp3 clear\n";
	mp3.clear();
	stlFile << "mp3 size: " << mp3.size() << std::endl;
	stlFile << "mp3 insert (from mp2)\n";
	mp3.insert(mp2.begin(), mp2.end());
	stlFile << "mp3 size: " << mp3.size() << std::endl;
	stlFile << "mp3: ";
	printMap(mp3, stlFile);

	stlFile << "erase 'that_thing'\n";
	mp3.erase(mp3.find("that thing"));
	stlFile << "erase 'non_existing'\n";
	mp3.erase("non_existing");
	stlFile << "mp3: ";
	printMap(mp3, stlFile);

	mp3.swap(mp2);
	stlFile << "mp3: ";
	printMap(mp3, stlFile);

	stlFile << "mp3 == mp2: " << (mp3 == mp2 ? "true" : "false") << std::endl;
	stlFile << "mp3 < mp2: " << (mp3 < mp2 ? "true" : "false") << std::endl;
	stlFile << "mp3 >= mp2: " << (mp3 >= mp2 ? "true" : "false") << std::endl;

	std::map<int, int> mp4;
	for (int i = 0, j = 100; i < 300000; i++, j++) {
		mp4.insert(std::make_pair(i * 2, j));
	}
	stlFile << "count 41: " << mp4.count(41) << std::endl;
	stlFile << "count 50: " << mp4.count(50) << std::endl;
	stlFile << "count 300005: " << mp4.count(300005) << std::endl;
	stlFile << "find 26: " << mp4.find(26)->first << std::endl;
	stlFile << "lower bound 127: " << mp4.lower_bound(127)->first << std::endl;
	stlFile << "upper bound 244: " << mp4.upper_bound(244)->first << std::endl;

	clock_t g_end = clock();
	stlFile << "stl_map_Execution time (ms): " << (double)(g_end - g_start) / CLOCKS_PER_SEC * 1000 << "ms" << std::endl;
}

int main()
{
    std::ofstream stlFile("./stlFile.txt");
	if (stlFile.fail())
	{
		std::cerr << "Error!" << std::endl;
	}
    std::ofstream ftFile("./ftFile.txt");
	if (ftFile.fail())
	{
		std::cerr << "Error!" << std::endl;
	}

    ftFile << "\n***** VECTOR TEST *****\n" << std::endl;
	ft_test(ftFile);
	ftFile.close();

    stlFile << "\n***** VECTOR TEST *****\n" << std::endl;
	stl_test(stlFile);
	stlFile.close();

	system("diff ftFile.txt stlFile.txt");
}

트리만 세 번을 만든 이유가 이 테스트기에 있는데, 하나는 rbtree를 구현했을 때에 

	std::map<std::string, int>::reverse_iterator rvrIt = mp3.rbegin();
	stlFile << '{';
	for (; rvrIt != mp3.rend(); rvrIt++) {
		stlFile << rvrIt->first << ':' << rvrIt->second << ' ';
	}

부분이었다.

 

왜인지 모르겠는데 end가 이상한 값을 가리키는 현상이 있어서 코드를 통째로 버렸다.

속도는 훨씬 빨랐습니다.

다음은 트리 편에서 말한 것처럼 splay tree의 선형 체인 문제가 있었다.

chaGPT는 이게 이론적인 경우에만 그렇다고 했는데, 그렇다고 멀쩡한 테스터기를 '이건 이론적인 경우'라며 내가 통과할 수 있게 고치는 게 올바르지 못한 방법이라고 생각해서 이것도 엎어버렸다.

 

결국 옛날 컴파일러의 avl tree를 보고 구현하게 되었는데, 처음에 만든 iterator는 그대로 둔 채로 tree를 다시 만들었는데 멀쩡하게 동작하는 걸 보면 아마 tree의 마지막 값을 참조해 올 때 문제가 있었는데 그걸 찾지 못했던 것 같다.