Data Structure/C++ STL

[C++ STL] 1.3 std::vector

lumana 2024. 6. 14. 00:13

std::vector

std::array의 단점

  • std::array의 크기는 컴파일 시간에 결정되는 상수이어야 한다.
    • 런타임 중에 변경할 수 없다.
  • 크기가 고정되어 있어서 원소를 추가/삭제할 수 없다.
  • 항상 스택 메모리를 사용한다. 메모리 할당 방법을 바꿀 수 없다

따라서 가변 크기의 데이터를 처리할 수 있는 컨테이너가 필요하다 --> std::vector

std::vector - 가변 크기 배열

  • 배열 기반으로 구현되어 있다
  • 초기화 과정에서 데이터의 크기를 제공하지 않아도 된다
  • std:array의 '고정 크기' 문제를 해결한다

벡터를 초기화 하는 몇 가지 방법

// 크기가 0인 벡터 선언
std::vector<int> vec;

// 지정한 초깃값으로 이루어진 크기가 5인 벡터 선언
std::vector<int> vec = { 1, 2, 3, 4, 5 };

// 크기가 10인 벡터 선언
std::vector<int> vec(10);

// 크기가 10이고 모든 원소가 5로 초기화된 벡터 선언
std::vector<int> vec(10, 5);
  • 크기를 명시적으로 지정하지 않거나 초깃값을 지정하여 크기를 유추할 수 있게 코드를 작성하지 않을 경우, 컴파일러 구현 방법에 따른 capacity를 갖는 벡터가 생성된다.
    • vector의 size는 벡터에 실제로 저장된 원소 개수를 나타내는 용어
    • capacity는 size와 다른 의미. (vector의 data를 저장하기 위해 메모리에 할당된 공간의 크기라고 생각하면 된다)

벡터에 새로운 원소 추가

  • 벡터에 새로운 원소를 추가하려면 push_back() 또는 insert() 함수를 사용한다.
push_back(val):
    if size < capacity // 새 원소를 추가할 공간이 있는 경우
    - 마지막 원소 다음에 val 저장
    - vector size를 1만큼 증가
    - return;

    if vector is already full // 할당된 메모리 고간이 가득 차 있는 경우
    - 2*size 크기의 메모리를 새로 할당
    - 새로 할당한 메모리로 기존 원소 전부를 복사/이동
    - 데이터 포인터를 새로 할당한 메모리 주소로 지정
    - 마지막 원소 다음에 val을 저장하고, 벡터 크기를 1만큼 증가
  • push_back() 함수는 벡터의 맨 마지막에 새로운 원소를 추가한다.
    • 따라서 속도가 매우 빠름
    • 뒤쪽에 남아 있는 공간이 있다면 O(1)
    • 공간이 충분하지 않다면 O(n)
    • 용량을 늘리는 경우는 많지 않으므로 평균 시간 복잡도는 O(1)
  • insert() 함수는 삽입할 위치를 나타내는 반복자를 첫 번째 인자로 받음으로써 원하는 위치에 추가한다.
    • 지정한 반복자 위치 다음의 모든 원소를 이동시키는 연산이 필요함
    • 필요한 경우 메모리를 새로 할당하는 작업도 수행된다
    • 원소들을 이동하는 연산 때문에 O(n) 시간이 걸린다
  • example
// 비어 있는 벡터 생성
std::vector<int> vec;

// 맨 뒤에 1 추가: {1}
vec.push_back(1);

// 맨 뒤에 2 추가: {1, 2}
vec.push_back(2); 

// 맨 앞에 0 추가: {0, 1, 2}
vec.insert(vec.begin(), 0);

// 1 앞에 4 추가 {0, 4, 1, 2}
vec.insert(find(vec.begin(), vec.end(), 1), 4);

효율적인 원소 추가 방법

  • push_back(), insert() 함수의 단점
    • 이들 함수가 추가할 원소를 먼저 임시로 생성한 후, 벡터 버퍼 내부 위치로 복사 또는 이동을 수행함
  • 이 단점을 새로운 원소가 추가될 위치에서 해당 원소를 생성하는 방식으로 최적화할 수 있다.
    • emplace_back(), emplace() 함수에 구현되어 있음
      • 위 함수를 사용하는 것이 성능 향상에 도움이 된다
      • 이 경우 생성된 객체를 전달하는 것이 아니라, 생성자에 필요한 매개변수를 전달해야 한다

벡터에서 원소 제거

  • std::vector는 원소 제거를 위해 pop_back()과 erase() 함수를 제공
  • pop_back()
    • 벡터에서 맨 마지막 원소를 제거하며, 벡터 크기는 1만큼 감소
    • 남아 있는 위치를 조정할 필요가 없으므로 매우 빠름. O(1)
  • erase()
    • 두 가지 형태의 오버로딩
      • (1) 반복자 하나를 인자로 받아 해당 위치 원소를 제거
      • (2) 범위의 시작과 끝을 나나태는 반복자를 받아 시작부터 끝 바로 앞 원소까지 제거
        • 즉 시작 위치 원소는 제거되지만, 끝 위치 원소는 제거되지 않음
    • 특정 위치 원소를 삭제한 후, 뒤쪽의 원소들을 모두 앞쪽으로 이동해야 함
    • O(n) 시간 소요
// 10개의 데이터를 가지고 잇는 벡터 선언
std::vector<int> vec = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

// 맨 마지막 원소 제거: { 0, 1, 2, 3, 4, 5, 6, 7, 8 }
vec.pop_back();

// 맨 처음 원소 제거 { 1, 2, 3, 4, 5, 6, 7, 8 }
vec.erase(vec.begin());

// 1번째 원소부터 4번째 앞 원소까지 제거 { 1, 5, 6, 7, 8 }
vec.erase(vec.begin() + 1, vec.begin() + 4);

유용한 std::vector 멤버 함수

  • clear() : 모든 원소를 제거하여 완전히 비어 있는 벡터로 만든다
  • reverse(capacity) : 벡터에서 사용할 용량을 지정
    • 지정한 값이 현재 용량보다 크면 메모리를 매개변수 크기만큼 재할당
  • shrink_to_fit() : 여분의 메모리 공간을 해제하는 용도로 사용
    • 벡터 크기가 더 이상 변겨되지 않을 때 사용하면 유용하다

std::vector 할당자

  • 템플릿 매개변수에서 데이터 타입 다음에 allocator(할당자)를 전달할 수 있다.
    • 사실 std::vector의 정의를 봐보면, 타입 매개변수로 데이터 타입과 allocator가 하나 더 사용된다
  • 사용자 정의 할당자를 사용하려면 정해진 인터페이스를 따라야 한다.
  • 벡터는 메모리 접근과 관련된 대부분의 동작에서 할당자 함수를 사용하므로 할당자는 다음의 함수 등을 제공해야 한다.
    • allocate()
    • deallocate()
    • construct()
    • destroy()
  • 힙 메모리 대신 자체적인 메모리 풀 또는 이와 유사한 자원을 사용하거나, 자동 메모리 관리가 필요한 application을 만들어야 하는 경우 유용하다

allocator란?

  • 유연한 메모리 관리를 위한 클래스
  • 메모리 동적 할당/해제를 할 때 new/delete 연산자를 사용함
    • allocator를 사용하면 유저가 원하는 메모리 할당 방식으로 구현할 수 있음
    • allocator 클래스를 상속받아 멤버함수를 override하여 커스텀할 수 있다

new/delete 연산자의 단점

  • 다음 3가지 과정을 반드시 거쳐야 함
  1. 기본 생성자 필요
  2. 메모리 할당
  3. 모든 요소 초기화
  • 라이브러리 개발자가 원하는 메모리 할당 방식으로 커스터마이징 할 수 없음

allocator의 장점

  • allocator 클래스를 사용하면 위 3가지 단계를 각각 원할 때 사용할 수가 있다.
  • 초기화되지 않은 공간(uninitialized)으로 메모리를 allocate 할 수 있다.
    • new 연산자의 경우 메모리를 할당하고 기본적으로 값 또는 객체를 의무적으로 초기화 해줌
    • int a = 3;을 int a = 0; a = 3 두 번의 과정을 거치고 있는 것
    • allocator의 멤버 함수를 사용하면 메모리의 할당은 되었지만 초기화 되지 않은 상태의 메모리의 시작 주소를 얻을 수 있다.
  • 할당받은 메모리에 객체를 생성 후 메모리 해제(deallocate)없이 생성한 객체들을 소멸(destroy)시킬 수 있다.
    • new 연산자로 할당한 메모리 공간은 delete를 사용하면 메모리 공간이 해제가 되는 것을 생각해보자
    • deallocate 후 destory 해야하는 과정을 분리했다고 생각하면 된다
  • 할당받은 메모리 공간 중 객체가 생성된 공간과 아직 초기화되지 않은 공간을 알 수 있는 방법을 제공함

Specification

template <class T>
class allocator
{
public:
   T* allocate(size_t);
   void deallocate(T*, size_t);
   void construct(T*, const T&);
   void destory(T*);

   ....
};

template <class In, class For>
For uninitialized_copy(In, In, For);

template <class For, class T>
void uninitialized_fill(For, For, const T&);
  • allocate 함수 : 초기화되지 않은 메모리 공간을 할당하여 그 시작 주소를 반환
  • deallocate 함수 : 메모리 공간을 해제
  • construct 함수는 초기화되지 않은 공간에 요소를 저장
  • destroy 함수는 객체를 소멸

참고) https://woo-dev.tistory.com/51

std::vector

std::array의 단점

  • std::array의 크기는 컴파일 시간에 결정되는 상수이어야 한다.
    • 런타임 중에 변경할 수 없다.
  • 크기가 고정되어 있어서 원소를 추가/삭제할 수 없다.
  • 항상 스택 메모리를 사용한다. 메모리 할당 방법을 바꿀 수 없다

따라서 가변 크기의 데이터를 처리할 수 있는 컨테이너가 필요하다 --> std::vector

std::vector - 가변 크기 배열

  • 배열 기반으로 구현되어 있다
  • 초기화 과정에서 데이터의 크기를 제공하지 않아도 된다
  • std:array의 '고정 크기' 문제를 해결한다

벡터를 초기화 하는 몇 가지 방법

// 크기가 0인 벡터 선언
std::vector<int> vec;

// 지정한 초깃값으로 이루어진 크기가 5인 벡터 선언
std::vector<int> vec = { 1, 2, 3, 4, 5 };

// 크기가 10인 벡터 선언
std::vector<int> vec(10);

// 크기가 10이고 모든 원소가 5로 초기화된 벡터 선언
std::vector<int> vec(10, 5);
  • 크기를 명시적으로 지정하지 않거나 초깃값을 지정하여 크기를 유추할 수 있게 코드를 작성하지 않을 경우, 컴파일러 구현 방법에 따른 capacity를 갖는 벡터가 생성된다.
    • vector의 size는 벡터에 실제로 저장된 원소 개수를 나타내는 용어
    • capacity는 size와 다른 의미. (vector의 data를 저장하기 위해 메모리에 할당된 공간의 크기라고 생각하면 된다)

벡터에 새로운 원소 추가

  • 벡터에 새로운 원소를 추가하려면 push_back() 또는 insert() 함수를 사용한다.
push_back(val):
    if size < capacity // 새 원소를 추가할 공간이 있는 경우
    - 마지막 원소 다음에 val 저장
    - vector size를 1만큼 증가
    - return;

    if vector is already full // 할당된 메모리 고간이 가득 차 있는 경우
    - 2*size 크기의 메모리를 새로 할당
    - 새로 할당한 메모리로 기존 원소 전부를 복사/이동
    - 데이터 포인터를 새로 할당한 메모리 주소로 지정
    - 마지막 원소 다음에 val을 저장하고, 벡터 크기를 1만큼 증가
  • push_back() 함수는 벡터의 맨 마지막에 새로운 원소를 추가한다.
    • 따라서 속도가 매우 빠름
    • 뒤쪽에 남아 있는 공간이 있다면 O(1)
    • 공간이 충분하지 않다면 O(n)
    • 용량을 늘리는 경우는 많지 않으므로 평균 시간 복잡도는 O(1)
  • insert() 함수는 삽입할 위치를 나타내는 반복자를 첫 번째 인자로 받음으로써 원하는 위치에 추가한다.
    • 지정한 반복자 위치 다음의 모든 원소를 이동시키는 연산이 필요함
    • 필요한 경우 메모리를 새로 할당하는 작업도 수행된다
    • 원소들을 이동하는 연산 때문에 O(n) 시간이 걸린다
  • example
// 비어 있는 벡터 생성
std::vector<int> vec;

// 맨 뒤에 1 추가: {1}
vec.push_back(1);

// 맨 뒤에 2 추가: {1, 2}
vec.push_back(2); 

// 맨 앞에 0 추가: {0, 1, 2}
vec.insert(vec.begin(), 0);

// 1 앞에 4 추가 {0, 4, 1, 2}
vec.insert(find(vec.begin(), vec.end(), 1), 4);

효율적인 원소 추가 방법

  • push_back(), insert() 함수의 단점
    • 이들 함수가 추가할 원소를 먼저 임시로 생성한 후, 벡터 버퍼 내부 위치로 복사 또는 이동을 수행함
  • 이 단점을 새로운 원소가 추가될 위치에서 해당 원소를 생성하는 방식으로 최적화할 수 있다.
    • emplace_back(), emplace() 함수에 구현되어 있음
      • 위 함수를 사용하는 것이 성능 향상에 도움이 된다
      • 이 경우 생성된 객체를 전달하는 것이 아니라, 생성자에 필요한 매개변수를 전달해야 한다

벡터에서 원소 제거

  • std::vector는 원소 제거를 위해 pop_back()과 erase() 함수를 제공
  • pop_back()
    • 벡터에서 맨 마지막 원소를 제거하며, 벡터 크기는 1만큼 감소
    • 남아 있는 위치를 조정할 필요가 없으므로 매우 빠름. O(1)
  • erase()
    • 두 가지 형태의 오버로딩
      • (1) 반복자 하나를 인자로 받아 해당 위치 원소를 제거
      • (2) 범위의 시작과 끝을 나나태는 반복자를 받아 시작부터 끝 바로 앞 원소까지 제거
        • 즉 시작 위치 원소는 제거되지만, 끝 위치 원소는 제거되지 않음
    • 특정 위치 원소를 삭제한 후, 뒤쪽의 원소들을 모두 앞쪽으로 이동해야 함
    • O(n) 시간 소요
// 10개의 데이터를 가지고 잇는 벡터 선언
std::vector<int> vec = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

// 맨 마지막 원소 제거: { 0, 1, 2, 3, 4, 5, 6, 7, 8 }
vec.pop_back();

// 맨 처음 원소 제거 { 1, 2, 3, 4, 5, 6, 7, 8 }
vec.erase(vec.begin());

// 1번째 원소부터 4번째 앞 원소까지 제거 { 1, 5, 6, 7, 8 }
vec.erase(vec.begin() + 1, vec.begin() + 4);

유용한 std::vector 멤버 함수

  • clear() : 모든 원소를 제거하여 완전히 비어 있는 벡터로 만든다
  • reverse(capacity) : 벡터에서 사용할 용량을 지정
    • 지정한 값이 현재 용량보다 크면 메모리를 매개변수 크기만큼 재할당
  • shrink_to_fit() : 여분의 메모리 공간을 해제하는 용도로 사용
    • 벡터 크기가 더 이상 변겨되지 않을 때 사용하면 유용하다

std::vector 할당자

  • 템플릿 매개변수에서 데이터 타입 다음에 allocator(할당자)를 전달할 수 있다.
    • 사실 std::vector의 정의를 봐보면, 타입 매개변수로 데이터 타입과 allocator가 하나 더 사용된다
  • 사용자 정의 할당자를 사용하려면 정해진 인터페이스를 따라야 한다.
  • 벡터는 메모리 접근과 관련된 대부분의 동작에서 할당자 함수를 사용하므로 할당자는 다음의 함수 등을 제공해야 한다.
    • allocate()
    • deallocate()
    • construct()
    • destroy()
  • 힙 메모리 대신 자체적인 메모리 풀 또는 이와 유사한 자원을 사용하거나, 자동 메모리 관리가 필요한 application을 만들어야 하는 경우 유용하다

allocator란?

  • 유연한 메모리 관리를 위한 클래스
  • 메모리 동적 할당/해제를 할 때 new/delete 연산자를 사용함
    • allocator를 사용하면 유저가 원하는 메모리 할당 방식으로 구현할 수 있음
    • allocator 클래스를 상속받아 멤버함수를 override하여 커스텀할 수 있다

new/delete 연산자의 단점

  • 다음 3가지 과정을 반드시 거쳐야 함
  1. 기본 생성자 필요
  2. 메모리 할당
  3. 모든 요소 초기화
  • 라이브러리 개발자가 원하는 메모리 할당 방식으로 커스터마이징 할 수 없음

allocator의 장점

  • allocator 클래스를 사용하면 위 3가지 단계를 각각 원할 때 사용할 수가 있다.
  • 초기화되지 않은 공간(uninitialized)으로 메모리를 allocate 할 수 있다.
    • new 연산자의 경우 메모리를 할당하고 기본적으로 값 또는 객체를 의무적으로 초기화 해줌
    • int a = 3;을 int a = 0; a = 3 두 번의 과정을 거치고 있는 것
    • allocator의 멤버 함수를 사용하면 메모리의 할당은 되었지만 초기화 되지 않은 상태의 메모리의 시작 주소를 얻을 수 있다.
  • 할당받은 메모리에 객체를 생성 후 메모리 해제(deallocate)없이 생성한 객체들을 소멸(destroy)시킬 수 있다.
    • new 연산자로 할당한 메모리 공간은 delete를 사용하면 메모리 공간이 해제가 되는 것을 생각해보자
    • deallocate 후 destory 해야하는 과정을 분리했다고 생각하면 된다
  • 할당받은 메모리 공간 중 객체가 생성된 공간과 아직 초기화되지 않은 공간을 알 수 있는 방법을 제공함

Specification

template <class T>
class allocator
{
public:
   T* allocate(size_t);
   void deallocate(T*, size_t);
   void construct(T*, const T&);
   void destory(T*);

   ....
};

template <class In, class For>
For uninitialized_copy(In, In, For);

template <class For, class T>
void uninitialized_fill(For, For, const T&);
  • allocate 함수 : 초기화되지 않은 메모리 공간을 할당하여 그 시작 주소를 반환
  • deallocate 함수 : 메모리 공간을 해제
  • construct 함수는 초기화되지 않은 공간에 요소를 저장
  • destroy 함수는 객체를 소멸

참고) https://woo-dev.tistory.com/51

'Data Structure > C++ STL' 카테고리의 다른 글

[C++ STL] 1.6 std::list  (0) 2024.06.15
[C++ STL] 1.5 Iterator(반복자)  (0) 2024.06.15
[C++ STL] 1.4 std::forward_list  (0) 2024.06.14
[C++ STL] 1.2 std::array  (0) 2024.06.13
[C++ 자료구조] 1.1 연속된 자료 구조와 연결된 자료 구조  (0) 2024.06.13

'Data Structure/C++ STL'의 다른글

  • 현재글[C++ STL] 1.3 std::vector

관련글

티스토리툴바