std::vector로 std::map구현해서 최적화 하기

std::map은 Key와 Value 값을 이용하여 데이터를 저장할 수 있는 자료구조 입니다.

알고리즘 문제를 풀면서 많이 접하며 사용을 해왔었다가 최근에 unordered_map을 주로 사용하게 되었었습니다.

map은 red-black tree 구조로 데이터가 저장되는데 이 구조는 데이터를 저장할때마다 키값을 기준으로 정렬을 시키게 됩니다. 정렬이 필요하다면 map을 사용하는 것이 좋지만 그렇지 않다면 불필요한 복잡도가 생기겠죠.

그래서 최적화를 위해 unordered_map을 주로 사용해왔는데, 오늘 아래와 같은 재미있는 글을 보게 되었습니다.

https://cpp-optimizations.netlify.app/dont_need_map/

You may not need std::map - CPP Optimizations diary

최적화에 관련된 글인데요. 첫번째 내용은 위에서 설명했던 내용이고 두번째 내용이 모든 element에 iteration 을 돌려야 할때 vector가 map보다 유리하다 라는 내용입니다. 이 내용도 vector와 map의 메모리 할당 방법을 이해한다면 충분히 vector를 사용하는 것이 성능향상에 유리하다는 것을 알 수 있을 것입니다. 관련하여 Stack Overflow에 쓰여진 글입니다.

글들은 그냥 읽어보기 좋았으나 흥미가 있던것은 vector로 map을 구현하고 lower_bound

를 이용하여 Element 선택이 가능하다라는 것에 한번 구현해보는게 어떨까해서 구현했고, 비슷한 내용이 없는 것 같아 기록을 남깁니다.

 

구현은 map에서 본인이 주로 사용하게 되는 조합인 <string, int>을 선택 했고, 다른 조합들도 아래의 예제를 통해 구현이 가능하리라 생각이 됩니다.cmp라는 커스텀 함수를 이용하여 특정 Element의 위치를 찾을 수 있었는데 여기서 생각을 해보니 lower_bound가 바이너리 서치이기 때문에 내가 찾기를 희망하는 Element에 가까운 위치를 찾을 수 있게 된다는 문제가 발생할 수 있었습니다. 그래서 본인은 함수로 빼서 찾은 위치에 있는 Element가 조건과 일치하지 않는다면 -1을 반환하도록 구현했습니다.

실제로 -1값을 가질 수도 있다는 것은 알지만 추가 구현은 귀찮아서 패스...

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool cmp(const pair<string, int> &a, const pair<string, int> &b) {
	return a.first < b.first;
}

int findElement(string s, vector<pair<string, int>> &v) {
	pair<string, int> target = { s,0 };
	auto pos = lower_bound(v.begin(), v.end(), target, cmp) - v.begin();
	
	if (v[pos].first == s)
		return v[pos].second;
	else
		return -1;
}


int main(void) {
	vector<pair<string, int>> my_map;

	my_map.push_back({ "orange",11 });
	my_map.push_back({ "apple",10 });
	my_map.push_back({ "pineapple",12 });

	sort(my_map.begin(), my_map.end());

	pair<string,int> target = { "pineapple",0 };
	auto pos = lower_bound(my_map.begin(), my_map.end(), target, cmp) - my_map.begin();

	cout << pos << " " << my_map[pos].second << "\n";

	cout << findElement("pineap", my_map);
	return 0;
}