C++, STL-2 set, map, hash

Set 컨테이너

set 컨테이너의 경우 

Red Black Trees를 사용하여 만들어진다.

Red Black Trees = 이진트리와 비슷한 형태로 만들어진다. 

Input에 상관없이 정렬되어서 출력 된다.

중복을 허용하지 않는다. 

 

find	random access	I/O	I/O end
O(Log n)	O(Log n)	O(Log n)	O(Log n)

#include <iostream>
#include <set>

int main(int argc, char const *argv[])
{
	str::set<int> nums{1,2,3,4,5};
    
    for(const int num : nums)
    {
    	std:count << num << " ";
    }
    std:cout << std::endl;
    
    return 0;
}

Multi-Set 컨테이너

일반적인 set컨테이너와는 다르게 여러개의 키를 가질 수 있다.

시간복잡도는 Search, Removal, Insertion Operations 모두 O(log n)의 시간복잡도를 가진다. 

Unordered-Set 컨테이너 

순서 없이 출력된다.

시간복잡도는 Search, Removal, Insertion Operations 모두 O(1)의 시간복잡도를 가진다. 

rehashing = O(n)

bucket_count 

Map 컨테이너

map 컨테이너도 set 컨테이너와 마찬가지로 

red-black trees로 만들어진다.

시간복잡도는 Search, Removal, Insertion Operations 모두 O(log n)의 시간복잡도를 가진다. 

UnOrdered Map 컨테이너

시간복잡도는 Search, Removal, Insertion Operations 모두 O(1)의 시간복잡도를 가진다. 

내부적으로 요소는 특정 순서로 정렬되지 않고 버킷으로 구성됩니다. 요소가 배치되는 버킷은 전적으로 해당 값의 해시에 따라 다릅니다. 이렇게 하면 개별 요소에 빠르게 액세스할 수 있습니다. 해시가 계산되면 요소가 배치된 정확한 버킷을 참조하기 때문입니다.

수정하면 요소의 해시가 변경되고 컨테이너가 손상될 수 있으므로 컨테이너 요소를 수정할 수 없습니다