C++ : unordered_set : 개념, 차이점, 장점, 예제, 구현

C++ : unordered_set : 개념, 차이점, 장점, 예제, 구현

 

set

자동 정렬되는 컨테이너입니다. 키들을 저장하고, 이진 탐색 트리를 기반으로 합니다. 탐색 시간은 O( log n ) 입니다. 삽입과 제거가 빈번해지면 느립니다. 

 

 

undorderd_set

std::map과 동일한 문제로 나오게 되었습니다. 자동 정렬되지 않는 set이라고 생각하면 됩니다. 해쉬 테이블 기반으로 합니다. 탐색시간이 O(1) 이며 최악의 경우 O(n) 입니다. 버킷 때문에 메모리 사용량이 증가할 수 있습니다.

 

 

#include <iostream>
#include <set>
#include <unordered_set>
#include <chrono>
#include "SpeedTestExample.h"

using namespace std;

namespace samples
{
	void SpeedTestExample()
	{
		// RUN THIS EXAMPLE IN RELEASE CONFIG

		// initialize test
		set<int> orderedSet;
		unordered_set<int> unorderedSet;

		const int NUMBER_TO_INSERT_LATER = 1023;
		const int MAX_NUMBER_IN_SET = 100000;

		unorderedSet.reserve(MAX_NUMBER_IN_SET);

		static_assert(MAX_NUMBER_IN_SET > NUMBER_TO_INSERT_LATER, "MAX_NUMBER_IN_SET should be greater than NUMBER_TO_INSERT");

		for (int i = 0; i < MAX_NUMBER_IN_SET; i++)
		{
			if (i == NUMBER_TO_INSERT_LATER)
			{
				continue;
			}

			orderedSet.insert(i);
			unorderedSet.insert(i);
		}

		auto start = chrono::high_resolution_clock::now();

		orderedSet.insert(NUMBER_TO_INSERT_LATER);

		auto end = chrono::high_resolution_clock::now();

		auto elapsedNanoSeconds = end - start;

		cout << "Inserting into orderedSet: " << elapsedNanoSeconds.count() << " ns" << endl;

		start = chrono::high_resolution_clock::now();

		unorderedSet.insert(NUMBER_TO_INSERT_LATER);

		end = chrono::high_resolution_clock::now();

		elapsedNanoSeconds = end - start;

		cout << "Inserting into unorderedSet: " << elapsedNanoSeconds.count() << " ns" << endl;

		// Uncomment this when you run it with Release configuration
		// system("pause"); 
	}
}

 

unordered_set과 set의 속도를 시간 측정하는 코드 샘플입니다. 시간 측정을 할 때에는 release 모드로 빌드해야 보다 정확한 시간 측정이 가능하다고 합니다. set과 방식은 동일하지만, 빈번하게 값을 가져오는 경우에는 unorderd_map을 활용해야 한다는 것을 알게 되었습니다. 원본 코드는 아래 경로에서 확인할 수 있습니다.

 

https://github.com/POCU/COMP3200CodeSamples/blob/master/11/SpeedTestExample.cpp

POCU/COMP3200CodeSamples