표준 템플릿 라이브러리(STL) - vector 메모리/ iterator , 표준 라이브러리 - string

https://modoocode.com/223

씹어먹는 C++ - <10 - 1. C++ STL - 벡터(std::vector), 리스트(list), 데크(deque)>

 

표준 라이브러리

https://docs.microsoft.com/ko-kr/cpp/standard-library/cpp-standard-library-header-files?view=msvc-170 

C++ 표준 라이브러리 헤더 파일

 

 

C++ 표준 템플릿 라이브러리 - Standard Template Library

• 임의 타입의 객체를 보관할 수 있는 컨테이너 (container)
• 컨테이너에 보관된 원소에 접근할 수 있는 반복자 (iterator)
• 반복자들을 가지고 일련의 작업을 수행하는 알고리즘 (algorithm)
• 함수 호출 연산자 (operator())를 오버로드하는 클래스들 함수자(functor)

표준 템플리 라이브러리 STL은 컨테이너, 반복자, 알고리즘, 함수자 4가지의 구성요소를 담당

표준 라이브러리 안에 표준 템플릿 라이브러리가 속해있는것이다.

 

 

 

임의 타입의 객체를 보관할 수 있는 컨테이너에서 나타나 있듯이 우리가 다루려는 객체가 어떤 특성을 갖는지 무관하게 라이브러리를 자유롭게 사용할 수 있다는 것

우리가 만일 사용하려는 자료형이 int 나 string과 같은 기본 자료형이 아니라, 우리가 만든 임의의 클래스의 객체들이여도 자유롭게 위 라이브러리의 기능들을 모두 활용할 수 있다.

또한 반복자의 도입으로 알고리즘 라이브러리에 필요한 최소한의 코드만을 작성할 수 있다.

기존의 경우 M 개 종류의 컨테이가 있고 N 종류의 알고리즘이 있다면 이 모든 것을 지원하려면 M * N 개의 알고리즘 코드가 있어야만 했지만 반복자를 이용해서 컨테이너를 추상화 시켜서 접근할 수 있기 때문에 N 개의 알고리즘 코드 만으로 M 종류의 컨테이너들을 모두 지원할 수 있게된다.

 

 

Vector

크기가 가변적인 배열인 vector은 힙 영역에 저장됨

int main() {
    vector<int> vec;
    cout << vec.size() << " " << vec.capacity() << endl;
    vec.push_back(1);
    cout << vec.size() << " " << vec.capacity() << endl;
    vec.push_back(2);
    cout << vec.size() << " " << vec.capacity() << endl;
    vec.push_back(3);
    cout << vec.size() << " " << vec.capacity() << endl;
    vec.push_back(4);
    cout << vec.size() << " " << vec.capacity() << endl;
    vec.push_back(5);
    cout << vec.size() << " " << vec.capacity() << endl;
    vec.push_back(6);
    vec.push_back(7);
    vec.push_back(8);
    cout << vec.size() << " " << vec.capacity() << endl;
    vec.push_back(9);
    cout << vec.size() << " " << vec.capacity() << endl;

    cout << endl;
    vector<char> vec1 = {'a','b','c','d','e'};
    cout << vec1.size() << " " << vec1.capacity() << endl;
    vec1.push_back('f');
    cout << vec1.size() << " " << vec1.capacity() << endl;
}

size()는 벡터의 유효한 요소들의 개수

capacity()는 벡터의 요소들을 담을 수 있는 메모리가 할당되어있는 공간의 용량

 

 

벡터를 따로 초기화 해주지않고 선언만 되어있으면 size, capacity모두 0으로 되어있고, 사이즈를 4만큼 지정해 주고 선언해 주었으면 4만큼 되어있다.

 

벡터의 길이보다 용량이 더 많을 때 뒤에 새로운 원소를 추가하게 되면 할당된 공간에 원소를 쓰기만하면된다. -> O(1)

 

하지만 새로운 원소를 추가하게될때 용량이 부족할 경우 더 큰 용량의 벡터를 새롭게 할당해야한다.

(기존 용량의 2배만큼 새롭게 할당된다.)

 

이 경우, 새로운 벡터를 할당 하고 기존의 벡터 n 개의 원소를 모두 복사하고 기존의 벡터 메모리를 해제해야한다. -> O(n) 

 

 

이러한 빈번한 재할당O(n)이 많이 일어나는것을 방지하기위해 미리 용량(capacity)를 확보해놓기 위해 reserve혹은 resize 를 사용

vector<int> v{ 10, 20 };
cout << v.size() << endl; // 2
cout << v.capacity() << endl; // 2
v.reserve(100);
cout << v.size() << endl; // 2
cout << v.capacity(); // 100


vector<int> v{ 10, 20 };
cout << v.size() << endl; // 2
cout << v.capacity() << endl; // 2
v.resize(100, 1); // = vector<int> (100,1)
cout << v.size() << endl; // 100
cout << v.capacity(); // 100

reserve는 용량만 확보 하고 값을 채우지않는 반면

resize는 용량확보하고 그만큼 값을 채운다

 

이렇게 사용할만큼 예측하여 미리 할당해주면 재할당발생빈도를 줄일 수 있다. 

 

 

 

 

 

 

반복자 (iterator)

반복자는 컨테이너 원소에 접근할수있는 포인터와 같은 객체

 

v.end()가 마지막 원소가 아니라 마지막 원소의 다음을 가리키는 이유?

v.begin() == v.end() 라면 원소가 없는 벡터를 의미한다.

만약 v.end()가 마지막 원소를 가리킨다하면 비어있는 벡터를 표현할수 없다.

 

iterator

int main() {
    vector<int> vec = {1,2,3,4,5};

    // 전체 벡터를 출력하기
    for (vector<int>::iterator it = vec.begin(); it != vec.end(); it++) {
        cout << *it << :endl;
    }
}

 

reverse_iterator

// 뒤에서부터 출력하기
for (vector<int>::reverse_iterator it = vec.rbegin(); it != vec.rend(); it++){
    cout << *it << " ";
}

 

 

뒤에서 부터 출력하려면 직접 index를 참조하여 출력하는 방식이있다.

모든 정수 유형은 C/C++ index에서 허용된다.

for(int i = vec.size()-1; i>=0; i--)
    cout << vec[i] << " ";

극단적으로 보았을때 부호가 있는 정수타입 int의 경우 오버 플로우를 발생시킬수 있고, 배열의 index는 음수값을 갈수없기때문에 index의 타입은 부호없는 정수라고한다. (size_t - 해당 운영체제에서 어떤 객체나 값이 포함할 수 있는 최대 크기의 데이터를 표현하는 타입으로 반드시 unsigned 형)

 

그래서 제대로 타입을 맞추어 주었을 경우

for(vector<int>::size_type i = vec.size()-1; i>=0; i--)
    cout << vec[i] << " ";

위에는 int, 아래는 size_type

i는 음수값을 가게되면서 언더플로우가 발생하게되면서 for문이 종료되지않는다.

 

따라서 역으로 원소를 참조하고싶을때는 역반복자를 이용하는것이 좋다고 한다.

 

 

 

string

string은 표준 라이브러리안에 속해있으며 , 표준 템플릿 라이브러리(STL)에는 속해있지않다.

string은 문자를 원소로 저장하고 문자열을 조작하기위한 '컨테이너' 이긴 하지만 STL에 속해있지않다.

string은 vector 컨테이너와 비슷한 시퀀스 컨테이너이며 배열 기반 컨테이너이다. (근데 vector는 STL이고 string은 STL이 아니다)

char*, char[]과 달리 문자열 끝에 '\0'이 붙지않고 문자열의 길이를 동적으로 변경 가능하다.

 

vector공부하다가 string도 동적할당 되는것을 알게되었다.

string 클래스는 자동으로 new 와 delete 를 실행하여 메모리 관련 부분을 대신해준다.

string도 마찬가지로 capacity로 할당된 크기를 알수있고, size값이 capacity를 넘으면 더 큰 capacity의 string을 재할당하고 기존의 string을 복사한뒤 파괴한다.

int main()
{
    string a = "str";
    string b = "<capacity15";
    string c = ">capacity-30 aaaaaaaaaaaaaaaaaaaa ";

    cout << a << endl;
    printf("a 변수 주소: %p\n",&a);
    printf("a[0]이 할당된 주소: %p\n",&a[0]);
    printf("a[1]이 할당된 주소: %p\n",&a[1]);
    printf("a[2]이 할당된 주소: %p\n",&a[2]);
    cout << "사이즈: " << a.size() << endl;
    cout << "용량: " << a.capacity() << endl;
    cout << endl;

    a.append(b);

    cout << a << endl;
    printf("a 변수 주소: %p\n",&a);
    printf("a[0]이 할당된 주소: %p\n",&a[0]);
    printf("a[1]이 할당된 주소: %p\n",&a[1]);
    printf("a[2]이 할당된 주소: %p\n",&a[2]);
    cout << "사이즈: " << a.size() << endl;
    cout << "용량: " << a.capacity() << endl;
    cout << endl;

    a.append(c);

    cout << a << endl;
    printf("a 변수 주소: %p\n",&a);
    printf("a[0]이 할당된 주소: %p\n",&a[0]);
    printf("a[1]이 할당된 주소: %p\n",&a[1]);
    printf("a[2]이 할당된 주소: %p\n",&a[2]);
    cout << "사이즈: " << a.size() << endl;
    cout << "용량: " << a.capacity() << endl;
}

처음 3사이즈에 15용량인 string일때, 그리고 용량이 넘지않게끔 string을 붙여도 할당된 주소값이 바뀌진 않았지만 용량이 넘칠만큼 붙이게되면 재할당되어 주소값이 바뀌는것을 알수있다. (변수 a의 주소값은 바뀌지않는다) 

 

 

 

 

 

 

Push_back vs Emplace_back

emplace_back 가변인자 템플릿을 사용하여 객체 생성에 필요한 인자만 받은 후 함수내에서 객체를 생성

class Test {
private:
    int value;
public:
    Test(const int _value):value(_value) { cout << "생성자" << endl; }
    virtual ~Test() { cout << "소멸자" << endl; }
    Test(const Test& obj) { cout << "복사 생성자" << endl; }
};

int main()
{
    vector<Test> vec;
    vec.reserve(5);

    cout << "push back 1---------------------" << endl;
    vec.push_back(5);
    cout << "push back 1---------------------" << endl;

    cout << "push back 2---------------------" << endl;
    vec.push_back(Test{5});
    cout << "push back 2---------------------" << endl;

    cout << "emplace back 1---------------------" << endl;
    vec.emplace_back(5);
    cout << "emplace back 1---------------------" << endl;

    cout << "emplace back 2---------------------" << endl;
    vec.emplace_back(Test{ 5 });
    cout << "emplace back 2---------------------" << endl;
}

//push back 1-------------------- -
//생성자
//복사 생성자
//소멸자
//push back 1-------------------- -
//push back 2-------------------- -
//생성자
//복사 생성자
//소멸자
//push back 2-------------------- -
//emplace back 1-------------------- -
//생성자
//emplace back 1-------------------- -
//emplace back 2-------------------- -
//생성자
//복사 생성자
//소멸자
//emplace back 2-------------------- -

즉, emplace_back의 효율을 보려면 Test 구조체의 경우 emplace_back(int) 를 사용해야 함

 

 

emplace_back() 과 push_back() 중 어느것이 더 효율적이다. 라고 말하기는 힘들지만, 두 함수의 차이점을 생각했을 때 다음과 같은 이슈가 발생할 수 있다.

int main(){
	vector<vector<int>> v;
}

다음과 같이 v 가 이중 벡터로 되있는 경우 push_back() 를 사용하면 다음과 같이 데이터를 넣을 수 있다.

vector<int> v1 = { 1, 2 };
v.push_back(std::move(v1));

이 때 다음과 같이 데이터를 넣는 경우는 매칭되는 생성자가 없어 오류가 발생하게 된다.

v.push_back(10); 	// <- ERROR

하지만, emplace_back() 을 사용하면 오류가 발생하지 않게 된다.

v.emplace_back(10);		// <- NOT ERROR

 

이는 v[0] 안에 10개의 새로운 공간을 할당하라는 뜻이기에 발생하는데, 이처럼 emplace_back() 은 컴파일 타임에서 에러를 잡아내지 못하기에 의도하지 않은 결과가 나올 수 있다.