[C/C++] 표준 템플릿 라이브러리(STL) - (3)

C++ STL

• 정렬

-  3가지 종류의 함수를 지원한다.

sort : 일반적인 정렬 함수
stable_srot : 정렬을 하되, 원소들 간의 순서를 보존한다.
ex) 벡터에 [a, b] 순으로 원소가 들어있고 a와 b의 크기가 같다고 했을 때, sort를 하면 [b, a] 순으로 변경될 가능성이 있지만 stable_sort를 사용하면 정렬 시에도 [a, b] 순으로 나오게 된다.
단, 이러한 특성 때문에 sort보단 느리다.
partial_sort : 배열의 일부분만 정렬한다.

-  sort에 들어가는 반복자의 경우 반드시 임의접근 반복자(RandomAccessIterator) 타입을 만족해야 하기 때문에, 벡터와 데크만 사용이 가능하고 나머지 컨테이너는 sort 함수를 사용할 수 없다.(리스트의 경우 반복자 타입이 BidirectionalIterator)

※  여기서 말하는 나머지 컨테이너란 앞에서 학습한 컨테이너들 중 벡터와 데크를 제외한 나머지 컨테이너를 의미한다.

-  sort 함수는 기본적으로 오름차순으로 정렬한다. sort 함수의 세번째 인자로 특정 조건을 넘겨주면 내림차순으로 정렬 등이 가능하다.

-  partial_sort는 [start, middle, end) 3개의 인자를 받는다. [start, end) 의 범위에 있는 원소들 중 가장 작은 원소들을 오름차순으로 [start, middle) 까지 정렬한다.

ex) {5, 1, 2, 9, 8, 3, 4} 라는 벡터가 있을 때 partial_sort(0, 3, 7) 과 같이 넘겨주면
{1, 2, 3, 8, 9, 4, 5} 와 같이 정렬된다.
즉, 필요한 부분 이외의 원소들은 랜덤한 순서로 정렬되는 것이다.
전체 원소 개수가 N이고 정렬하려는 부분의 크기가 M이라면 partial_sort의 복잡도는 O(NlogM)

-  C++ 표준에 따르면 sort 함수는 최악의 경우에도 O(nlogn) 이 보장되지만 stable_sort는 최악의 경우 O(n (logn)^2) 으로 작동한다.

• 원소 제거(remove, remove_if)

-  대부분의 컨테이너에서는 원소를 제거하는 함수 erase를 지원한다.

-  remove 함수는 실제로 원소를 삭제하는 연산을 수행하지 않는다. 특정 원소를 벡터 맨 뒤쪽으로 밀어두고, 해당 원소들을 erase 함수를 이용해서 제거하는 것이다.

ex)  {1, 2, 3, 5, 3, 4} 라는 벡터가 있을 때 remove(begin, end, 3) 을 호출하면
{1, 2, 5, 4, 3, 3} 으로 벡터가 재정렬 된다. 이를 erase(첫번째 3 위치, end) 로 호출하면 {1, 2, 5, 4} 로 변경되는 것이다.
=>  사용 예시 : vec.erase(std::remove(vec.begin(), vec.end(), 3), vec.end())

-  명확한 값이 아니라 특정한 조건을 만족하는 원소들을 제거하기 위해서는 remove_if 함수를 사용한다.

=>  remove_if 함수는 세번째 인자로 조건을 설명할 함수 객체를 전달받는다.

-  remove_if 함수의 세번째 인자로 함수 객체를 전달받는 경우, 전달되는 함수 객체는 이전의 호출에 의해 내부 상태가 달라지면 안된다.

=>  함수 객체 안에 인스턴스 변수를 넣는 것은 원칙상 불가하다.
==>  remove_if를 실제로 구현 했을 때, 해당 함수 객체가 여러번 복사 될 수 있기 때문

 

• 람다 함수(lambda function)

-  익명의 함수 객체를 뜻한다.

-  [capture list] (받는 인자) -> 리턴 타입 { 함수 본체 } 의 꼴로 사용된다.

=>  리턴 타입을 생략하면 컴파일러가 알아서 함수 본체에서 return 문을 보고 리턴 타입을 추측한다.
==>  return 경로가 여러군데여서 추측할 수 없다면 컴파일 오류 발생
=>  [capture list] (받는 인자) { 함수 본체 } 리턴 타입 생략 시 이런 꼴로 사용가능

-  캡처 목록(capture list)는 어떤 변수를 캡처할 지 작성하는 부분이다.

=>  캡처 리스트 사용 방법

[] : 아무것도 캡처 안함
[&a, b] : a는 레퍼런스로 캡처하고 b는 (변경 불가능한) 복사본으로 캡처
[&] : 외부의 모든 변수들을 레퍼런스로 캡처
[=] : 외부의 모든 변수들을 복사본으로 캡처
=>  클래스 멤버변수를 캡처 리스트에 넣고싶을 땐, 멤버 변수 자체를 넣는 것이 아니라 this를 통해 전달한다. => [this]

 

• 원소 수정하기(transform)

-  transform(시작 반복자, 끝 반복자, 결과를 저장할 컨테이너의 시작 반복자, Pred)

=>  Pred에는 remove_if의 세번째 인자처럼 함수 객체를 사용하면 된다.
==>  위에서 배운 람다함수를 사용하면 더 좋다.

-  transform 함수를 사용하면 for문을 쓸 필요도 없으며, 어떤 일을 하는 코드인지 더 간단 명료하게 나타낼 수 있다.

 

• 원소 탐색함수(find, 'find_if, any_of, all_of' 등)

-  find(시작 반복자, 끝 반복자, 값)

=>  시작 반복자부터 끝 반복자까지 순회하며 값과 같은 원소가 있는지 확인하고 이를 가리키는 반복자를 리턴한다.
==>  반복자에 따라서 앞에서 부터 찾기도 하고 뒤에서 부터 찾는 경우도 있다.(forward_iterator, reverse_iterator)
==>  컨테이너에 중복된 값이 있더라도 가장 먼저 찾은 것을 리턴한다.

-  컨테이너에서 기본적으로 find 함수를 지원한다면 이를 사용하는 것이 훨씬 빠르다.

=>  알고리즘 라이브러리에서의 find함수는 그 컨테이너가 어떠한 구조를 가지고 있는지에 대한 정보가 하나도 없기 때문
ex)  set에서 사용하는 find 함수는 O(log n), unordered_set의 경우 find 함수가 O(1)로 수행될 수도 있다. 그러나 알고리즘 라이브러리의 find 함수는 평범한 O(n)으로 처리된다.
==>  알고리즘 라이브러리의 find 함수를 사용할 경우 기본적으로 find 함수를 지원하지 않는 컨테이너에 사용해야 한다.

-  find 함수가 단순한 값을 받는다면 find_if 함수는 함수 객체를 인자로 받아서 그 결과가 참인 원소들을 찾는다.

-  any_of는 인자로 받은 범위 안의 모든 원소들 중에서 조건을 하나라도 충족하는 것이 있다면 true를 리턴한다.

=>  OR 연산과 비슷

-  all_of는 모든 원소들이 전부 조건을 충족해야 true를 리턴한다.

=>  AND 연산과 비슷

 

 

 

---

 

 

 

틀린 부분이나 이상한 부분이 있으면 댓글로 편하게 지적해주세요!

감사합니다!

 

 

참고

씹어먹는 C++ - <10 - 3. C++ STL - 알고리즘(algorithm)> (modoocode.com)