C++

std::vector에서 size, capacity의 차이점은 무엇일까?

, ,

std::vector, std::string에서는 길이 리턴이 가능하다. string에서는 length, size모두 사용 가능하며, vector에서는 size를 사용하면 되겠다. 그런데 갑자기 인텔리센스(자도완성)에서 보이는 capacity… size와 차이가 무엇일까?

size와 capacity

size and capacity
위 그림과 같이, capacity는 vector의 type 또는 string의 각 character type들을 담을 수 있는 메모리가 할당되어 있는 공간의 용량이다.
보통, capacity는 현재 가지고 있는 원소의 개수(size, length)보다 더 많은 공간을 할당해 놓고 있다.
일반적으로 string에서는 8bytes를 미리 확보하고, 그보다 length가 더 길다면 32bytes, … 순으로 증가하는 것으로 보인다(이는 컴퓨터 구조, os등에 따라 차이가 보여질 수 있다).

따라서, 새로운 원소를 추가할 때(push_back) capacity가 size보다 크다면, O(1)로 새로운 원소를 추가하거나 지울 수 있게 된다.


하지만 할당한 공간(capacity)를 다 채우게 되면 새로운 연속된 공간을 다시 할당하여 기존의 원소들을 모두 복사해야 한다. 결국 O(n)으로 수행된다.

즉, 새로운 원소를 추가할 때

  1. capacity > size
    맨 뒤 공간에 원소를 복사한 뒤 ++size만 일어난다. (O(1))
  2. capacity == size
    capacity가 증가한 새로운 연속된 공간을 할당하고, 기존의 원소를 모두 복사하고 기존 정보는 지운다. capacity > size인 상황으로 만든 후 1번 과정을 다시 진행한다. (O(n))

resize와 reserve

위에서 보았듯이, reserve에서는 capacity를 우리가 원하는 크기로 할당 가능하게 한다.

resize는 원하는 수 만큼 원소를 생성한다. 또한 증가되는 size만큼 복사 생성자가 호출된다는 점이 있다(In c++11).

example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <string>

void* operator new(std::size_t count) {
	std::cout << count << " bytes 할당" << std::endl;
	return malloc(count);
}

bool contains_easy(const std::string& str) {
	return str.find("easy") != std::string::npos;
}

int main() {
	std::cout << contains_easy("Test word") << std::endl;
	std::cout << contains_easy("c++ string is not easy to use") << std::endl;
}

위의 예제에서 “Test word”와 “c++ string is not easy to use”에서 출력되는 결과는 다음과 같다.

1
2
3
4
5
8 bytes 할당
0
8 bytes 할당
32 bytes 할당
1

실제로 8bytes를 기본으로 capacity로 할당하고 있으나, 그 이상으로 string의 size가 넘어갈 시에 32bytes로 재할당시키는 것을 볼 수 있다.

Reference

  1. https://en.cppreference.com/w/cpp/container/vector/capacity
  2. https://en.cppreference.com/w/cpp/container/vector/size
Share