EFFECTIVE STL 간단 요약

----------------------------------------------------------------------------------------------------
[EFFECTIVE STL]
----------------------------------------------------------------------------------------------------
[1 : Containers]

[ITEM 1 : Choose your containers with care]

standard STL sequence containers : vector string, dequeue, list
standard STL associative containers : set, multiset, map, and multimap



----------------------------------------------------------------------------------------------------
[2 : Vector and string]


vector , string 가지고 모든 array 관련 application 대체 가능

1. vector, string의 performance 향상 방법
2. string implemenation의 다양성
[ITEM 13 : Prefer vector and string to dynamically allocated arrays]

[ITEM 16 : Know how to pass vector and string data to legacy APIs]


vector v : &v[0] first element에 대한 포인터

void doSomething(const int * plnts, size_t numInts);

// EMPTY 체크 해야함
if(!v.empty()) doSomething(&v[0], v.size());

char * --> string 으로 대체
void doSomething(const char *p)

string s
// string 이 length 0 이어도 문제 없이 동작 --> null charactor 에 대한 포인터 리턴
// string 은 null character 또한 가질수 있다.
doSomething(s.c_str());


[주의]

시나리오 1 : C API 로 부터 array 사이즈 만큼 초기화 시킨다.

size_t fillArray(double *pArray, size_t arraySize)

vector vd(maxNumDoubles);
vd.resize(fillArray(&vd[0], vd.size());

vector 인 경우는 문제 없는 시나리오 (vector와 array memory layout 은 동일)


시나리오 2 : 시나리오 1인데 string을 초기화 시킨다.
--> vector를 가지고 구현해야만 가능


size_t fillString(char *pArray, size_t arraySize);

vector vc(maxNumChars);

// ------------> TERRABLE CODE
// string s;
//size_t charWritten = fillString(s.c_str(), maxNumChars);

size_t charWritten = fillString(&vc[0], vc.size());

string s(vc.begin(), vc.begin() + charWritten);

결론 : C API 사용시 vector에 data를 넣고 해당 STL container에 copy 하는 순서를 따라야함.




void doSomething(const int * plnts, size_t numInts); // C API

set intSet;
vector v(intSet.begin(), intSet.end());
...
vector v(intSet.begin(), intSet.end());

// EMPTY 체크 해야함
if(!v.empty()) doSomething(&v[0], v.size());











string s : s.c_str()

but, certain restriction








----------------------------------------------------------------------------------------------------
[3 : Associative Container]

[ITEM 19 : Understand the difference between equality and equivalence]


EQUQLITY : find algorithm (operator== 사용)

EQUIVALENCE : set::insert (operator< 사용) set ciss;
set::iterator iter;
bool inserted;

boost::tie(iter,inserted) = ciss.insert("aired");

BOOST_TEST(inserted == true);

boost::tie(iter,inserted) = ciss.insert("AIRED");
BOOST_TEST(inserted == false);


// EQUIVALCE 연산 : CIStringCompare comparation functor 에 의해 equivalent 하나 equal 은 아님
// ITEM44 참고
BOOST_TEST(ciss.find("aired") != ciss.end());

// find algorithm 은 equality 연산 : operator==
// ASSERT FAIL
BOOST_TEST(find(ciss.begin(), ciss.end(),"Aired") != ciss.end());


왜 standard associative container는 equivalence 기반인가? ( 답 ?)

TWO Comparison Function

1 : sorted order 유지 : default less comparison function
Equivalence를 only one comparision function 에서 정의함
2 : Equility 에 대한 default comparision function 존재(equal_to)
그러나 STL 에서는 사용하지 않고 operator== 정의해서 non-member find 알고리즘같은경우도 고려함


[ITEM 20 : Specify comparision types for associative containers of pointers]

* POINTER VALUE 로 sorting 되어있는 associative container 구현
1 : container 의 comparision type을 specify.
2 : deference 작업 필수 (Template으로 구현)

struct DereferenceLess {

template
bool operator()(PtrType pT1, PtrType pT2) const
{
return *pT1 < *pT2; } }; void print(const string *ps){ cout << *ps <<> ssp2;
ssp2.insert(new string("AIRED1"));
ssp2.insert(new string("AIRED2"));
for_each(ssp2.begin(), ssp2.end(), print);

[ITEM21 : Always have comparision functions return false for equal values]

// ITEM21
// WRONG USAGE
set > s;
set >::iterator iter2;

bool inserted2;
boost::tie(iter2,inserted2) = s.insert(10);
BOOST_TEST(inserted2 == true);

// equivalce 가 실패 해서 INSERT 된다.
// !(10A <= 10B) &&amp;amp;amp;amp;amp; !(10B <=10A) // !(true) && !(true) // false && false boost::tie(iter2,inserted2) = s.insert(10); [ITEM 22 : Avoid in-place key modification in set and multiset] [ITEM 23 : Consider replacing associative containers with sorted vectors] set, multiset, map, multimap is OK , 그러나 logrithmic-time lookup speed 능가 하는 constant-time lookup speed 필요 lookup speed 가 중요하다면 non standard hashed container 사용(ITEM25) standard associative container 는 balanced binary search tree로 구현 되어 있다. --> insertion, erase, lookup combination 에 대한 OPTIMIZATION

세가지 DataSturcture 에 대한 사용
1 . Setup :
2 .
3 .

Sorted Vector
- lookup algorithm : binary_search, lower_bound, equal_range

binary serarch tree 를 binary searching 하는것 보다 sorted vector내에서 binary_searching 이 빠른 이유?
1 : size
2 : locality of reference

associative container 의 각 element 당 left, right child node 에 대한 포인터 스페이스 OVERHEAD

vector space overhead 무시 : 3 pointer + 2 pointer + 1 int

vector 는 swap trick 통해 extra space 제거 가능 , 그러나 이자체도 의미가 없다. lookup 동안에는
mermory referencing 이 없슴

morory page 당 몇개 들어갈지 계산하면?

12byte 클래스 , pointer 4byte
4K page 내 : vector(341 entry) , associative container(170 entry)

associative container 사용시 small memory page set 을 클러스터링 할 수 있는 container allocator 구현해야함.
--> tree node 사이에서 locality fo reference 추가 시킴

Sorted Vector : insertion & erasures 에 대한 오버헤드가 큼 , 그렇다 하더라도 associative container
비하면 미비한 오버헤드
insert new element : one 씩 이동 , expensive , reallocate 발생시는 더 큰 오버헤드

map 은 sorting 을 위해서 element 의 key 부분만 필요
pair 부분만

--> pair : const 없다. vector 는 element 의 value 들이 move 되면서 assing 됨

[ITEM 24 : Choose carefully between map::operator[] and map::insert when efficiency is import]

element 존재시 ? operator[] : insert

[ITEM 25 : Familiarize yourself with the nonstandard hashed containers]



----------------------------------------------------------------------------------------------------
[4 : Iterators]


----------------------------------------------------------------------------------------------------
[5 : Algorithms]

[ITEM 30: Make sure destination ranges are big enough]

----------------------------------------------------------------------------------------------------
[6 : Functors, Functor Classes, Functions, etc]


functors : function and function-like object

find_if, for_each ,,, 등등 많은 알고리즘들이 functor를 이용해 control을 제어 한다.

[ITEM38: design functor classes for pass-by-value]
STL function objects are passed by value(i.e., copied) when passed to and from functions


template
Function for_each(InputIterator first, InputIterator last, Function f);

Function object 사용시 2가지 전제 조건
1: function object 자체가 small 해야함
--> pass by value 에 대한 overhead

2: monomorphic 해야함(not polymorphic) --> no virtual function
--> base class, derive class 간 pass-by-value 시 slicing problem 발생
--> Effect C++ ITEM22 , STL ITEM3


but polymorphic functor 자체를 사실상 피하기는 불가능
보통 function object 자체가 크고 polymorphic

bridge pattern으로 해결가능(handle-body)

[ITEM39 : Make predicates pure functions]

predicate : return boool 형태의 function( implicitly bool conversion 도 가능)

predicate 예 : standard associative containers 의 comparison functions , find_if 및 sort
알고리즘에 parameter 로서 패스 된다.

pure function : return value가 parameter 에 의해서만 변하는 function

predicate class : operator() function 이 predicate 인 functor 클래스

중요 : predicate function 들을 pure function 을 만족해야함.

functor 클래스는 1개의 operator() function 을 가짐

unary_function binary_function 을 상속받는 이유
--> adaptable function object를 만들기 위함
--> not1, bind2nd 자체도 adaptable function object와 같이 동작


---------------------------------------------------------------------------------------------------------
[7 : Programming with the STL]

ITEM 43 : Prefer algorithm calls to hand-written loops

vector<u> vector;
for(vector<u>::iterator i = vector.begin(); i!= vector.end(); ++i)
i->redraw();

for_each(vector.begin(), vector.end(), mem_fun(&U::redraw));

1. Efficiency
2. Correctness
3. Maintainablility


ITEM 44 : Prefer member functions to algorithms with the same names
1. FAST
2. container 에 맞게 integrating.


associative container : count, find, lower_bound, upper_bound, equal_range

list container : remove, remove_if, unique, sort, merge, reverse

ITEM 45 : Distinguish among cuont, find, binary_search, lower_bound, upper_bound, and equal_range

p 200 표 참고


-----------------------------------------------------------------------------------------------