[effective STL] 항목 30 : 알고리즘의 데이터 기록 범위는 충분히 크게 잡자.

2016. 2. 20. 22:02프로그래밍/Effective STL

728x90
728x90

핵심

알고리즘을 쓰기 전에 내부 동작 구조를 알고 컨테이너를 결정해주고,

재할당이 최대한 일어나지 않게 범위를 잘 잡아야 한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <list>
#include <string>
 
using namespace std;
 
int transmogrify(int x) { return x*x; }
 
template <class T>
void printVector(T SomeContainer, string str) {
    cout<<"=============="<<str<<"=============="<<endl;
    for each (int i  in SomeContainer) { cout<< i << endl; } 
    cout<<endl;
}
 
int main(int argc, const char* argv[])
{
    vector<int> values;
 
    for (int i = 0; i < 5; i++) {
        values.push_back(i);
    }
 
    vector<int> results1;
 
    // runtime error
    // transform(values.begin(), values.end(), results.end(), transmogrify);
 
    transform(values.begin(), values.end(), back_inserter(results1), transmogrify);
    // back_inserter
    // container supported push_back function. vector, string, deque, list and so on.
    
    printVector(results1, "results1");
 
    // if list then
    list<int> results2;
    transform(values.begin(), values.end(), front_inserter(results2), transmogrify);
 
    printVector(results2, "results2");
 
    // if front input
    list<int> results3;
    transform(values.rbegin(), values.rend(), front_inserter(results3), transmogrify);
 
    printVector(results3, "resulrs3");
 
    // if center input
    // use reserve
    results1.reserve(results1.size() + values.size());
 
    transform(values.begin(), values.end(), 
        inserter(results1, results1.begin() + (results1.size() / 2)), transmogrify);
 
    printVector(results1, "results1 center input");
 
    // overlap
    // use clear
    results1.clear();
    results1.reserve(values.size());
 
    transform(values.begin(), values.end(), back_inserter(results1), transmogrify);
 
    printVector(results1, "results1 overlap");    
 
    return 0;
}
cs


back_inserter와 front_inserter는 iterator 헤더에 있다.

back_inserter는 push_back이 제공되는 컨테이너여야 한다. 벡터라던가 스트링이라던가 덱이라던가..

그래서 적당한 컨테이너에 적당한 방법으로 호출 해주어야 한다는 것./


그리고 results 들을 미리 reserve를 해주지 않으면

알고리즘이 돌며 내부에서 계속 재할당을 하게 된다.


1
2
3
4
5
6
7
8
9
...
 
 
results1.reserve(results1.size() + values.size());
 
...
 
results1.reserve(results1.size() + results1.clear();    
results1.reserve(values.size());
cs


뭐 이런식으로 reserve로 미리 공간을 할당하여 사용해야 한다.

transform 알고리즘이 얼마나 메모리를 쓸지 미리 예상하고 할당하고 사용하자는 것이다.

728x90
반응형