stl 썸네일형 리스트형 STL lower_bound() upper_bound() 이번에는 모든 분들이 다 아시는 sort를 제외한 다른 sorting 함수와 lower(OR upper)_bound()를 알아보도록 하겠습니다. [binary_search(arr_begin,arr_end,find_value) : 검색해주는 함수로서 찾는 값이 존재하면 True, 아니면 False를 리턴한다.] 이진 탐색(binary search)를 사용하는데, 정렬이 되어 있다는 가정하에 값을 빨리 찾고 싶을 때 사용합니다. arr_begin - 시작 arr_end - 끝 find_value - 찾고자 하는 값 [1 4 5 7 8 11 12 12 16 21 35] 11개의 값이 있다고 가정하자, 만약 여기서 21이라는 값을 찾고 싶다면, 어떻게 할까? 반복문을 사용해서 처음부터 끝까지 비교를 해 보면 됩.. 더보기 STL Binary Search function binary_search(target)는 target value이 들어 있는 배열(or vector)의 인덱스를 반환하는 줄 알았으나, bool 값을 반환을 한다. STL에서 지원하는 binary_search()는 세 개의 매개변수를 받는다. 첫 번째는 찾고자 하는 범위의 시작점, 두 번째는 찾고자 하는 범위의 끝점이다. 이 둘은 반복자(iterator)로 주어져야 한다. 세 번째 매개 변수는 찾고자 하는 수이다. 찾고자 하는 수를 매개 변수로 전달하면 된다. // binary_search(반복자.시작점, 반복자.끝점, 찾고자 하는 값); // 은 찾고자 하는 값을 찾으면 true를, 찾지 못하면 false를 반환한다. vector nums; int target = 3; bool isFound = bin.. 더보기 (ordered) Map vs Unordered Map C++에서 map은 red-black tree로 구현이 된다. Unordered Map은 hash table로 구현이 된다. 차이점 1. map과 unordered map의 큰 차이점은 구현에서부터 이미 차이가 난다. 2. map은 탐색 연산의 시간 복잡도가 O(log N)인 반면 unordered map은 hash table을 이용하므로 O(1) 3. map은 AVL 트리와 같이 삽입/삭제 시 항상 밸런스를 맞추기 위해 정렬을 하지만, unordered map은 그렇지 않다. 결론 1. 정렬을 필요로 하는 경우가 아니라면 연산 속도 면에서 unordered map이 훨~~~~~씬 유리 2. 일반적으로 key값이 짧고, int형인 경우 unordered map을 권장( 그 이유는 hash function.. 더보기 이전 1 다음