Effective STL - Chapter2 [ Vector 와 String ]

저번 정리가 너무 세세하고 요점이 보이지 않아서 개인적으로 아니다 라고

느껴서 이번에는 깔끔하게 정리를 해보았습니다.

---

CHAPTER2. Vector 와 String

---

내용 정리

1. 배열을 버리고 vector 와 string을 사용해야 하는 이유

2. vector 와 string의 수행 성능을 높이는 방법

3. string의 여러 가지 구현 방식

4. vector 와 string 데이터를 매개 변수로 넘기는 방법

5. 과도한 메모리 할당을 피하는 방법

---

 

1. 배열을 버리고 vector 와 string을 사용해야 하는 이유

 

동적으로 배열 할당 할 시 문제점 : 메모리 해제에 일일이 신경써야 한다.

 

▷ vector 와 string의 경우 

- 자체적으로 메모리 관리

   요소 삽입 시 : 스스로 메모리 확장을 하고, 기존 메모리를 해제 해준다.

   요소 삭제 시 : 메모리에서 소멸될 때 각 객체의 소멸자를 통해 해당 컨테이너 안의 요소를 모두 없애줌과 동시에 메모리도 해제 해준다.

 

▷ vector 와 string 의 장점

- 반복자 사용 가능 (Iterator , reverse_iterator)

- begin, end ,size 같은 멤버 함수

 

▷ 동적 할당 문자열을 string으로 대체하는 가장 큰 이유

: string은 참조 카운팅이 되도록 구현 하여, 불필요한 메모리 할당 과 문자 복사를 없앰으로써 많은 

  애플리케이션에서 높은 수행성능을 낼 수 있도록 하고 있씁니다.

  string을 *참조 카운팅을 통해 최적화 하는것을 상당히 중요하게 생각 하고 있습니다. 

 

문제점 : string을 다중 쓰레드 환경에서 사용하면, 메모리 할당이나 복사에서 절약된 시간을 

*동시성 제어에 걸리는 *오버헤드가 잡아먹는 경우도 생깁니다.

 

문제 해결 방법 

1. 참조 카운팅을 사용하지 않는 다른 string을 구현

2. string 대신에 vector<char>을 고려

 

 

※ 여기서 살펴 보아야 할 것

1. 실제로 우리가 사용하는 표준 STL 라이브러리에 string은 참조 카운팅 되게 구현 되어 있나?

2. 참조 카운팅이 최적화 되는 이유

 

※ 확인

1. 질문 : 실제로 우리가 사용하는 표준 STL 라이브러리에 string은 참조 카운팅 되게 구현 되어 있나?

1. 답 : 아뇨, 현재 String 클래스의 구현 코드를 찾아 보았을 때 '참조 카운트'는 찾아 볼 수 없었습니다. 

         (추측으론 과거의 라이브러리 string에서 참조 카운팅을 한것 같습니다.)

        현재 제가 사용하는 코코스엔진의 string(base_string<char>)를 찾아 봤을 때도 카운팅 되는 부분은 찾을 수 없었습니다.

 

2. 질문 : 참조 카운팅이 최적화 되는 이유

2. 답 : 후에 나옴

---

2. vector 와 string의 수행 성능을 높이는 방법(reserve)

 

▷ vector의 realloc 과정

1. 컨테이너의 현재 용량의 2배가 되는 메모리 블록을 새로 할당(alloc) 합니다.

2. 컨테이너가 가지고 있던 모든 요소 데이터를 새 메모리에 복사(copy) 합니다.

3. 원래의 메모리에 저장된 모든 객체를 소멸(destroy) 시킵니다.

4. 원래의 메모리를 해제(dealloc) 합니다.

 

!! 주의 !!

: 위 과정이 일어나면 반복자, 포인터 혹은 참조자를 사용하고 있던 모든 자료구조를 새로 세팅해야 한다.(무효화)

 

▷ 위 과정을 줄이는 방법

- reserve 멤버 함수 이용 (vector , string)

: 사용할 메모리를 미리 할당해 둠으로써 재할당의 회수를 최소화 시키고, 아울러 메모리 재할당 과

  반복자/포인터/참조자의 무효화로 인해 요구되는 비용 부담을 피해 갈 수 있도록 해줍니다.

 

- reserve를 이용한 불필요한 메모리 재할당을 피하는 방법

1. 컨테이너에 저장되는 요소의 개수를 파악해 미리 필요한 양을 예약(reserve)해 놓는 방법

2. 필요한 최대량을 미리 예약해 놓은 후, 나중에 데이터를 모두 넣고 남은 용량을 잘라내는 방법

 

!! 주의 !!

: push_back 이 아닌, insert를 써서 문자열의 아무 위치에 문자 하나를 넣으려고 할 때 반복자 무효화가 때문에

  문자가 삽입된 위치부터 끝까지의 모든 반복자 / 포인터 / 참조자는 무효화 됩니다.

---

3. string의 구현 방식

( 저자는 여러 구현 방식에 대해 설명 했지만 여기선 다루지 않겠다 )

 

sizeof(string) = 24

 

string이 가지고 있는 정보

- 문자열의 크기(size) : 실제 문자열의 길이

- 문자를 담아두는 메모리의 용량(capacity) : 메모리 용량

- 문자열의 값(value)

- 할당자(allocator) -> 선택적

- 문자열 값에 대한 참조 카운트(reference count) -> 확인해 볼 수 없었음

 

---

4. vector 와 string 데이터를 매개 변수로 넘기는 방법

 

ㅁ 기존의 C API에 vector 와 string을 넘기는 방법

- vector의 요소를 넘기는 방법

vector<int> v;

v[0] ; // 벡터 내의 첫번째 요소에 대한 참조자를 나타냄
&v[0] ; // 첫째 요소를 가르키는 포인터 입니다.

 

- string의 요소를 넘기는 방법

string s;

s.c_str();	// C API 넘길 때

 

ㅁ vector, string 객체를 C API를 통해 초기화

- vector 

: 벡터의 요소 메모리를 API에 그냥 넘긴다.( c / c++ 배열과 동일한 메모리 구조를 가졌기 때문에 )

- string 

: API 쪽에서 vector<char>에 데이터를 쓰게 하고, 이 벡터에서 문자열 쪽으로 데이터를 복사하면 됩니다.

 

ㅁ vector 나 string 가 아닌 다른 STL 컨테이너의 데이터를  C API에 넘기는 방법

: 해당 컨테이너의 데이터를 vector 객체에 복사하고 나서, 그 벡터를 API를 넘기면 됩니다.

---

5. 과도한 메모리 할당을 피하는 방법

 

5-1.  쓸데 없이 남은 용량 없애 주기(swap)

vector<int> numVec;
// for numVec에 데이터 1000개가 삽입됨
// ...
// numVec을 없애주고 싶다.
vector<int>().swap(numVec);

- swap( ) 함수의 흐름

1. 임시 벡터 안의 데이터와 'numVec'안의 데이터가 완전히 바뀌게 됩니다.

2. 'numVec'는 필요 없는 용량이 제거된 상태가 되고, 임시객체는 'numVec'이 사용하고 있던 불필요한 메모리를 가지게 됩니다.

3. 코드가 끝나면 임시 객체가 소멸되기 때문에 그 객체가 떠 맡고 있던 메모리도 동시에 해제 됩니다.

 

!! 주의 !!

: 완벽하게 메모리가 없어진다는 보장은 없습니다.(라이브러리 구현에 따라 최저 용량 설정에 따라 틀립니다.)

 

!! 참고 !!

: 두 컨테이너를 바꾸면 내부의 요소 데이터뿐만 아니라 반복자, 포인터, 참조자도 모두 바뀝니다.

---

5-2. vector<bool> 을 자제해 주자

: vector<bool>은 사실 STL 컨테이너로서 두 가지가  잘못되어 있습니다.

 

① STL 컨테이너가 아니다.

이유 : 컨테이너 요구사항 중 operator[]가 지원되야 한다.

( 한마디로, 하나의 객체의 주소값을 가지고 객체의 포인터를 얻어내야 한다.) 

T * p = &c[0];	//operator[] 반환해 주는 주소값으로 초기화 해줘야 한다.(컨테이너)

 

② bool을 담고 있지 않습니다.

이유 : vector<bool>은 실제로 bool이 들어 있지 않은 가짜 컨테이너입니다. 

         공간을 줄이기 위해 bool을 압축(pack) 시킨 데이터 표현 방식을 쓰기 때문에 컴파일에 실패 합니다.

         vector에 저장되는 bool을 하나의 비트로 나타내어 한 바이트로 여덟 개의 bool을 담을 수 있게 구현함

         vector<bool>은 *비트 필드(bitfield)를 써서 bool을 저장하고 있는 것 처럼 흉내내는 것일 뿐입니다.

          (뭔 소리죠?...bool을 bool로 못 부른다닝..)

 

 

▷ vector<T>::operator[ ] 에서 비트에 대한 참조자처럼 동작하는 객체를 반환하는 방법

: 프록시 객체(proxy object)라고 불리는 패턴을 쓰면 됩니다. (추후에 정리)

 

▷ vector<bool> 을 대신 할 방법

1. deque<bool>

: deque는 vector가 할 수 있는 모든 것을 할 수 있고, 진짜 bool 을 저장하는 컨테이너 입니다.

 

2. bitset(비트셋)

: bitset은 STL 컨테이너는 아니지만, 표준 c++ 라이브러리에 속해 입니다.

  STL 컨테이너와 달리, 비트셋의 크기(요소의 개수)는 컴파일 타임에 고정되기 때문에 요소를 새로 삽입한다든지

  제거 하는 작업은 할 수 없습니다.

  더욱이 STL이 아니기 때문에 반복자를 지원 하지 않습니다.

    하지만, 비트하나 하나를 모아 보여주는 클래스 답게 비트 조작에 관련된 편리한 멤버 함수를 지원 합니다.

 

---

ㅁ 동시성 제어란?
: 동시에 실행되는 여러개의 트랜잭션이 작업을 성공적으로 마칠 수 있도록 트랜잭션의 실행 순서를 
  제어 하는 기법입니다.

 

ㅁ 오버헤드란?
: 프로그램의 실행 흐름에서 나타나는 현상중 하나이며, 
  예를 들어, 프로그램의 실행 흐름 도중에 동떨어진 위치의 코드를 실행 시킬 때,
  추가적으로 시간, 메모리 , 자원이 사용되는 현상 입니다.

 

ㅁ 비트 필드(Bit Fields) 란?

: 비트 필드는 여러 데이터를 하나의 구조체에 넣어 주는 C 언어의 자료구조의 하나입니다.

  메모리 및 저장소가 고가였던 시절 메모리의 사용량을 줄일 목적으로 목적으로 유용하게 사용되었으나, 

  현재는 이러한 목적 보다는 시스템의 제어를 위한 저수준 통신을 위해서 사용됩니다.

   예를 들면 여러 오브젝트를 하나의 머신워드에 넣거나 9비트 짜리 정수와 같은 비표준 외부파일 형식을 읽을 때 사용할 수 있습니다.

struct packed_struct
{
	unsigned int f1:1;
    unsigned int f2:1;
    unsigned int f3:1;
    unsigned int f4:1;
    
    unsigned int type:4;
    unsigned int funny_int:9;
} pack;

 

ㅁ string 참조 카운팅 관련 사이트 

https://del4u.tistory.com/24

참조 카운팅 (Reference Counting) - 2