STL 프로그래밍을 더 재미있게 해주는 팁 모음 (1)

◾ STL?

컨테이너, 반복자, 알고리즘, 함수 객체로 구성된 라이브러리

 

 

항목 43 : 어설프게 손으로 작성한 루프보다는 알고리즘이 더 낫다

알고리즘은 대체로 반복자 2개를 매개변수로 받아서 범위로 작동한다.

범위 사이의 모든 객체를 훑는다는 점에서 루프와 일맥상통한다. 아니, 직접 루프를 사용해서 작성할 일들을 알고리즘이라는 이름 하에 정리해놓은 것들이다.

 

std::list<Widget> lw;
...
for (auto i = lw.begin(); i != lw.end(); ++i) i->redraw();
std::for_each(lw.begin(), lw.end(), std::mem_fun_ref(&Widget::redraw));
// 둘의 동작은 동일하다

직접 작성한 루프보다도 한번의 알고리즘 호출이 대체적으로 더 괜찮다.

그 이유는 효율, 정확성, 유지보수성의 측면에 있다.

 

◾ 효율

STL 제작자가 컨테이너의 구현 방식을 충분히 파악하고 있기 때문에 최적화가 잘 이루어져 있고, 컴퓨터 공학적인 알고리즘을 사용하기 때문에 웬만하면 직접 만드는것보다 훨씬 효율적이다. 또한 부가적으로 쓸데없는 계산량을 줄인다.

 

◾ 정확성

루프 안에서는 반복자를 계속 관리해주어야 한다. 증감, 무효화 여부 모두 신경써야 한다.

 

대체로 알고리즘이 간결하기 때문에 코드 가독성 측면에서 바라보면 알고리즘을 선택할 수밖에 없다.

또한 for, while, do를 보면 루프가 나온다는건 알지만 무엇을 하는지 대강 파악하려 해도 처음부터 살펴보아야 한다.

하지만 알고리즘은 이름에서부터 어떤일을 하는지 명시되기 때문에 대강 파악할 수 있다.

 

(이후 나오는 내용은 함수자를 만드는 과정이 나오는데 요즘은 람다식을 넘겨주면 된다.)

 

알고리즘이 이미 제공하고 있거나 제공하는 동작과 비슷한 일을 해야한다면 알고리즘을 쓰자.

 

 

항목 44 : 같은 이름을 가진 것이 있다면 일반 알고리즘 함수보다 멤버 함수가 더 낫다

알고리즘 함수와 이름이 같은 컨테이너 멤버 함수들이 몇개 있다.

이런 것들은 멤버 함수를 써주는게 낫다. 더 빠르고 해당 컨테이너에 더 잘 맞물려 있기 때문이다.

 

std::set<int> s; // 값이 100만개가 있다면?
...
auto i = s.find(727); // 로그 탐색시간. 최악40회, 평균20회
auto i = std::find(s.begin(), s.end(), 727); // 선형 탐색시간. 최악100만회, 평균50만회

예를들어 연관 컨테이너는 이진 탐색 트리로 구성되어 있어서 멤버 함수를 사용하면 빠른 탐색이 가능하다. 하지만 일반 알고리즘 함수를 사용하면 정렬 여부를 따지지 않기 때문에 선형 탐색을 시도하므로 더 오래걸린다.

 

또한 맵의 경우 멤버 함수는 key만 고려하여 동작할 뿐, value는 신경쓰지 않는다. 하지만 일반 알고리즘 함수는 동등성을 기준으로 페어에 들어있는 두 멤버를 모두 고려하여 동작한다.

 

list같은 경우는 remove처럼 아예 동작이 다르거나 sort처럼 아예 사용이 불가능할수 있다.

 

 

항목45 : count, find, binary_search, lower_bound, upper_bound, 그리고 equal_range를 제대로 파악해 두자

 

◾ 컨테이너가 정렬되지 않은 경우 : count, find

탐색에 선형 시간이 걸린다. 상등성으로 판단한다.

count : 찾는 값이 몇개나 있는가

find : 찾는 값이 어디에 있는가

 

◾ 컨테이너가 정렬된 경우 : binary_search, lower_bound, upper_bound, equal_range

탐색에 로그 시간이 걸린다. 동등성으로 판단한다.

binary_search : 찾는 값의 존재 여부. (위치 반환X)

lower_bound : 찾는 값이 존재하면 첫번째 원소의 위치, 존재하지 않으면 삽입될 적절한 위치 반환.

{1,3,5,7,9}에서 5를 탐색하면 5의 위치, 8을 탐색하면 9의 위치가 반환된다.

upper_bound : 찾는 값이 존재하면 마지막 원소의 다음 위치, 존재하지 않으면 삽입될 적절한 위치 반환.

{1,3,5,7,9}에서 5를 탐색하면 7의 위치, 8을 탐색하면 9의 위치가 반환된다.

equal_range : 찾는 값의 범위를 pair로 반환해준다. 각각 lower_bound, upper_bound의 반환값이다. 두 반복자 사이의 거리를 구하면 중복되는 원소의 개수를 알 수 있다.

 

erase와 lower_bound, upper_bound를 같이 사용하면 특정 값 이상 또는 초과되는 값의 범위를 모두 지울 수 있다.

 

 

연관 컨테이너는 상황이 약간 다르다. binary_search를 제외한 위의 알고리즘들을 멤버 함수로 제공해주고 find나 count의선형 시간을 걱정할 필요도 없다.

 

출처 : https://baboruri.tistory.com

 

 

항목 46 : 알고리즘의 매개 변수로는 함수 대신 함수 객체가 괜찮다

함수 포인터보다 함수 객체가 추상화 손실을 고려하더라도 성능이 더 좋다. 이유는 인라이닝 때문이다.

둘다 인라인으로 선언된 경우에 함수 객체는 인라이닝 되는 반면, 함수 포인터로 호출된 함수는 인라이닝 되지 않는다.

왜냐면 인라이닝은 컴파일 타임에 이루어져야 하는데 함수 포인터는 컴파일 타임에 확정을 지을 수 없기 때문이다.

 

효율과 상관없이 컴파일과 관련해서도 함수 객체를 사용해야 한다.

 

std::set<std::string> s;

std::transform(s.begin(), s.end(), std::ostream_iterator<std::string::size_type>(std::cout, "\n"),
    std::mem_fun_ref(&std::string::size)); // 될 것 같은데 컴파일이 안된다

/*  */

struct StringSize : public std::unary_function<std::string, std::string, std::string::size_type> {
    std::string::size_type operator()(const std::string& s) const { return s.size(); }
};

std::transform(s.begin(), s.end(), std::ostream_iterator<std::string::size_type>(std::cout, "\n"),
    StringSize()); // 컴파일이 잘 된다

 

이것뿐만 아니라 함수 객체는 미묘한 언어 문제도 막아준다.

 

/* 이항 함수 템플릿 average가 있을 때, */
template<typename FPType>
FPType average(FPType val1, FPType val2) { ... }

transform(..., average<typename iterator_traits<InputIter1>::value_type>);

템플릿 매개변수 타입으로 2개의 인자를 받는 이항 함수를 함수 포인터로 넘겨주는 경우 표현식이 모호해질수 있다.

무슨 얘기냐 하면 컴파일러는 단항 함수 템플릿 average가 존재할수도 있다고 판단해서 컴파일 오류를 발생시킨다.

 

template<typename FPType>
FPType average(FPType val) { ... }
// 이게 존재하면 어떤 템플릿을 인스턴스화 시켜야 하는지 모호해진다

함수 객체는 이런 걱정이 없으니 웬만하면 인자로 넘겨줄 때는 함수 객체를 사용하도록 하자.