[C++] vector 컨테이너 부수기

안녕하세요? 수구리입니다.

 

이번 포스팅에서는 vector에 대한 좀 더 자세히 알아보기 위해서 정리를 해보았습니다.

 

알고 있었던 부분도 있었지만, 더 나아가 자세한 내용을 살펴보니 제가 모르던 내용도 있었습니다.

 

vector에 대한 개념이 잡히셨으면 좋겠습니다!

 

소개

• 이번 장에서는 표준 라이브러리에서 제공하는 기능에 대해서 알아보자.

17.1 컨테이너 개요

• 표준 라이브러리 컨테이너를 사용하면 여러 가지 위험에 노출될 가능성을 최대한 줄일 수 있다.
• 표준 라이브러리에 있는 것들은 모두 std 네임스페이스에 속한다.

17.1.1 원소에 대한 요구사항

• 표준 라이브러리 컨테이너는 원소를 값으로 처리한다.
• 즉, 값 전달 방식으로 복제본을 저장하고, 대입 연산자로 대입 후, 소멸자로 원소를 삭제하는 과정이라는 의미이다.
• 원소를 레퍼런스로 처리하고 싶다면 (레퍼런스 전달 방식) 원소에 대한 포인터를 저장한다.
• 그러면 컨테이너에서 복제하는 대상이 포인터이지만 복제된 값도 결국 똑같은 원소를 가리키기 때문.

17.1.2 익셉션과 에러 감사

• 표준 라이브러리 컨테이너는 에러 검사 기능을 제공
• 어떤 익셉션이 발생할 수 있는지에 대해 소개

17.1.3 반복자

• 표준 라이브러리는 컨테이너의 원소에 접근하는 기능을 범용적으로 제공하기 위해 반복자(iterator) 패턴을 사용
• 반복자는 컨테이너의 특정 원소에 대한 포인터이다.
• 반복자의 기본 연산은 일반 포인터와 비슷하다. 따라서 일반 포인터를 얼마든지 특정 컨테이너에 대한 반복자로 쓸 수 있음.
• 다양한 컨테이너의 반복자에 대한 기본 사용법에 대해서 알아보자.

begin(), end() 메서드

• begin()은 첫 번째 항목을 참조하는 반복자를 리턴
• end()는 마지막 항목의 바로 다음 원소에 해당하는 지점을 가리키는 반복자를 리턴
• begin()과 end()는 모두 첫 번째 원소는 포함하지만, 마지막 원소는 포함하지 않는 반개방 범위를 지원함.
• 수학 기호로 [begin, end) 라고 표현

 

 

---

 

17.2 순차 컨테이너

• vector, deque, list, forward_list등을 순차 컨테이너라고 함.
• 이번 절에서는 vector 컨테이너에 대해서 알아보자.

17.2.1 vector

• 벡터 컨테이너는 표준 C 스타일 배열과 매우 비슷
• 원소를 인덱스로 접근 가능, vector의 끝자리뿐만 아니라 원하는 지점에 원소 삽입 가능
• 원소를 추가하거나 삭제하는 작업은 선형 시간이 걸림.
• 반면 추가와 삭제 연산을 끝에서 처리한다면 분할 상환 상수 시간이 걸린다.

1. vector 개요

고정 크기 vector

• vector를 사용하는 가장 쉬운 방법은 고정 크기 배열처럼 사용하는 것
• 마지막 원소에 접근하는 방법은 operator [] 말고도 at(), front(), back() 메서드가 있다.
• at()은 경계 검사를 수행해서 인덱스가 범위를 벗어나면 out_of_range 익셉션을 던짐
• front()와 back()은 첫 번째와 마지막 원소에 대한 레퍼런스 리턴

 

최고점이 100이 되도록 시험 점수를 정규화 하는 프로그램

#include <cstddef>
#include <vector>
#include <iostream>
#include <limits>

using namespace std;

int main()
{
    vector<double> doubleVector(10); // double 값 열 개를 담은 vector를 생성한다.

    // 최댓값(max)을 double의 최솟값으로 초기화한다.
    double max = -numeric_limits<double>::infinity();

    for (size_t i = 0; i < doubleVector.size(); i++) {
        cout << "Enter score " << i + 1 << ": ";
        cin >> doubleVector[i];
        if (doubleVector[i] > max) {
            max = doubleVector[i];
        }
    }

    max /= 100.0;
    for (auto& element : doubleVector) {
        element /= max;
        cout << element << " ";
    }
    cout << endl;
    return 0;
}

• size() 메서드로 컨테이너에 담긴 원소의 수를 파악
• 범위 기반 for문을 작성하여 요소에 접근후 출력

 

동적 크기 vector

• vector의 진가는 크기가 동적으로 조절된다는 데 있다.
• 위의 프로그램에서 입력하는 점수의 개수에 제한이 없다고 가정

#include <cstddef>
#include <vector>
#include <iostream>
#include <limits>

using namespace std;

int main()
{
    vector<double> doubleVector; // double 값 열 개를 담은 vector를 생성한다.

    // 최댓값(max)을 double의 최솟값으로 초기화한다.
    double max = -numeric_limits<double>::infinity();

    for (size_t i = 1; true; i++) {
        double temp;
        cout << "Enter score " << i << " (-1 to stop): ";
        cin >> temp;
        if (temp == -1) {
            break;
        }
        doubleVector.push_back(temp);
        if (temp > max) {
            max = temp;
        }
    }

    max /= 100.0;
    for (auto& element : doubleVector) {
        element /= max;
        cout << element << " ";
    }
    cout << endl;
    return 0;
}

• 점수를 하나씩 읽을 때마다 push_back() 메서드로 vector에 추가

 

2. vector의 세부 기능

생성자와 소멸자

• 디폴트 생성자는 원소가 0개인 vector를 생성함
• 원소 수와 초깃값 설정 가능

vector<int> inVector; // 원소 수가 0인 int 타입의 vector 생성
vector<int> intVector(10, 100); // int형 백터 10칸 모두 100으로 초기화
vector<string> stringVector(10, "hello");

 

vector의 복제와 대입

• vector는 객체의 복제본을 저장함.
• 복제 생성자와 대입 연산자는 vector의 원소를 복제할 때 깊은 복제를 수행
• 성능을 높이려면 함수 또는 메서드에 vector를 전달할 때 레퍼런스나 const 레퍼런스로 전달하자

// 두 vector의 내용을 상수 시간에 맞바꾸는 swap() 메서드
vector<int> v1(10);
vector<int> v2(5, 100);
v1.swap(v2);
// 결과
// v1은 값이 100인 원소 5개를 갖게 되고,
// v2는 값이 0인 원소 10개를 갖게 된다.

 

vector 비교

• 자주 사용하는 비교 연산자를 오버로딩한 버전을 제공함.
• int type과 vector를 비교하는 예시를 보자

#include <vector>
#include <iostream>

using namespace std;

int main()
{
    vector<int> vectorOne(10);
    vector<int> vectorTwo(10);

    if (vectorOne == vectorTwo) {
        cout << "equal!" << endl;
    } else {
        cout << "not equal!" << endl;
    }

    vectorOne[3] = 50;

    if (vectorOne < vectorTwo) {
        cout << "vectorOne is less than vectorTwo" << endl;
    } else {
        cout << "vectorOne is not less than vectorTwo" << endl;
    }
    return 0;
}

// 실행 결과
// equal!
// vectorOne is not less than vectorTwo

 

vector 반복자

• 예제와 실제 사용법을 중심으로 vector의 반복자에 대해서 알아보자.
• 앞의 점수 정규화 프로그램에서 범위 기반 for문이 아닌 반복자를 사용하는 버전을 살펴보자.

for (vector<double>::iterator iter = begin(doubleVector); iter != end(doubleVector); ++iter) {
  *iter /= max;
  cout << *iter << " ";
}

• 위의 iter 초기화를 할 때 auto iter =...로 대체가 가능함.
• 증가 연산을 수행하는 부분에서 몰랐던 부분이 있었다.
• 대체로 후행 증가를 하곤 했는데 후행 증가보다는 선행 증가가 성능이 좋다는 것을 알게 되었다.

 

가능하면 후행 증가 보다는 선행 증가를 지정하는 것이 좋다. 후행 증가는 새로운 반복자 객체를 리턴하는 반면, 선행 증가는 레퍼런스만 리턴하기 때문이다!

 

// auto 키워드를 사용한 버전, 이 코드를 사용하려면 앞에 나온 for문을 주석처리한다.
for (auto iter = begin(doubleVector); iter != end(doubleVector); ++iter) {
  *iter /= max;
}

• auto 키워드를 사용하면 초기화 문장의 우변 타입을 보고 iter 변수의 타입을 추론함.
• 위의 예에서 우변 : begin()을 호출한 결과

 

원소 객체의 필드에 접근하기

• 컨테이너의 원소가 객체라면 반복자에 "->" 연산으로 객체의 메서드나 데이터 멤버에 접근이 가능하다.

#include <vector>
#include <string>
#include <iostream> // for cout

using namespace std;

int main()
{
    vector<string> stringVector(10, "hello");

    for (auto it = begin(stringVector); it != end(stringVector); ++it) {
        it->append(" there");
        cout << *it << endl;
    }

    // 범위 기반 for문을 사용한 버전
    for (auto& str : stringVector) {
        str.append(" there");
        cout << str << endl;
    }

    return 0;
}

const_iterator

• 반복자는 대개 읽기와 쓰기가 가능하다. 하지만, 안정성 면에서는 보장을 할 수 없다.
• 따라서 읽기 전용인 const_iterator를 사면 보다 안정성면에서는 좋다.
• iterator는 const_iterator로 변환이 가능하지만 그 반대는 컴파일 에러가 발생한다.
• vector의 원소를 수정할 필요가 없다면 const_iterator를 사용하여 코드의 성능을 최적화해보자!

 

반복자의 안전성

• 다음과 같은 예시는 안전성이 매우 떨어진다.

vector<int> intVector;
auto iter = end(intVector);
*iter = 10; // 버그, iter가 벡터의 원소를 가리키고 있지 않음

• end()가 리턴하는 반복자는 vector의 마지막 원소가 아니라 그다음 원소를 가리킨다!
• 또 다른 문제로는 반복자가 서로 일치하지 않을 때 발생하는 문제도 있다.

 

#include <vector>

using namespace std;

int main()
{
    vector<int> vectorOne(10);
    vector<int> vectorTwo(10);

    // 벡터에 원소를 채운다.

    // 버그! 무한 루프에 빠질 수 있다.
    for (auto iter = begin(vectorTwo); iter != end(vectorOne); ++iter) {
        // 루프 본문
    }
    return 0;
}

 

반복자의 다른 연산

• 랜덤 액세스를 지원한다.

#include <vector>
using namespace std;

int main()
{
    vector<int> intVector(10);

    auto it = begin(intVector);
    it += 5;
    --it;
    *it = 4;

    return 0;
}

 

반복자의 인덱싱

• 다음 세 가지 경우에는 반복자를 사용하는 것이 유리하다.
  1. 시퀀스 컨테이너의 원하는 지점에 추가, 삭제하기 쉽다.
  2. 표준 라이브러리의 알고리즘을 사용하기 좋다.
  3. list, map, set에 대해서는 반복자를 사용하는 것이 항상 빠름.

 

vector에 레퍼런스 저장하기

• vector와 같은 컨테이너에 레퍼런스를 저장할 수도 있다.

#include <vector>
#include <string>
#include <functional>
#include <iostream>

using namespace std;

int main()
{
    string str1 = "Hello";
    string str2 = "World";

    // string에 대한 레퍼런스를 담은 vector를 생성한다.
    vector<reference_wrapper<string>> vec{ ref(str1) };
    vec.push_back(ref(str2));  // push_back()에도 적용할 수 있다.

    // 앞에서 만든 vector의 두 번째 원소(레퍼런스)가 참조하는 string 값을 변경한다.
    vec[1].get() += "!";

    // 최종 결과(변경된 str2 값)를 출력한다.
    cout << str1 << " " << str2 << endl;
}

 

원소 추가와 삭제

• push_back() 메서드 : 원소를 맨 뒤에 추가
• pop_back() 메서드 : 원소 삭제
• pop_back() 메서드는 삭제한 원소를 리턴하지 않는다. back() 메서드로 미리 받아두자.
• insert() 메서드 : 원하는 지점에 원소 추가
  • 원소 하나만 추가
  • 원소 하나에 대한 n개의 복제본 추가
  • 반복자의 범위로 지정된 원소들을 추가
  • 지정한 원소를 이동 의미론을 적용해서 vector에 이동시켜 추가
  • 원소 리스트를 initializer_list에 지정해서 vector에 추가
• erase() 메서드 : vector에 원소 중 원하는 것을 삭제
  • 반복자 하나를 인수로 받아 원소 하나만 삭제하는 version.
  • 삭제할 원소의 범위를 지정하는 두 개의 반복자를 인수로 받아 삭제하는 version.

• clear() 메서드 : 원소 모두 삭제

// 인수를 두 개 받는 버전의 erase()와 세 가지 버전의 insert() 예시
#include <vector>
#include <iostream>

using namespace std;

template<typename T>
void printVector(const vector<T>& v)
{
    for (auto& element : v)
    {
        cout << element << " ";
    }
    cout << endl;
}

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

    // 앞에서 vectorOne을 초기화할 때 깜박 잊고 넣지 않은 4를 여기서 추가한다.
    vectorOne.insert(cbegin(vectorOne) + 3, 4);

    // vectorTwo에 6부터 10까지의 원소를 추가한다.
    for (int i = 6; i <= 10; i++) {
        vectorTwo.push_back(i);
    }

    printVector(vectorOne);
    printVector(vectorTwo);

    // vectorTwo의 원소를 모두 vectorOne 뒤에 추가한다.
    vectorOne.insert(cend(vectorOne), cbegin(vectorTwo), cend(vectorTwo));
    printVector(vectorOne);

    // vectorOne에서 2부터 5까지 삭제한다.
    vectorOne.erase(cbegin(vectorOne) + 1, cbegin(vectorOne) + 5);
    printVector(vectorOne);

    // vectorTwo를 완전히 비운다.
    vectorTwo.clear();

    // 100에 대한 복제본 10개를 추가한다.
    vectorTwo.insert(cbegin(vectorTwo), 10, 100);

    // 마지막 원소를 제거해서 원소를 9개만 남긴다.
    vectorTwo.pop_back();
    printVector(vectorTwo);

    return 0;
}

 

이동 의미론

• 이동 의미론 덕분에 표준 라이브러리 컨테이너를 함수에서 값으로 리턴해도 성능 오버헤드를 최소화할 수 있다.

#include <cstddef>
#include <vector>

using namespace std;

vector<int> createVectorOfSize(size_t size)
{
    vector<int> vec(size);
    int contents = 0;
    for (auto& i : vec) {
        i = contents++;
    }
    return vec;
}

int main()
{
    vector<int> myVector;
    // 이동 의미론을 지원하므로 이동 대입 연산자를 호출함.
    myVector = createVectorOfSize(123);
    return 0;
}

 

임플레이스 연산

• 특정한 지점에 설치를 한다는 의미
• emplace_back() 메서드로 복제나 이동 작업을 수행하지 않고, 컨테이너에 공간을 마련하여 객체를 그 자리에 바로 생성

vec.emplace_back(5, 'a');

 

알고리즘 복잡도와 반복자 무효화

• vector에서 원소의 추가와 삭제 연산의 복잡도는 선형 시간이다.
• 내부에서 공간 재할당이 발생하면 추가 or 삭제 대상이 되는 원소를 가리키는 반복자뿐만 아니라
• 기존 반복자들도 모두 무효가 된다.

vector의 메모리 할당 방식

• vector에 원소를 추가하면 자동으로 메모리가 할당된다.
• 추상화 원칙에 따라 vector의 내부 메모리 할당 방식을 알 필요가 없지만
  1. 효율성 : 재할당이 발생하면 선형 시간의 복잡도를 가질 수 있다.
  2. 반복자 무효화 : 메모리 재할당 시, 기존의 반복자들이 모두 무효화됨
• 위의 두 이유 때문에 이러한 메커니즘을 알아둘 필요가 있다.

크기와 용량

• 크기에 대한 정보를 알려주는 메서드
• size() 메서드 : 원소의 개수 (벡터 크기)
• capacity() 메서드 : 재할당 없이 담을 수 있는 원소의 개수
• 현 상태에서 재할당 없이 추가할 수 있는 원소의 개수는 capacity() - size()이다.

예비 용량

• 공간을 미리 확보하기 위한 방법
  1. reserve() 메서드 호출하기 : 지정한 수의 원소를 충분히 담을 만큼의 공간 할당
  2. vector에 담길 원소 수를 vector 생성자나 resize() or assign() 메서드로 지정 : 원하는 크기의 vector 생성, 용량도 적절히 설정

데이터에 직접 접근하기

• data() 메서드 : vector에 데이터가 있는 메모리 블록에 대한 포인터를 구할 수 있다.

vector<int> vec { 1, 2, 3 };
int* data1 = vec.data();
int* data2 = data(vec);