vector를 map 처럼 활용하기

vector를 map 처럼 활용하기

vector는 메모리가 연속되어있기에 탐색속도를 따라갈 컨테이너가 없다.

또한 map은 자식노드의 포인터, 부모노드에대한 포인터를 가지고 있기때문에 vector보다 차지하는메모리가 크다.

정렬된 vector에 데이터를 저장하는 것은 연관컨테이너(map,set,,)보다 메모리 소비량이 적을가능성이 있고 , cash miss가 없기때문에 빠르다!

하지만 map처럼 만든 vector는 언제나 정렬되어있어야 한다.

따라서 삽입및 삭제동작과 탐색동작이 거의 섞이지 않는 경우에는 벡터가 낫겠다.

맵에 저장되는 객체는 pair이다. 하지만 vector로 map을 흉내낼때는 const를 떼야된다.

왜냐면 벡터를 정렬할때 , 대입연산을 통해 이동하기 때문이다~

벡터에 저장되는 pair 객체는 pair로 만들어야한다.

벡터를 정렬할때, pair 에 기본적으로 있는 operator< 는 pair의 두 멤버 데이터를 모두 고려하기 때문에, 정렬에 쓸 비교함수를 직접 만들어줘야겠다~

그리고 탐색을 할때 필요한 탐색용 함수도 있어야겠다!!

탐색용함수를 만들때, 이게 키타입인지 페어객체인지 알수가 없어서 모든 경우를 고려해서 만들어 줘야한다.

만들어진 예제코드

typedef pair Data; class DataCompare { public: bool operator() (const Data& lhs, const Data& rhs) const{ //검색용 return keyLess(lhs.first,rhs.first); } bool operator() (const Data& lhs, const Data::first_type& rhs) const{ //탐색용 return keyLess(lhs.first,rhs); } bool operator() (const Data::first_type& lhs, const Data& rhs) const{ //탐색용 return keyLess(lhs,rhs.first); } private: //실제로 비교하는 함수 inline bool keyLess(const Data::first_type& key1,const Data::first_type& key2) const{ return key1

위 코드는 정렬, 탐색 모두 잘 적용된다.

vector vd; //데이터 삽입 ... string s = "search_data"; if(binary_search(vd.begin(),vd.end(),s,DataCompare())) { ... } auto i =lower_bound(vd.begin(),vd.end(),s,DataCompare()); if(i !=vd.end()&& !(i->first < s )){ ... } pair::iterator range = equal_range(vd.begin(),vd.end(),s,DataCompare()); if(range.first!=range.second){ ... }

정렬된 컨테이너에서 사용할수 있는 탐색함수들~

binary_search: 이진탐색

lower_bound: 찾고자 하는 대상보다 크거나 같은 데이터의 첫 번째 위치

upper_bound: 찾고자 하는 값보다 큰 값이 처음으로 나타나는 위치

equal_range: lower_bound 와 upper_bound를 동시에 반환하는 iterPair 반환 함수

from http://icehongsifrzzn.tistory.com/84 by ccl(A) rewrite - 2021-08-10 13:00:30