when to use STL data structures(multimap)

int main() {
    multimap<int, int> test;
    test.insert(pair<int, int>(3, 4));
    test.insert(pair<int, int>(2, 4));
    test.insert(pair<int, int>(1, 4));
    test.insert(pair<int, int>(1, 1));
    test.insert(pair<int, int>(1, 2));
    // 두번째 인자로는 정렬안함
    for (multimap<int, int>::iterator it = test.begin(); it != test.end(); it++) {
        cout << (*it).first << " " << (*it).second << endl;
    }
    while(1){ }
    map<int, int> namemap;
    namemap.insert(pair<int, int>(2, 3));
    namemap.insert(map<int, int>::value_type(4, 3));
    namemap[5] = 3;
    namemap[5] = 2; // 후자로 바꿔버리네.
    for (map<int, int>::iterator it = namemap.begin(); it != namemap.end(); it++) {
        cout << (*it).first << " " << it->second << endl;
    }
    while (1) {}
    return 0;
}
 

Array, vector : 

insert : O(n), delete : O(n) search O(1)

push_back : O(1)

vector을 만들고 sort까지 하려면 N^2logN

사용처 : read가 많은 경우

list :

insert : O(1), delete :  O(1), search O(n)

find min : O(N)

사용처 : I/O가 많은 경우

tree(BST):

insert: O(logN), delete : O(logN), search : O(logN)

make : O(N)

N개의 입력을 BST로 만들려면 NlogN

사용처 : I/O가 발생하면서 지속적으로 sort의 필요가 있는 경우

STL : map, set, multimap, multiset

heap

insert : O(logN), delete: O(logN), search : O(logN)

make : O(N)

find min/max : O(1)

사용처 : I/O가 발생하면서 지속적으로 최대/최소값을 트래킹할 필요가 있는 경우(sort는 안된다), 변형되어도 자동으로 최대최소값이 로딩됨

STL : priority_queue(max_heap)

hash table:

insert O(1) delete O(1) search O(1)

find min/max : O(N)

사용처 : 빠르게 I/O를 하고싶은 경우, 중복검사, 존재성검사

STL : unordered_map, unordered_set

있는 array를 sort하는 경우 >> NlogN

힙 build >> O(N) but unsorted. 하나씩 제거해가며 최대값을 하나씩 넣는 경우

여기서 하나씩 제거해가며 뺴야 되므로 logN 평균.

total : 실익 없음

BST build >> O(NlogN) 근데 결국 그 BST를 쓰려면 최소값부터 쭉 불러내야 하는데

그게 또 O(N) 뭐 전체 복잡도는 O(NlogN) 이지만..

사실상 정렬된 리스트를 유지하면서 움직이는거랑 무슨 차인지 모르겠지만

구현의 편의성이라고 하자 STL에 있으니까 ㅋㅋ