U E D R , A S I H C RSS

EffectiveSTL/Container

  • STL을 구성하는 핵심 요소에는 여러 가지가 있다.(Iterator, Generic Algorithm, Container 등등). 역시 가장 핵심적이고, 조금만 알아도 쓸수 있고, 편하게 쓸수 있는 것은 Container다. Container는 Vector, List, Deque 과 같이 데이터를 담는 그릇과 같은 Object라고 보면 된다.
  • STL의 Container들의 장점이라고 한다면, 역시 유연성, 메모리 관리 알아서 하기, 자신이 알아서 늘었다 즐었다 하기 등등이 있겠다. 또한 인터페이스가 이거나 저거나 비슷비슷해서 하나만 공부하면, 쉽게 다른것도 쓸수 있다는 것도 또 하나의 장점이 될수 있겠다.
  • 큰 1장 Containers에서는 상황에 맞는 적절한 Container 고르는 법, 효율성 극대화 하기 등등을 다룬다.

Contents

1. Item1. Choose your containers with care.
1.1. STL이 지원하는 Containers
1.2. vector, deque, list 고르는 팁
1.3. Contiguous-memory Containers & Node-based Containers
1.4. STL Container 고르는 팁
2. Item2. Beware the illusion of container-independant code.
2.1. 완벽한 Container 독립적인 코드 작성은 불가능?
2.2. 그나마 고치기 쉽게 하는 팁들
3. Item3. Make copying cheap and correct for objects in containers.
3.1. STL way
3.2. 상속받은 객체를 넣을때의 문제점
3.3. 해결책
3.4. Why copy?
4. Item4. Call empty instead of checking size() against zero.
5. Item5. Prefer range member functions to their single-element counterparts.
5.1. a 컨테이너에 있는 내용의 뒷부분의 절반을 b라는 벡터 컨테이너에 넣고 싶다면, 어떻게 해야할까?
6. Item6. Be alery for c++'s most vexing parse
6.1. 문제점?
6.2. 예제 : ints.dat 에 저장되어 있는 정수들을 읽어서 list<int> data에 쓰는 작업을 한다.
6.3. 해결책
6.4. 잡담
7. Item7. When using containers of newed pointers, remember to delete the pointers before the container is destroyed
7.1. 서론
7.2. 예제
7.3. 보완법 1(class for function object)
7.4. 보완법 2(Smart Pointer)
8. Item8. Never create containers of auto_ptrs.
9. Item9. Choose carefully among erasing options.
9.1. 어떤 컨테이너가 int값들을 담고 있다고 하자. 거기서 1982 라는 숫자를 몽땅 지워주고 싶다면?
9.2. 조건 검사해서 몽땅 지워주기
9.2.1. 쉽게 할수 있는 컨테이너들
9.2.2. Associative Container 일때
9.3. 잡담
10. Item10. Be aware of allocator conventions and restrictions.
11. Item11. Understand the legitimte uses of custom allocators.
12. Item12. Have realistic expectations about the thread safety of STL containers.


1. Item1. Choose your containers with care.

1.1. STL이 지원하는 Containers

  • Sequence Containers - vector, deque, list, string( vector<char> ) 등등
  • Associative Containers - set, multiset, map, multimap 등등
  • 그 외에 Non Standard라고 써있는게 있긴 한데, 잘 안쓰는 것 같다. 혹시라도 나중에 중요성이 부각되면 다시 봐야겠다. 딴게 급하니 일단.. AfterCheck
  • vector가 좋다고 써있다. 잘 쓰자. 가끔가다 시간,저장공간 등등에 있어서 Associative Containers를 압도할때도 있다고 한다.
    • vector 는 Sequence Container 니까 보통 Associative Container 들(주로 Map)보다 메모리낭비가 덜함. 그대신 하나 단위 검색을 할때에는 Associative Container 들이 더 빠른 경우가 있음. (예를 들어 전화번호들을 저장한 container 에서 024878113 을 찾는다면.? map 의 경우는 바로 해쉬함수를 이용, 한큐에 찾지만, Sequence Container 들의 경우 처음부터 순차적으로 좌악 검색하겠지.) --1002

1.2. vector, deque, list 고르는 팁

  • vector는 무난하게 쓰고 싶을때
  • list는 중간에서 삽입, 삭제가 자주 일어날때
  • deque는 종단점(시작과 끝)에서 삽입, 삭제가 자주 일어날때

1.3. Contiguous-memory Containers & Node-based Containers

  • 전자는 배열을 기반으로 하는 Container(즉, 동적 메모리 할당을 할때 할당된 메모리들이 연속적이 된다), 후자는 노드를 기반으로 하는 Container(노드의 경우는 반드시 연속적인 메모리가 아닐 수 있다.)다. 노드가 뭔지는 링크드 리스트를 짜보면 알게 된다.
  • 전자에는 vector, string, deque 등이 있다. 뭔가 또 복잡한 말이 있긴 한데 그냥 넘어가자. 대충 insert, delete가 일어나면 기존의 원소가 이동한다는 말 같다.
  • 후자에는 list 등이 있다. 노드는 그냥 포인터만 바꿔 주면 insert, delete가 자유자재로 된다는거 다 알것이다.

1.4. STL Container 고르는 팁

  • 양끝에서 insert, delete 하려면? Associative Containers는 쓰면 안된다.
  • Random Access Iterator(임의 접근 반복자)가 필요하다면, vector, deque, string 써야 한다. (rope란것도 있네), Bidirectional Iterator(양방향 반복자)가 필요하다면, slist는 쓰면 안된다.(당연하겠지) Hashed Containers 또 쓰지 말랜다.
  • Insert, Delete 할때 원소의 인덱스 위치가 변하면 안된다? 그러면 Contiguous-memory Containers는 쓰면 안된다. (해당 원소의 인덱스 위치가 변한다.)
  • Search 속도가 중요하다면 Hashed Containers, Sorted Vector, Associative Containers를 쓴다. (바로 인덱스로 접근, 상수 검색속도)
  • Insert, Delete를 효율적으로 쓰려면, Node Based Containers를 쓰자.
  • Iterator, Pointer, Reference 갱신을 최소화 하려면 Node Based Containers를 쓴다.



2. Item2. Beware the illusion of container-independant code.

2.1. 완벽한 Container 독립적인 코드 작성은 불가능?

  • Standard Contiguois-memory Container들은 임의접근 연산자 []을 지원하지만, 다른건 지원하지 않는다.
  • Standard Node-based Container들은 양방향 반복자(bidirectional Iterator)를 지원한다.
  • 결국 이 코드에서 이 컨테이너에서 작동하는 함수를 썼는데, 컨테이너를 같은 계열의 것으로 바꾸면 좋겠지만, 성향이 다른걸로 바꾸면--; 많이 고쳐야 할것이다.
  • 각각의 컨테이너는 장점과 단점을 가지고 있다. 고르는 능력을 기르자.
    STL Tutorial and Refereince 를 보면, 일부러 해당 Container 에게 최적화된 메소드들만 지원한다고 써있었던 기억. 예를 든다면, Vector 의 경우 push_front 같은 것이 없다. (만일 vector에 push_front 를 한다면? push_front 될때마다 매번 기존의 원소들 위치가 바뀐다.) --1002

2.2. 그나마 고치기 쉽게 하는 팁들

  • typedef을 쓰자.

~cpp 
vector<Type>::itarator // typedef vector<Type>::iterator VTIT 이런식으로 바꿀수 있다. 앞으로는 저렇게 길게 쓰지 않고도 VIIT 이렇게 쓸수 있다.
  • Encapsulization을 잘 하자. 바뀌는 것에 대한 충격이 줄어들 것이다.



3. Item3. Make copying cheap and correct for objects in containers.

3.1. STL way

  • 컨테이너에 넣을 때나 뺄 때, 복사를 한다.
  • 컨테이너에 Object를 넣을때에는, 그 Object의 복사 생성자(const reference)와, 대입 연산자를 재정의(const reference) 해주자. 안그러면 복사로 인한 엄청난 낭비를 보게 될것이다.

3.2. 상속받은 객체를 넣을때의 문제점

  • Slicing에러

~cpp 
vector<Widget> vw;

class SpecialWidget : public Widget ...

SpecialWidget sw;

vw.push_back(sw) // 어떻게 될까. 복사되면서 SpecialWidget만의 특수성은 제거되고, Widget의 특성만 남게 된다.
  • 해결책으론 가상함수 등등이 있다. 하지만 더 좋은 방법이 있다.

3.3. 해결책

  • 컨테이너에 값을 넣지 말고, 포인터를 넣는 것이다.

~cpp 
vector<Widget*> vw;
vw.push_back(new SpecialWidget); // 잘된다.
  • 하지만 역시 내가 delete해줘야 한다는 단점이 있다. 대안으로 smart pointers라는게 있다.(이게 뭘까)
    MoreEffectiveC++/Techniques1of3 의 Item 28 을 봐라. 영문을 보는것이 더 좋을것이다. MoreEffectiveC++ 의 전자책과 아날로그 모두다 소장하고 있으니 필요하면 말하고, 나도 이 책 정리 할려고 했는데, 참여하도록 노력하마 --상민

3.4. Why copy?

  • 불필요한 객체의 복사를 막기 위해 디자인 되어있다.(잘 이해가 안간다.)
  • 내가 요구할때만 그만큼 많은 공간을 할당한다.



4. Item4. Call empty instead of checking size() against zero.

  • 컨테이너에 하나도 안들었다는것을 가정할때 size() == 0 이것보다 empty() 가 더 좋다고 한다.
  • empty()는 상수 시간에 수행이 가능하고, size()는 선형 시간에 수행이 가능하다.
  • 고로 empty() 쓰자.



5. Item5. Prefer range member functions to their single-element counterparts.

  • 범위 가지고 노는 메소드가 하나씩 가지고 노는 메소드보다 우월하다. 수행시간의 차이가 있는듯하다.

5.1. a 컨테이너에 있는 내용의 뒷부분의 절반을 b라는 벡터 컨테이너에 넣고 싶다면, 어떻게 해야할까?

  • STL에 익숙하지 않다면 아마도 다음과 같이 할 것이다.

~cpp 
// 명시적인 반복문을 쓴다.
vector<Object> a,b;

b.clear();

for(vector<Object>::const_itarator VWCI = a.begin() + a.size()/2 ; VWCI != a.end() ; ++VWCI)
	b.push_back(*VWCI)


  • 약간 익숙한 사람이라면..

~cpp 
// copy 알고리즘을 이용한다.
vector<Object> a,b;

b.clear();
copy( a.begin() + a.size() / 2, a.end(), back_inserter(b)) ;

  • 어느 정도 알고, 익숙한 사람이면 다음과 같이..

~cpp 
// assign 메소드를 사용한다.
vector<Object> a,b;

b.assign(a.begin() + a.size() / 2, a.end());

  • 이 네 가지 방법을 보자. 첫번째 두번째 방법은 루프를 사용한다. 두번째 방법에 루프가 어딨냐고 물으면 나는 모른다. copy 알고리즘 내부에서 루프를 사용한단다. 하지만 assign 메소드는 루프를 사용하지 않고 한번에 짠! 해주는거 같다.

  • copy, push_back 이런것은 넣어줄때 insert iterator를 사용한다. 즉, 하나 넣고 메모리 할당 해주고, 객체 복사하고(큰 객체면... --; 묵념), 또 하나 넣어주고 저 짓하고.. 이런것이다. 하지만 assign은 똑같은 작업을 한번에 짠~, 만약 100개의 객체를 넣는다면 assign은 copy이런것보다 1/100 밖에 시간이 안걸린다는 것이다.(정확하진 않겠지만.. 뭐 그러하다.)

  • 또 하나의 문제점, insert 메소드는 실행할때마다 새로운 공간을 할당하기 위해 하나씩 밀린다. 만약 컨테이너가 n개의 객체를 가지고 있고, 거기다 m개의 객체를 insert로 넣으면.. n*m만큼 뒤로 땡기느라 시간을 낭비하게 된다. int같은 기본 자료형이면 괜찮을지도 모르지만.. 만약에 객체가 큰 경우라면, 대입 연산자, 복사 생성자 이런것도 저만큼 호출하게 된다. 미친다.

  • range 멤버 메소드는 주어진 두개의 반복자로 크기를 계산해서 한번에 옮기고 넣는다. 벡터를 예로 들면, 만약에 주어진 공간이 꽉 찼을때, insert를 수행하면, 새로운 공간 할당해서 지금의 내용들과, 넣으려는 것들을 그리로 옮기고 지금 있는걸 지우는 작업이 수행된다. 이짓을 100번 해보라, 컴퓨터가 상당히 기분나빠할지도 모른다. 하지만 range 멤버 메소드는 미리 늘려야 할 크기를 알기 때문에 한번만 하면 된다.

  • 성능 따지기 골치 아픈 사람이라도, range 시리즈가 하나씩 시리즈보다 타이핑 양이 적다는 걸 알것이다.



6. Item6. Be alery for c++'s most vexing parse

6.1. 문제점?

  • 아직까지도 STL을 완벽하게 지원하는 컴파일러는 존재하지 않는다.
  • 잊어버리고 있었던 클래스의 생성자에 관한..

~cpp 
class Widget {...};    // 디폴트 생성자가 있다고 가정
Widget a               // 맞다.
Widget b()             // 과연?
  • Widget b() 이것은 Widget형의 객체를 리턴해주는 b라는 이름을 가진 함수다. 이것과 관련해 파싱 에러가 자주 일어난다고 한다.

6.2. 예제 : ints.dat 에 저장되어 있는 정수들을 읽어서 list<int> data에 쓰는 작업을 한다.


~cpp 
ifstream dataFile("ints.dat");
list<int> data(ifstream_iterator<int>(dataFile),ifstream_iterator<int>());     // 이런 방법도 있군. 난 맨날 돌려가면서 넣었는데..--;

  • 왠지는 모르겠지만 두번째 문장은 작동하지 않는다. 위에서 제기한 문제 때문(괄호에 관련된)이다. 별루 중요한 것 같진 않으니 그냥 넘어감. 그래도 해결책은..

6.3. 해결책

~cpp 
ifstream dataFile("ints.dat");
ifstream_iterator<int> dataBegin(dataFile);
ifstream_iterator<int> dataEnd;

list<int> data(dataBegin, dataEnd);         // 요런식으로 써주자.

6.4. 잡담

  • C++이 이렇게 애매한줄은 몰랐다.
  • STL에서 반복자로 돌리는건 표준 스타일이란다. 그렇게 하도록 하자.



7. Item7. When using containers of newed pointers, remember to delete the pointers before the container is destroyed

7.1. 서론

  • 누누히 강조했던 new로 만든거 넣었으면, delete 해주자는 것이다.
  • 컨테이너가 파괴될때 포인터는 지워주겠지만, 포인터가 가리키는 객체는 destroy되지 않는다.(Detected Memory Leaks!)

7.2. 예제

~cpp 
vector<Object*> v;

for(int i = 0 ; i < 10 ; ++i)
	v.push_back(new Object); // new로 넣어줬다.

...
...

for(vector<Object*>::iterator i = v.begin() ; i != v.end() ; ++i)
	delete *i // 지워주자.

return 0;

  • 하지만 ... 부분에서 예외가 터져서 프로그램이 끝나버린다면? 또다시 Detected Memory Leaks!

7.3. 보완법 1(class for function object)

  • 이를 보완하기 위해 delete를 함수 객체로 만드는 법이 있다.(뭐야 이거?)
    • Fucntion Object 보통 class키워드를 쓰던데, struct(이하 class라고 씀)를 써놨군. 뭐, 별 상관없지만, 내부 인자 없이 함수만으로 구성된 class이다. STL에서 Generic 을 구현하기에 주효한 방법이고, 함수로만 구성되어 있어서, 컴파일시에 전부 inline시킬수 있기 때문에 최적화 문제를 해결했음. 오 부지런히 보는가 보네. 나의 경쟁심을 자극 시키는 ^^;; --상민

~cpp 
struct DeleteObject : public unary_function<const T*, void>
{
         template<typename T>
	void operator()(const T* ptr) const
	{
		delete PTR;
	}
};

void f()
{
	...
	for_each(v.begin(), v.End(), DeleteObject());    // 정말 이상하군..--;
}
  • 밑에꺼 쓰고 덧붙이는 건데 이 방법은 열라 안좋은 거란다.(struct DeleteObject, 쳇 그러면서 뭐하러 설명해?-.-)

7.4. 보완법 2(Smart Pointer)

  • 또 다른 방법으로 컨테이너에 포인터를 넣는 대신 스마트 포인터를 넣는 것이다.(아악..--; MDC++(MEC++)을 봐야 하는가..ㅠ.ㅠ)

~cpp 
typedef boost::shared_ptr<Object> SPO;	// boost 라이브러리라는게 있단다.

vector<SPO> v;
for(int i = 0 ; i < 10 ; ++i)
	v.push_back(SPO(new Object));



8. Item8. Never create containers of auto_ptrs.

  • 생략. 도무지 뭔말하는건지 모르겠다. COAP는 또 뭐고..--;
    • 컨테이너를 오토 포인터로 생성하지 말것~


9. Item9. Choose carefully among erasing options.

9.1. 어떤 컨테이너가 int값들을 담고 있다고 하자. 거기서 1982 라는 숫자를 몽땅 지워주고 싶다면?

  • Contiguous-memory container 일때

~cpp 
c.erase( remove(c.begin(), c.end(), 1982), c.end() );        // 이건 내부적으로 어떻게 돌아가는 걸까. 찾아봐야겠군. 
  • list일때 - erase 써도 되지만 remove가 더 효율적이다.

~cpp 
c.remove(1982);
  • Associative container 일때 - remove쓰면 난리난다.(없으니깐--;) 또 제네릭 알고리즘 remove도 역시 안된다. 컨테이너가 망가질수도 있다.

~cpp 
c.erase(1982);

9.2. 조건 검사해서 몽땅 지워주기

  • 또 이상한 팁이 있군. bool형을 리턴하는 함수를 인자로 같이 넣어주면 그 조건을 만족하는 값은 모조리 지워주는..(함수 포인터일까.. 함수 포인터는 아직도 언제 쓰는건지 모르겠다. 혹시 아시는분은 좀 가르쳐 주세요^^;)
    • 함수포인터임. (또는 위에서의 함수객체.) 해당 함수 객체로 조건을 파악한뒤 삭제하거나 비교,소트 하는 일을 많이 함. --1002

9.2.1. 쉽게 할수 있는 컨테이너들

~cpp 
bool badValue(int x) { ... }    // 넣어줄 함수 선언

~cpp 
c.erase( remove_if(c.begin(), c.end(), badValue), c.end() );    // Contiguous-memory Container일때(vector, deque, string)

~cpp 
c.remove_if(badValue);    // list일때

9.2.2. Associative Container 일때

  • 쉽지만 비효율적인 방법 - remove_copy_if 를 사용한다. 이것은 지우고 싶은걸 제외한 나머지 것들을 새로운 컨테이너로 옮긴다. 그 다음에 원래 컨테이너를 새로 만든것과 바꿔 버린다.(우울하군--;)

~cpp 
AssocContainer<int> c;    // map,multimap,set,multiset 등을 일반화한 이름이다. 실제로 저런 이름의 컨테이너는 없다.--;
...
AssocContainer<int> goodValues;

remove_copy_if(c.begin(), c.end(), inserter(goodValues, goodValues.end()), badValue);     // 헉 이분법--;. 보면서 느끼는 거지만 정말 신기한거 많다. 저런 것들을 도대체 무슨 생각으로 구현했을지..

c.swap(goodValues);       // c랑 goodValues랑 바꾼다. 이런것도 있군.
  • 어렵지만 효율적인 방법 - 뭐 또 파일에 쓴다고 해서 이상한방법 쓰는데 그냥 넘겼다.

~cpp 
AssocContainer<int> c;

for(AssocContainer<int>::iterator i = c.begin() ; c != c.end() ; )
{
    if(badValue(*i))
    {
        c.erase(i++);     // 지워야 할 값이면 일단 지우고 반복자 하나 증가시켜준다. 후위 연산자는 그 값을 미리 복사를 하기 &#46468;문에 가능한 일이다. 
    }                     // 그냥 지우면 그 반복자는 void가 된다. 안좋다--;
    else ++i;             // 아니면 그냥 증가
}

9.3. 잡담

  • 반복자를 이용해서 루프를 돌다가 어떤 걸 지우면, 그걸 가리키고 있던 반복자는 갱신된다. 다음에 어떻게 될지 장담 못한다는 뜻이다. 주의하자.


10. Item10. Be aware of allocator conventions and restrictions.


11. Item11. Understand the legitimte uses of custom allocators.


12. Item12. Have realistic expectations about the thread safety of STL containers.

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2009-05-27 07:09:19
Processing time 0.1054 sec