태그: C++

정렬 기준에 대한 첨언

vector<int> v;

…

sort(v.begin(), v.end(), greater<int>());

…

bool a5Exists = binary_search(v.begin(), v.end(), 5);

bool a5Exists = binary_search(v.begin(), v.end(), 5, greater<int>());

vector<int> v;

v.reserve(10);

for(int i=1; i<=10; ++i)

{

   v.push_back(i);

}

v[3] = v[5] = v[9] = 99;

remove(v.begin(), v.end(), 99);

   v.begin()                     v.end()

     ↓                             ↓

   ┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐

   │1 │2 │3 │99│5 │99│7 │8 │9 │99│

   └──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘

   v.begin()           v.end()

    ↓                   ↓

   ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐

   │1│2│3│5│7│8│9│?│?│?│

   └─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘

                  ↑

       remove에서 리턴된 반복자위치

vector<int> v;

…

v.erase(remove(v.begin(), v.end(), 99), v.end());

• vector, string, deque 혹은 C++ 배열에 대해 전체 정렬을 수행할 필요가 있을 때에는 sort 나 stable 소트를 사용한다.
  
• vector, string, deque 혹은 C++ 배열에 대해 상위 n개의 요소만 순서에 맞추어 뽑아내고 싶다면 partial_sort를 사용한다.
  
• vector, string, deque 혹은 C++ 배열에 대해 상위 n개의 요소를 뽑되 순서를 고려할 필요가 없다면 nth_element가 적합하다.
  
• 표준 시퀀스 컨테이너가 있고, 이 컨테이너의 요소들을 어떤 기준에 만족하는 것들과 그렇지 않은 것들을 모아 구분하고 싶다면 partition 혹시 stable_partition 을 사용한다. (등급을 구분하거나 더 나아가 몇 등급이상의 것만 얻거나)
  
• list의 경우 partition, stable_partition 은 직접 사용이 가능하며 sort 와 stable_sort 알고리즘 대신 list::sort 멤버 함수를 사용할수 있다. 만일 partial_sort나 nth_element의 기능이 필요하다면 백터등으로 변환하거나 반복자를 백터에 넣어 정렬하는 간접적인 방법을 사용해야 한다.

1. partition
   
2. stable_partition
   
3. nth_element
   
4. partial_sort
   
5. sort
   
6. stable_sort
   

int transmogrify(int x);                // 정수 x를 받아

                                        // 새로운 값을 생성

vector<int> values;

vector<int> result;

transform(values.begin(), values.end(),

                  result.end(), // 알고리즘의 결과를

                  transmogrify);        // result 뒤에 추가 시도

ifstream inputFile(“file.txt”);

string fileData((istream_iterator<char>(inputFile)),

                istream_iterator<char>());

vector<int> v;

v.reserve(5);                           // 미리 할당 EffectiveSTL14 를 참고

for( int i=1; i<=5; i++) {

        v.push_back(i);

}
// 3을 가리킨다.

vector<int>::reverse_iterator ri = find(v.rbegin(), v.rend(), 3);
// i가 ri의 기점과 같게 한다.

vector<int>::iterator i(ri.base());

1. iterator는 모든 다른 반복자로 변환이 가능하다.
   
2. reverse 반복자류는 해당하는 종류의 반복자로 base() 맴버함수를 통해 변환이 가능하다.
   (reverse_iterator -> iterator, const_reverse_iterator -> const_iterator )
   
3. reverse_iterator는 const_reverse_iterator 로 변환이 가능한다.
   

• 어떤 형태의 insert와 erase 멤버함수는 무조건 iterator 만을 넘겨야 한다.
  
• const_iterator 를 iterator로 암시적으로 변환하는 방법은 없고 굳이 바꾸자면 EffectiveSTL27의 내용을 참조한다. 하지만 일반성도 떨어지고 효율에 대한 보장도 할수 없다.
  
• reverse_iterator를 iterator로 변환할수 있으나, 변환후 약간의 조정이 필요하다. 자세한 내용은 EffectiveSTL28을 참고한다.