게임 프로그래머

벡터는 처음부터 요소의 개수를 정해 주고 생성해도 됨

vector<int> v(10);

string은 int 매개 변수를 받는 생성자가 없기 때문에 컴파일되지 않음

string s(10);

error C2665: 'std::basic_string<char,std::char_traits<char>,std::allocator<char>>::basic_string'
: no overloaded function could convert all the argument types

string은 클래스가 아니라 using 타입

C++은 임의의 문자 특성(traits)을 가진 임의의 문자 타입을 임의의 할당자를 써서 메모리에 저장한 단위의 시퀀스를 문자열이라고 봄

C++에서 쓰이는 string처럼 동작하는 모든 객체는 basic_string 템플릿을 인스턴스화한 것

따라서 컴파일러 진단 메시지에 string 대신 basic_string이 언급됨

_EXPORT_STD using string  = basic_string<char, char_traits<char>, allocator<char>>;

할당자를 받는 생성자는 웬만하면 쓰지 말자

이 생성자는 해당 컨테이너와 동일한 타입인데 동등하지 않은(inequivalent) 할당자를 가진 상태로 되기 때문에 위험

class NiftyEmailProgram
{
public:
	void showEmailAddress(const string& nickname) const;

private:
	using NicknameMap = map<string, string>;
	NicknameMap nicknames;
};

void NiftyEmailProgram::showEmailAddress(const string& nickname) const
{
	NicknameMap::iterator iter = nicknames.find(nickname);
	if (iter != nicknames.end())
	{

	}
}

no suitable user-defined conversion from "std::_Tree<std::_Tmap_traits<std::string, std::string, std::less<std::string>, std::allocator<std::pair<const std::string, std::string>>, false>>::const_iterator"
(aka "std::_Tree_const_iterator<std::_Tree_val<std::conditional_t<true, std::_Tree_simple_types<std::pair<const std::string, std::string>>, std::_Tree_iter_types<std::pair<const std::string, std::string>,
unsigned long long, long long, std::pair<const std::string, std::string> *, const std::pair<const std::string, std::string> *, std::_Tree_node<std::pair<const std::string, std::string>, void *> *>>>>")
to "std::map<std::string, std::string, std::less<std::string>, std::allocator<std::pair<const std::string, std::string>>>::iterator"
(aka "std::conditional_t<false, std::_Tree_const_iterator<std::_Tree_val<std::conditional_t<true, std::_Tree_simple_types<std::pair<const std::string, std::string>>,
std::_Tree_iter_types<std::pair<const std::string, std::string>, unsigned long long, long long, std::pair<const std::string, std::string> *, const std::pair<const std::string, std::string> *, std::_Tree_node<std::pair<const std::string, std::string>, void *> *>>>>,
std::_Tree_iterator<std::_Tree_val<std::conditional_t<true, std::_Tree_simple_types<std::pair<const std::string, std::string>>, std::_Tree_iter_types<std::pair<const std::string, std::string>,
unsigned long long, long long, std::pair<const std::string, std::string> *, const std::pair<const std::string, std::string> *, std::_Tree_node<std::pair<const std::string, std::string>, void *> *>>>>>") exists

_Tree는 표준 연관 컨테이너를 구현하는 내부 템플릿

중간에 타입을 생략하고 보면 no suitable user-defined conversion from const_iterator to iterator이므로 iter를 map::find가 반환한 const_iterator로 초기화하는데 iterator로 변환하는데 실패했다는 의미

nicknames는 비상수 객체이고, find는 비상수 반복자를 반환하지만 showEmailAddress가 const 멤버 함수이므로 nicknames가 상수 객체가 되기 때문에 find가 const_iterator를 반환

따라서 iter를 const_iterator로 변경하거나 함수의 const를 제거해야 함

컴파일러 진단 메시지에서 긴 템플릿 이름들을 축약하는 연습을 해야 의미를 이해할 수 있음

STL의 컴파일러 메시지를 이해하는 힌트

vector와 string의 경우 반복자와 포인터가 똑같기 때문에 iterator를 가지고 실수했다면 컴파일러 진단 메시지는 포인터 타입을 언급할 가능성이 매우 높음

예를 들어, 소스 코드에 vector<double>::iterator가 있다면 컴파일러 메시지는 double* 라고 함

back_insert_iterator, front_insert_iterator, insert_iterator 등을 언급하는 메시지는 대부분 back_inserter, front_inserter, inserter를 호출할 때 실수했다는 의미

출력 반복자는 대입 연산자의 내부에서 출력 혹은 삽입 동작을 취하기 때문에 이런 반복자에 대해 실수했을 때에는 대입 연산자를 언급

STL 알고리즘의 내부가 잘못 되었다는 에러 메시지라면 알고리즘과 함께 사용한 타입에 문제가 있는 의미

예를 들면 알고리즘에 잘못된 반복자를 전달하는 상황

// 임의 접근 반복자를 요구하는 알고리즘에 양방향 반복자를 넣는 상황
list<int>::iterator iter1, iter2;
sort(iter1, iter2);

y보다 크거나 같은 값 중 가장 마지막 값부터 x보다 작은 값을 지우고 싶다고 가정

v.erase(remove_if(find_if(v.rbegin(), v.rend(), [y](int num)
                                                {
                                                    return num >= y;
                                                }).base(),
                    v.end(), [x](int num)
                    {
                        return num < x;    
                    }),
        v.end());

이러한 코드가 쓰기 전용 코드라고 불리는 이유는 쓰기에는 쉽지만 읽고 이해하는데 어렵기 때문

쓰기 전용 코드가 안좋은 이유는 중첩된 함수가 많아 다른 사람이 이해하기 어려움

n이 함수의 출현 순서 번호라고 하고 간단하게 fn으로 표시하면
v.f1(f2(f3(v.f4(), v.f5(), f6()).f7(), v.f8(), f9()), v.f10());

함수들을 분해하여 이해하는데 시간이 걸림

따라서 함수를 분해하여 작성하고, 주석을 사용하자

// rangeBegin을 y보다 크거나 같은 요소 중 가장 마지막 요소로 초기화, 만약 이런 요소가 없다면 v.begin()으로 초기화됨
vector<int>::iterator rangeBegin = find_if(v.rbegin(), v.rend(), [y](int num)
                                                                {
                                                                    return num >= y;
                                                                }).base();
                                                                
// rangeBegin부터 end까지 x보다 작은 값을 모두 지움
v.erase(remove_if(rangeBegin, v.end(), [x](int num)
                                        {
                                            return num < x;    
                                        }),
        v.end());

쓰기 전용 코드의 여부는 코드를 읽는 사람에 달려 있음

주변에 이러한 코드를 사용하는 것이 관례라면 계속 사용하지만 그렇지 않다면 코드를 쪼개고, 주석을 사용해야 함

읽기 힘든 코드는 유지보수에 어렵고, 소프트웨어는 개발보다 유지보수에 더 많은 시간이 들어가므로 읽기 쉬운 코드를 작성해야 함

vector<double> v;

// 함수 객체
sort(v.begin(), v.end(), greater<double>());

inline bool doubleGreater(double d1, double d2)
{
    return d1 > d2;
}

// 함수
sort(v.begin(), v.end(), doubleGreater);

doubleGreater 함수를 전달하는 것보다 greater<double> 함수 객체를 쓴 것이 일반적으로 더 빠름

백 만 개의 double을 가진 벡터를 sort의 실행 시간을 측정한 결과 함수 객체를 사용한 sort가 20ms 빠름

함수 객체가 빠른 이유는 인라이닝 때문

함수 객체의 operator()가  inline으로 선언되어 있고, 정의가 있다면 대부분의 컴파일러는 알고리즘의 템플릿 인스턴스화 과정에서 인라인으로 만들기 때문에 함수 호출이 없고, 최적화까지 적용됨

함수를 전달할 경우 함수를 함수 포인터로 변경하고 포인터를 통한 간접 함수 호출 비용이 발생하고 인라인이 되지 않기 때문에 느림

(컴파일러가 함수 포인터로 호출하는 함수는 inline으로 선언됐더라도 인라인으로 만들지 않음)

template<typename FPType>
FPType average(FPType val1, FPType val2)
{
    return (val1 + val2) / 2;
}

template<typename InputIter1, typename InputIter2>
void writeAverages(InputIter1 begin1, InputIter1 end1, InputIter2 begin2, ostream& s)
{
    transform(begin1, end1, begin2, ostream_iterator<typename iterator_traits<InputIter1>::value_type>(s, "\n"),
    average<typename iterator_traits<InputIter1>::value_type>);
}

템플릿 함수는 포인터로 변환할 수 없기 때문에 전달할 수 없어 컴파일 에러 발생하기 때문에 함수 객체를 사용해야 해결됨

만약 탐색할 범위가 정렬됐다면 binary_search, lower_bound, upper_bound, eqaul_range 등의 알고리즘으로 로그 시간에 수행

정렬되지 않았다면 선형 시간의 알고리즘인 count, count_if, find, find_if만 사용해야 함

정렬되지 않은 컨테이너 탐색 알고리즘

상등성으로 탐색

count

찾는 값의 개수를 반환

count != 0을 직접 쓰기도 하지만 내부적으로 양수를 true, 0을 false로 해석하는 것이 보편적

if (count(lw.begin(), lw.end(), w))
    
if (count(lw.begin(), lw.end(), w) != 0)

find

찾는 값의 위치(반복자)를 반환

값을 못 찾았을 때 컨테이너의 end 반복자를 반환하기 때문에 end 반복자와 비교해야 함

if (find(lw.begin(), lw.end(), w) != lw.end())

값의 존재 여부를 점검하는 목적으로는 count를 사용하는 코드가 더 간단하지만 탐색이 성공했을 때 효율은 find가 더 좋음

find는 탐색이 성공했을 때 바로 끝내지만 count는 끝까지 탐색하기 때문

검색한 값의 첫 번째 객체를 알고 싶은 경우 find의 반환값을 사용

list<Widget>::iterator iter = find(lw.begin(), lw.end(), w);
if( iter != lw.end())

정렬된 컨테이너 탐색 알고리즘

정렬되지 않은 컨테이너가 정렬되면 두 개의 값을 비교할 때 사용하던 상등성 기준이 동등성으로 바뀜

같은 값이 인접해 있으므로 동등성만 비교해도 충분하기 때문

binary_search

값이 있는지 없는지 bool 값만 반환하기 때문에 어떤 값이 있는지 탐색할 때 제일 좋음

if (binary_search(vw.begin(), vw.end(), w))

lower_bound

찾으려는 key 값보다 같거나 큰 key가 처음 등장하는 위치를 반환

반환하는 반복자가 원하는 값이 아닐 수 있으므로 비교 구문도 필요함

vector<Widget>::iterator iter = lower_bound(vw.begin(), vw.end(), w);
if( iter != vw.end() && *iter == w )

lower_bound를 통해 동등성 검사로 탐색하고, operator==로 상등성 검사를 하기 때문에 대부분은 동일한 결과가 나오지만 상등성과 동등성이 다를 경우 잘못 동작함

Timestamp::operator<가 시간 순서대로 비교한다는 가정

ageLimit보다 오래된 타임 스탬프를 지우는 예제

Timestamp ageLimit;
vector<Timestamp> vt;

vt.erase(vt.begin(), lower_bound(vt.begin(), vt.end(), ageLimit));

upper_bound

찾으려는 key 값보다 큰 key가 처음 등장하는 위치를 반환

정렬된 범위에 객체를 삽입할 때 정렬 순서를 유지할 때 유용

(동등한 값이 삽입된 순서대로 저장됨)

Person newPerson;
list<Person> lp;

lp.insert(upper_bound(lp.begin(), lp.end(), newPerson), newPerson);

upper_bound를 list에 사용하고 있으므로 로그 시간이 아닌 선형 시간에 동작

eqaul_range

원하는 값이 어디에 있는지 탐색할 때 사용

반복자 쌍으로 구성된 pair 객체를 반환하는데, 첫 번째 반복자는 lower_bound의 반환값이고, 두 번째 반복자는 upper_bound가 반환하는 반환값과 같음

두 반복자가 같다면 원하는 값을 찾지 못했다는 것을 의미

auto IterPair = equal_range(vw.begin(), vw.end(), w);
if(IterPair.first != IterPair.second)

이 코드는 동등성만을 사용하기 때문에 모든 경우에 정확히 동작

두 반복자 사이의 거리를 구하면 찾는 값과 동등한 값을 가진 객체의 개수를 구할 수 있음

distance(IterPair.first, IterPair.second);

따라서 equal_range는 find와 count 동작을 동시에 해줌

표준 연관 컨테이너에 사용할 때에는 알고리즘이 아닌 멤버 함수를 사용하는 것이 효율이 더 좋음

(예외로 binary_serach는 비슷한 알고리즘의 멤버 함수가 없음)

정리

multiset, multimap에서 어떤 값이 있는지 확인할 때에는 최악의 경우 모든 객체를 일일이 찾아야 하므로 count보다 find가 일반적으로 좋음

컨테이너에는 STL 알고리즘과 같은 이름을 가진 멤버 함수가 있음

연관 컨테이너는 count, find, lower_bound, upper_bound, equal_range

list는 remove, remove_if, unique, sort, merge, reserve

알고리즘보다 멤버 함수가 특정 컨테이너에 최적화되어있음

100만개의 정수를 가진 set이 있다고 가정

set<int> s;

set<int>::iterator iter = s.find(727);
set<int>::iterator iter2 = find(s.begin(), s.end(), 727);

find 멤버 함수는 로그 시간에 실행되어 최악의 경우(2xlog2(n)) 40번의 비교

find 알고리즘 함수는 선형 시간에 실행되어 최악의 경우 100만 번의 비교

STL 알고리즘은 상등성을 기준으로 삼지만 연관 컨테이너는 동등성을 기준으로 삼기 때문에 동작이 다를 수 있음

map, multimap의 각 멤버 함수는 pair의 키 객체만 비교하지만 알고리즘 함수는 pair의 값 객체까지 비교하기 때문에 동작이 다름

list의 멤버 함수는 객체를 복사하지 않고 포인터를 조작하지만 알고리즘 함수는 객체를 복사함

알고리즘 함수는 알고리즘적 복잡도는 동일하지만 복사 비용이 발생하여 멤버 함수가 나은 수행 성능을 제공

list 멤버 함수는 알고리즘과 다르게 동작하는 경우도 있어 기억해야 함

list 외 시퀀스 컨테이너의 객체를 제거하려면 remove, remove_if, unique와 erase를 함께 사용해야 하지만 list는 멤버 함수에서 객체를 제거해줌

sort 알고리즘은 임의 접근 반복자만 사용 가능하지만 list는 양방향 반복자이므로 사용 불가능하여 멤버 함수의 sort를 사용해야 함

merge 알고리즘은 원본 컨테이너를 수정하지 않지만 llist는 원본 컨테이너를 수정하여 새로운 컨테이너로 이동함

일반적으로 알고리즘은 동작을 실행할 객체 범위의 시작과 끝을 가리키는 반복자를 받음

따라서 알고리즘은 매개 변수로 지정된 범위 안에 있는 모든 객체를 순회해야 하므로 루프를 수행함

루프를 통해 Widget::redraw를 실행한다고 가정하자

list<Widget> lw;
const list<Widget>::iterator endIter = lw.end();
for(list<Widget>::iterator iter = lw.begin(); iter != endIter; ++iter)
{
    iter->redraw();
}

for_each 알고리즘으로 똑같이 구현할 수 있음

for_each(v.begin(), v.end(), [](Widget& widget) { widget.redraw(); });

루프보다 for_each 한 번의 알고리즘 호출이 일반적으로 좋을 수 있음

효율

라이브러리 제작자가 컨테이너의 구현 방식을 충분히 파악하고 있기 때문에 순회 코드를 최적화함

예를 들면 deque는 하나 이상의 고정 크기 배열에 저장되므로 반복자보다 포인터를 통해 순회하는 것이 빠르다는 것을 라이브러리 제작자는 알고 있기 때문에 최적화가 이루어짐

하지만 라이브러리 사용자는 최적화 내용을 모르기 때문에 루프보다 알고리즘의 효율이 더 좋을 수 있음

컴퓨터 공학적인 알고리즘을 사용하여 보통 프로그래머보다 높은 수준의 효율적인 알고리즘을 제공

정확성

반복자가 유효해야 하고, 원하는 위치를 가리켜야 함

프로그래머가 반복자를 잘못 조작할 수 있고 무효화될 수 있음

배열의 모든 요소마다 41을 더한 후 deque의 앞에 삽입한다고 가정하자

계속 앞에 삽입하므로 배열의 순서가 반대되는 상황이 발생

double data[maxNumDoubles];
deque<double> d;

for(size_t index = 0; index < maxNumDoubles; ++index)
{
    d.insert(d.begin(), data[i] + 41);
}

순서가 바뀌는 상황은 수정했지만 insert가 호출되면서 모든 반복자가 무효화됨

deque<double>::iterator insertIter = d.begin();

for(size_t index = 0; index < maxNumDoubles; ++index)
{
    d.insert(insertIter++, data[i] + 41);
}

반복자 무효화 수정

deque<double>::iterator insertIter = d.begin();

for(size_t index = 0; index < maxNumDoubles; ++index)
{
    insertIter = d.insert(insertIter, data[i] + 41);
    ++insertIter;
}

알고리즘으로 사용하면 무효화 걱정이 필요 없음

transform(data, data + maxNumDoubles, inserter(d, d.begin()), [](double a) { return a + 41; });

유지보수성

직접 만든 루프보다 간단한 코드로 생산될 가능성이 높음

알고리즘의 함수 이름이 각각의 동작을 잘 정의되어 있어서 충분히 이해할 수 있는 수준이므로 명확한 의미를 전달

만약 루프로는 간단한 작업인데, 알고리즘으로는 복잡하다면 루프가 더 좋음