C++ 08.11 - std::vector의 capacity 및 stack 동작

08.11 - std::vector의 capacity 및 stack 동작

이전 포스트 2018/07/31 - C++ 07.22 - std::vector 소개에서 std::vector가 동적 배열이라는 것을 이야기했다.

std::vector는 가장 유용하게 많이 사용되므로 다른 속성과 기능에 대해서 좀 더 이야기해보자.

---

Length vs. Capacity

int* array = new int[10] { 1, 2, 3, 4, 5 };

위 예제 코드는 요소 5개만 할당하였어도 배열의 길이는 10이라고 말할 수 있다.

초기화한 요소만 사용하고, 사용하지 않는 요소들을 미래에 확장하기 위해 남겨두기 위해서는 어떻게 해야 할까? 위 예제에서는 할당된 요소 수에서 "사용하는" 요소 수를 별도로 기억해야 한다.

int* array = new int[10] { 1, 2, 3, 4, 5 }; // 미래에 확장 위해 10개로 미리 잡아놓는다.
int length = 5; // 사용하는 요소 수

for(int i = 0; i < length; ++i)
{
    // ...
}

길이만 기억하는 내장 배열이나 std::array와 달리 std::vector에는 length와 capacity의 두 가지 속성이 있다. length는 배열에서 사용되는 요소의 수이며, capacity는 메모리에 할당된 용량의 크기다.

int main()
{
    std::vector<int> array { 0, 1, 2 };
    array.resize(5); // set length to 5

    std::cout << "The length is: " << array.size() << '\n';

    for (auto const &element: array)
        std::cout << element << ' ';

    return 0;
};
/* The length is: 5
   0 1 2 0 0      */

위 예제 코드는 resize() 함수를 사용해서 벡터의 길이를 5로 지정했다. 이는 배열에 처음 5개 요소를 사용한다는 것을 알린다. 그렇다면 이 배열의 용량은 얼마일까? capacity() 함수를 통해 용량을 알 수 있다.

int main()
{
    std::vector<int> array { 0, 1, 2 };
    array.resize(5); // set length to 5

    std::cout << "The length is: " << array.size() << '\n';
    std::cout << "The capacity is: " << array.capacity() << '\n';
}

/* The length is: 5
   The capacity is: 5 */

위에서 resize() 함수는 std::vector의 길이(length)와 용량(capacity)을 모두 변경했다. 용량은 항상 길이보다 크거나 같다.

---

More Length vs. Capacity

왜 길이(length)와 용량(capacity)을 구별할까? std::vector가 메모리를 재할당하기 때문이다. 배열의 크기를 조정하는 것은 비용이 크기 때문에 될 수 있으면 피하는 게 좋다. 다음 예제를 보자:

int main()
{
    std::vector<int> array;
    array = { 0, 1, 2, 3, 4 }; // okay, array length = 5
    std::cout << "length: " << array.size() << "  capacity: " << array.capacity() << '\n';

    array = { 9, 8, 7 }; // okay, array length is now 3!
    std::cout << "length: " << array.size() << "  capacity: " << array.capacity() << '\n';

    return 0;
}

/* length: 5  capacity: 5
   length: 3  capacity: 5 */

벡터에 더 작은 배열을 할당했지만, 메모리를 재할당하지 않았다. (용량이 여전히 5다.) 단순히 길이를 변경했으므로 처음 세 요소만이 현재 유효하다는 것을 알 수 있다.

---

용량이 아닌 길이를 기준으로 한다.

배열의 첨자 연산자([]) 및 at() 함수의 범위는 용량이 아닌 길이를 기준으로 한다. 앞의 예제에서 길이 3과 용량 5의 배열을 고려할 때, 인덱스 4로 배열 요소에 접근하려고 하면 4가 배열 길이보다 크기 때문에 실패한다.

---

std::vector로 stack 동작

std::vector는 동적 배열이지만 스택(stack)처럼 동작할 수 있다. 이를 위해 다음 3가지 함수를 사용한다.

• push_back : 스택의 요소를 푸시한다.
• back() : 스택의 최상위 값을 반환한다.
• pop_back() : 스택에서 요소를 팝한다.

void printStack(const std::vector<int> &stack)
{
    for (const auto &element : stack)
        std::cout << element << ' ';
    std::cout << "(cap " << stack.capacity() << " length " << stack.size() << ")\n";
}

int main()
{
    std::vector<int> stack;

    printStack(stack);

    stack.push_back(5); // push_back() pushes an element on the stack
    printStack(stack);

    stack.push_back(3);
    printStack(stack);

    stack.push_back(2);
    printStack(stack);

    std::cout << "top: " << stack.back() << '\n'; // back() returns the last element

    stack.pop_back(); // pop_back() back pops an element off the stack
    printStack(stack);

    stack.pop_back();
    printStack(stack);

    stack.pop_back();
    printStack(stack);

    return 0;
}
/*
(cap 0 length 0)
5 (cap 1 length 1)
5 3 (cap 2 length 2)
5 3 2 (cap 3 length 3)
top: 2
5 3 (cap 3 length 2)
5 (cap 3 length 1)
(cap 3 length 0) */

함수가 호출될 때 필요한 경우 벡터의 용량이 자동 조정된다. 위 예제에서는 3번 조정되었다. 벡터의 용량이 조정되는 것은 메모리를 재할당하는 동작이므로 비용이 크다. 그러므로 벡터에 일정량의 용량을 미리 할당함으로써 성능 향상을 꾀할 수 있다.

void printStack(const std::vector<int> &stack)
{
    for (const auto &element : stack)
        std::cout << element << ' ';
    std::cout << "(cap " << stack.capacity() << " length " << stack.size() << ")\n";
}

int main()
{
    std::vector<int> stack;

    stack.reserve(5); // Set the capacity to (at least) 5

    printStack(stack);

    stack.push_back(5);
    printStack(stack);

    stack.push_back(3);
    printStack(stack);

    stack.push_back(2);
    printStack(stack);

    std::cout << "top: " << stack.back() << '\n';

    stack.pop_back();
    printStack(stack);

    stack.pop_back();
    printStack(stack);

    stack.pop_back();
    printStack(stack);

    return 0;
}
/* 
(cap 5 length 0)
5 (cap 5 length 1)
5 3 (cap 5 length 2)
5 3 2 (cap 5 length 3)
top: 2
5 3 (cap 5 length 2)
5 (cap 5 length 1)
(cap 5 length 0) */

용량을 미리 5로 설정함으로써 프로그램이 실행되는 동안 메모리 재할당이 일어나지 않았다.

---

 번역: 이 포스트의 원문은 https://www.learncpp.com/cpp-tutorial/7-10-stdvector-capacity-and-stack-behavior/ 입니다.