Effective STL - Chapter1 효과적인 컨테이너 01

이 책은 "Effective STL : C++ 표준 템플릿 라이브러리(STL)를 효과적으로 활용하는 50가지의 명쾌한 테크닉 모음 입니다.

 

저자의 STL 정의 : 반복자(iterator)를 가지고 동작하는  C++ 표준 라이브러리의 일부분

---

1-1 : 적재적소에 알맞은 컨테이너를 사용하자

• 표준 STL 시퀀스(sequence) 컨테이너 : vector , string ,deque , list   → 선형
• 표준 STL 연관(aasociative) 컨테이너 : set , multiset , map, multimap  → key , value  
• 비표준 시퀀스 컨테이너 : slist 와 rope가 있습니다. ( slist : 단일 연결 리스트 / rope : 대용량(문자열) string)
• 비표준 연관 컨테이너 : hash_set , hash_multiset , hash_map , hash_multimap
• string 대신 사용 되는 vector<char> : string은 참조 카운팅이 되도록 구현이 되어 있기 때문에, 문자열을 나타낼 때에는 
  vector<char>
• 표준 연관 컨테이너 대신 사용되는 vector : vector가 수행 속도나 크기 면에서 표준 연관 컨테이너 보다 더 나을 때도 있다.
• STL에 속하지 않는 표준 컨테이너 : 배열 , bitset , valarray, stack, queue, priority_queue

 

연속 메모리(contiquous-memory) 컨테이너 /  노드 기반(node_based) 컨테이너

 

ㅁ 연속 메모리 컨테이너 (배열 기반 컨테이너)

: 동적 할당된 하나 이상 의 메모리 단위(chunk)에다가 데이터 요소를 저장해 두는 컨테이너 입니다.

  새 요소가 삽입 되거나 삭제되면, '밀어내기' 때문에 수행 성능이 떨어지게 될 수 있습니다.

  ( 표준 : vector , string ,deque / 비표준 : rope ) 

 

ㅁ 노드 기반 컨테이너: 동적 할당된 하나의 메모리 단위에다가 하나의 요소만을 저장 합니다.  컨테이너 요소를 삽입 혹은 삭제 했을 때 노드의 포인터만이 영향을 받지, 노드의 내용은 그대로 입니다.  '밀어내기' -> X , 전형적으로 균형 트리(balance tree)로 구현 되어 있습니다.( 표준 : list , slist / 비표준 : hash_set , hash_map 등 )

 

* string 코드는 참조 카운팅이 되도록 구현되어 있습니다.* rope는 참조 카운팅에 기반하여 구현되었습니다.

 

1-2 : "컨테이너에 독립적인(container-independent) 코드" 라는 환상을 조심하자

컨테이너에 독립적인 환상이란, 각 컨테이너의 공통된 특징만을 사용하도록 하는 프로그래밍 입니다.

각 STL 컨테이너는 각자 자신만의 장점과 약점을 가지고 있기 때문에, 서로 바꾸어서 쓸 수 없도록 설계 되었습니다.

그렇기에 컨테이너 타입을 바꾸 수 밖에 없을때는 변경을 조금 더 용이하게 해주기 위해 "캡슐화"를 이용하면 됩니다.

 

ㅁ 컨테이너와 반복자 타입에 대해 typedef 하기

▷ 기존 스타일

class Widget{...}'
vector<Widget> vw;
Widget bestWidget;

...
vecotr<Widget>::iterator i = 	// bestWidget에다가 어떤 값을 줍니다.
find(vw.begine(), vw.end(),bestWidget);	
// bestWidget과 같은 값을 가진 Widget을 벡터에서 찾습니다.

▷ typedef 스타일

class Widget{...};
typedef vector<Widget> WidgetContainer;
typedef WidgetContainer::iterator::iterator WCIterator;
WidgetContainer vw;
Widget bestWidget;

...
WCIterator i = find(vw.begin(), vw.end() , bestWidget);

별칭(typedef)를 이용하여 컨테이너 타입을 훨씬 쉽게 바꿀 수 있습니다.

 

▷ template class 인자 추가 -> typedef를 이용하기 때문에 typedef 정의만 바꿔주면 된다. 

    typedef로 선언하고 사용한 코드들은 변경 할 필요가 없다.

class Widget{...};

template<typename T>
SpecialAllocator{...};

typedef vector<Widget, SpecialAllocator<Widget>> WidgetContainer;
typedef WidgetContainer::iterator WCIterator;
WidgetContainer vw;
Widget bestWidget;
...
WCIterator i = find(vw.begin() , vw.end() , bestWidget);

 

typedef는 어떤 타입에 붙인 다른 이름에 불과하기 때문에, 이것으로 할 수 있는 캡슐화의 효과는 지극히 '문자적(lexical)' 입니다.

▷ 클래스로 다른 컨테이너로 바꿀 경우 

: 클래스에 컨테이너를 숨기고, 그 컨테이너에 관련된 정보 중에 필요한 것만 클래스 인터페이스를 통해 개방하면 됩니다.

// 상품 구매자 '리스트'를 만든다고 할 때
class CustomerList
{
	private:
    	typedef list<Customer> CustomerContainer;
        typedef CustomerContainer::Iterator CCIterator;
        CustomerContainer customers;
        
    public:
    	필요한 데이터를 받아 올 수 있는 인터페이스 함수 선언
        ...
 }

 

1-3 : 복사(Copy)는 컨테이너 안의 객체에 맞게 비용은 최소화하며, 동작은 정확하게 

컨테이너의 본분은 객체를 담아 관리하는 것 
컨테이너에 들어가는 것은 여러분이 지정한 그 객체의 복사본(copy) 이다.

복사 되어 들어가고 (copy in) , 복사 되어 나오는 것 (copy out)

"객체 복사", 이것이 바로 STL이 사는 법 입니다.

 

▷ 복사 생성자와 복사 대입(assignment) 연사자(operator=)

class Widget
{
	public:
    	...
        Widget(const Widget&);				// 복사 생성자
        Widget& operator=(const Widget&);		// 복사 대입 연산자
        ...
};

▷ 상속된 객체의 경우 복사 동작 중에 데이터가 잘라지는 경우가 있습니다.(슬라이스) - 객체 컨테이너

vector<Widget> vw;

class SpecialWidget:				//SpecialWidget은 Widget에서
	public Widget{...};			//상속 받았습니다.
    
SpecialWidget sw;				// sw는 vw에 추가될 때 기본 클래스
vw.push_back(sw);				// 객체로서 들어갑니다. 따라서 복사
						// 도중에 sw만의 성질을 잃습니다.

기본 클래스(base class) 객체의 컨테이너를 만들어 놓고 여기다가 파생 클래스(derived class) 객체를 넣으면, 복사 과정에서

기본 클래스의 복사 생성자가 쓰이면서 파생 클래스 부분에 선언된 데이터는 잘려 나갑니다.

 

방법 : 객체 컨테이너 x / 포인터 컨테이너 

포인터의 복사는 일단 속도가 빠르고, 예상 했던 대로 동작하며, 포인터가 복사될 때 잘려나가는 현상이 생기지 않습니다.

그리고 스마트 포인터를 사용하면 골칫거리(memory leak)를 피할 수 있습니다.

• 컨테이너(Container)에 포인터(Pointer)를 저장한다는 것은 포인터가 가리키는 객체가 아니라 포인터가 복사된다는 뜻 입니다.
  

 

1-4 : size() 의 결과를 0 과 비교할 생각이면 차라리 empty를 호출하자

if(c.size()==0)
// 두 코드는 본질적으로 같다.
if(c.empty())

• empty()함수는 모든 STL로 구현된 container들 모두에 대하여 O(1)이다.
• size() 함수는 특정 container(std::list)는 STL 구현에 따라서 O(n)이 될 수 있다.

 

▽ list 컨테이너에 Size함수의 선형 시간이 걸리는 상황

list.splice( ) 함수는 컨테이너 데이터를 복사하지 않고 그대로 옮겨서 사용합니다.(상수의 시간 소요)

그러면, 추가된 데이터를 "세어야" 하기 때문에 선형시간이 걸리게 된다.

list<int> list1;
list<int> list2;
...							// list2에 있는 모든 노드 중에서
list1.splice(						// 가장 처음 5가 나타나는 부분 부터
	list1.end(), list2,				// 뒤에서 가장 처음 10이 나타는
    find(list2.begin(), list2.end() , 5),		// 부분까지를 list1의 끝에다가
    find(list2.rbegin(), list2.rend(), 10).base()	// 옮겨 놓습니다. "base()" 호출에
);

#include <iostream>
#include <list>

int main()
{
	std::list<int> list1 = { 1,2,3,4,5,6 };
	std::list<int> list2 = { 7,8,9 };
	std::list<int>::iterator it;

	it = list1.begin();

	list1.splice(it, list2);  	// {7,8,9,1,2,3,4,5,6}

	int size = list2.size();	// SIZE = 0;

	return 0;
}

 

 

1-5 : 단일 요소를 단위로 동작하는 멤버 함수보다 요소 범위를 단위로 동작하는 멤버 함수가 더 낫다.

ㅁ assign 함수

: 이 함수는 표준 시퀀스 컨테이너(vector ,string , deque , list)라면 모두 사용 가능합니다.

  범위 멤버 함수(range member function)는 STL 알고리즘 처럼 의도한 일을 적용할 요소들의 '범위'를 두 개의 반복자를 사용해서

  지정 합니다.

 

▷ assign 함수를 이용한 요소들의 범위 바꾸기

#include <iostream>
#include <vector>

void print(std::vector<int> TargetVector)
{
    for(auto number : TargetVector)
        std::cout << number <<" ";
    
    std::cout << std::endl;
}


int main(void)
{
    // vector.assign(x,y) : x개의 y로 할당 / 기존데이터 삭제
    // vector.assign(x,y) : x~y 데이터를 할당 / 기존 데이터 삭제
    
    std::vector<int> vector1 = {1,2,4,5,7,8};
    std::vector<int> vector2 = {10,11,12};
    
    print(vector1);	// 1,2,4,5,7,8
    
    vector1.assign(3,5);  
    print(vector1);	// 5, 5, 5
    
    vector1.assign(vector2.begin(), vector2.end());
    print(vector1);	// 10,11,12
    
}

이 assign 함수는 루프를 사용하지 않고 요소들을 바꿀 수 있습니다. 

 

▷ 삽입 연산자(back_insert) & copy를 이용한 복사

    vector<Widget> v1, v2;
    
    copy(v2,begin() + v2.size() / 2, v2.end(), back_insert(v1));

▷ 삽입 연산자(insert)를 사용해서 복사 대상 범위를 지정하는 복사

vector<Widget> v1, v2;

v1.insert(v1.end() , v2.begin() + v2.size() / 2, v2.end());

 

◈ 단일 요소 멤버 함수보다 범위 멤버 함수가 더 좋은 이유

• 범위 멤버 함수를 사용한 코드가 대개 짧다(즉, 프로그래머의 손이 덜 아프다).
• 범위 멤버 함수는 훨씬 명확하고 간결한 의미를 전달한다.

단일 요소 멤버 함수에서는 메모리 할당자의 요구도 많고 객체 복사도 빈번하며 , 불필요한 연산도 더 자주 일어납니다.

같은 일을 한다고 볼 때 범위 멤버 함수는 이보다 효율적 입니다.

 

▷  Array 데이터를 vector에 복사(vector.insert( ) ) → 범위 버전의 insert

int data[numValues];

vector<int> v;
...
	// 범위를 삽입할 위치, 삽입할 범위의 시작, 삽입할 범위의 끝
v.insert<v.begin() , data, data + numValues);	// data에 들어 있는 int 들을
						// v의 앞에다가 끼워 넣습니다.

▷  위의 코드를 iterator를 넣은 순환 호출로 구현 → 단일 버전의 insert

vector<int>::iterator insertLoc(v.begin());
for(int i = 0; i < numValues ; ++i)
{
	insertLoc = v.insert(insertLoc, data[i]);
}

원래의 순서와 반대로 v에 들어간다

    ( 위 코드 : 거꾸로 삽입되는 것을 해결 하는 방법 )

▷  copy를 이용한 요소 삽입 → 범위 버전의 insert

const int numValues = 10;
int data[numValues] = {1,2,3,4,5,6,7,8,9,10};

std::vector<int> v;

// loop X
copy(data , data + numValues , std::insert(v, v.begine()));

 

◈ 단일 요소 버전의 insert의 단점 ("수행 성능세")

1. 불필요한 함수 호출

단일 버전 : vector에 numValue개의 요소를 한번에 하나씩 넣기 때문에 numValue 만큼 불리게 됩니다.

범위 버전 : 한번의 함수 호출로 끝나기 때문에 호출 회수가 numValue -1 만큼 줄어 듭니다.

 

2. 인라이닝으로도 공제가 불가능한  비용

ex ) v에 n개의 요소가 있다.

단일 버전 : n * numValues 만큼 이동이 일어 납니다.

                 만약 v 가 Widget 같은 복잡한 객체를 담고 있다고 하면 요소를 이동 시킬 때마다 해당 객체 타입의

                 대입 연산자나 복사 생성자가 호출될 것입니다.

                 이럴 경우 (n-1)*numValues번은 Widget의 대입 연산자가, numValues번은  Widget의 복사 생성자가 호출 됩니다.

 

범위 버전 : 하나의 데이터를 요소를 옮기는데 한번이면 끝납니다.

                     즉 , 총 비용은 n번의 이동량 뿐입니다.

비교	단일 버전	범위 버전
횟수	n * numValue	n
차이 횟수	n * (numValue -1)

3. 메모리 할당  

상황 : 새 데이터를 추가 하려는데 메모리가 꽉찬 컨테이너 

비교	단일 버전	범위 버전
Vector / String	log2 * numValues (1000개의 요소를 삽입할 때 새로운 메모리 할당 10번 일어남)	삽입 전에 필요한 메모리량을 예측할 수 있기 때문에, 메모리 할당을 무식하게 여러번 수행 하지 않음 (엄청난 절감 효과)
List	2*(numValues -1) next 포인터를 두번 업데이트 하게 됨	최종적으로 삽입될 노드의 개수를 파악할 수 있기 때문에, 불필요한 포인터 세팅을 피해 주고 한 번의 대입만으로 각 포인터가 삽입 후의 노드 주소 값을 가지게 세팅 함

ㅁ Iterator

: 매개 변수 타입인 iterator는 말 그대로 컨테이너의 반복자 타입, 즉 container::iterator란 뜻입니다.

 

ㅁ 범위를 지원하는 멤버 함수

1. 범위 생성(Range Construction)

: 모든 표준 컨테이너는 다음과 같은 평태의 생성자를 지원하고 있습니다.

container::container(InputIterator begin,	// 범위 시작
		InputIterator end);		// 범위의 끝

2.범위 삽입(Range Insertion) : 모든 표준 컨테이너는 다임과 같은 형태의 insert를 지원하고 있습니다.

void container::insert(iterator position, // 범위를 삽입할 위치
	inputIterator begin,	   	 // 삽입할 범위의 시작
   	 inputIterator end);		// 삽입할 범위의 끝

연관 컨테이너는 자신이 가지고 있는 비교 함수를 사용하여, 삽입될 요소가 놓일 위치를 결정하기 때문에, 위치 매개 변수를

가지고 있지 않은 시그니처를 제공 합니다.

void container::insert(InputIterator begin , InputIterator end);

※ 단일 요소 버전의 insert를 범위 버전으로 교체할 때 주의 할 점!

: push_front, push_back은 하나의 요소를 컨테이너에 넣는 함수 이지만 "삽입"류로 불리지 않습니다. 

  그렇기에 push_front , push_back을 호출하는 루프를 보게 된다면 범위 버전의 insert로 바꾸기 바랍니다!

 

push_front , push_back ---> 삽입류 X

 

3. 범위 삭제(Range Erasure) : 역시 표준 컨테이너에서 범위 버전의 erase를 제공하고 있지만, 반환 타입은

    시퀀스 퀀테이너와 연관 컨테이너에 대해서 각각 다릅니다.

▷ 시퀀스 컨테이너

iterator container::erase(iterator begin , iterator end);

▷ 연관 컨테이너

void container::erase(iterator begin , iterator end);

 

 ㅁ 시퀀스 컨테이너와 연관 컨테이너의 구현이 다른 이유

 : 연관 컨테이너 버전의 erase에서 반복자를 반환하게 되면 수행성능에 저하가 일어 납니다.

   그렇기에 연관 컨테이너는 반환을 하지 않는 void erase 함수로 구현을 하고, 

   시퀀스는 반복자를 반환하여도 수행면에서 문제가 없기에 iterator를 반환하게 구현 되었습니다.

 

erase 함수의 경우 ---- 함수 호출 횟수 ---->    단일 요소 버전  > 범위 요소 버전

비교	단일 요소 버전	범위 요소 버전
erase	내부 데이터 요소가 한 위치씩 마지막 위치 까지 이동	한 번의 이동으로 마지막 위치까지 이동

ㅁ vector 와 string 의 erase 문제 ( 메모리 할당 )

: vector 와 string의  메모리는 새 데이터 요소를 넣을 때 자동으로 메모리가 늘어나지만, 

  erase 같은 경우 자동으로 메모리를 줄여 주지 않습니다.

  그렇기에 범위 버전 erase의 특성을 확실히 나타내 주는 것이 erase 와 remove를 함께 사용하는 erase-remove 합성문 입니다.

  그럼 범위 요소를 지움과 동시에 메모리를 줄여줄 것 입니다.

 

4. 범위 대입(Range Assignment) : 모든 표준 시퀀스 컨테이너는 범위 버저너의 assign을 제공 하고 있습니다.

void container::assign(InputIterator begin , InputIterator end);

 

범위 멤버 함수는 작성이 쉽고, 동작의 의미를 명확하게 나타내 주며 , 수행 성능도 월등히 높습니다.

 

---

다음 페이지에서 계속...