std::vector vs std::list

1. std::vector

std::vector는 동적으로 크기가 조절되는 배열이다. C-스타일 배열과 유사하게, 메모리 상에 연속된 공간에 원소들을 저장한다.

1.1. 내부 구조 및 구현

std::vector는 일반적으로 세 개의 포인터(또는 포인터와 정수)로 구현된다.

• begin: 할당된 메모리 블록의 시작을 가리키는 포인터.
• end: 마지막 원소 바로 다음 위치를 가리키는 포인터. (end - begin은 현재 저장된 원소의 개수, 즉 size()가 된다.)
• capacity: 할당된 총 메모리 공간의 끝을 가리키는 포인터. (capacity - begin은 재할당 없이 저장할 수 있는 총 원소의 수, 즉 capacity()가 된다.)

메모리:
[elem1][elem2][elem3][ ... ][elemN][ (unused) ][ (unused) ]
^                                  ^                        ^
|                                  |                        |
begin                              end                      capacity

1.2. 동작 방식

• 원소 접근: operator[] 또는 at()을 통해 특정 인덱스의 원소에 접근한다. 포인터 연산(begin + index)을 통해 O(1)의 시간 복잡도로 매우 빠르게 접근할 수 있다. 이는 데이터가 메모리에 연속적으로 위치하기 때문에 가능하다.
• 삽입/삭제:
  • 끝에서의 삽입 (push_back): size가 capacity보다 작으면, end 위치에 원소를 생성하고 end를 1 증가시킨다. 이 과정은 O(1)입니다. 하지만 size가 capacity와 같아지면 재할당(reallocation)이 발생한다.
    1. 현재 capacity보다 큰 (보통 1.5배 또는 2배) 새로운 메모리 블록을 할당한다.
    2. 기존의 모든 원소를 새로운 메모리 블록으로 이동(move) 또는 복사(copy)한다.
    3. 기존 메모리 블록을 해제합니다.
    4. begin, end, capacity 포인터를 갱신한다.
       재할당 과정 자체는 O(n)의 비용이 들지만, 이러한 비용이 드물게 발생하도록 capacity를 지수적으로 증가시키기 때문에, push_back의 평균 시간 복잡도는 분할 상환 시간 복잡도(Amortized O(1))가 된다.
  • 중간/처음에서의 삽입/삭제: 특정 위치에 원소를 삽입하거나 삭제하려면, 그 위치 뒤의 모든 원소를 한 칸씩 뒤로 밀거나 앞으로 당겨야 한다. 이는 O(n)의 시간 복잡도를 가진다.

1.3. 캐시 효율성 (Cache Locality)

vector의 가장 큰 장점 중 하나는 캐시 지역성(Cache Locality)이 매우 높다는 것이다. 데이터가 메모리에 연속적으로 모여 있기 때문에, 하나의 원소에 접근할 때 CPU는 해당 원소 주변의 데이터까지 함께 CPU 캐시(L1, L2, L3)로 가져온다. 따라서 순차적으로 원소를 순회할 때, 대부분의 데이터 접근이 RAM이 아닌 훨씬 빠른 캐시에서 처리(Cache Hit)된다. 대량의 데이터를 순회하는 연산에서 성능 이점을 제공한다.

 

2. std::list 상세 분석

std::list는 이중 연결 리스트(Doubly-linked List)로 구현된다. 각 원소는 노드(node)라는 별도의 메모리 공간에 저장되며, 이 노드들이 포인터를 통해 서로를 연결한다.

2.1. 내부 구조 및 구현

std::list의 각 노드는 보통 세 부분으로 구성된다.

• 데이터(Data): 실제 저장되는 원소.
• 다음 노드 포인터(Next Pointer): 다음 노드의 메모리 주소를 가리키는 포인터.
• 이전 노드 포인터(Previous Pointer): 이전 노드의 메모리 주소를 가리키는 포인터.

list 객체 자체는 맨 앞 노드와 맨 뒤 노드를 가리키는 포인터(head, tail)와 리스트의 크기(size)를 관리한다.

메모리:
[Node1] <-----> [Node2] <-----> [Node3] ... (각 노드는 메모리 여러 곳에 흩어져 있음)
  |               |               |
[prev|data|next] [prev|data|next] [prev|data|next]

2.2. 동작 방식

• 원소 접근: list는 operator[]를 제공하지 않는다. 특정 위치의 원소에 접근하려면 처음(또는 끝)에서부터 원하는 위치까지 포인터를 따라 순차적으로 이동해야 한다. O(n)
• 삽입/삭제: list의 가장 큰 장점입니다. 특정 위치를 가리키는 반복자(iterator)가 있다면, 해당 위치에서의 삽입/삭제는 O(1)의 시간 복잡도로 매우 빠르다.
  • 삽입: 새로운 노드를 생성하고, 삽입할 위치의 이전 노드와 다음 노드의 포인터만 수정하여 새 노드를 연결.
  • 삭제: 삭제할 노드의 이전 노드와 다음 노드가 서로를 가리키도록 포인터를 수정한 뒤, 해당 노드의 메모리를 해제.
    vector처럼 다른 원소들을 이동시킬 필요가 전혀 없다.

2.3. 캐시 비효율성

list의 각 노드는 동적 할당되므로 메모리 공간에 흩어져 있을 가능성이 높다. 따라서 리스트를 순회할 때마다 다음 노드의 주소를 따라가야 하는데, 이 주소는 현재 노드와 멀리 떨어져 있을 수 있다. 이로 인해 CPU 캐시의 이점을 거의 누리지 못하고, 매번 RAM에 접근해야 하는 Cache Miss가 발생할 확률이 높다. vector에 비해 순차 순회 성능이 현저히 떨어지는 주된 원인이다. 또한, 각 원소마다 2개의 포인터를 추가로 저장해야 하므로 메모리 오버헤드도 vector보다 크다.

 

3. 계층별 동작 비교 (vector.push_back(x) vs list.push_back(x))

계층	std::vector::push_back(x)	std::list::push_back(x)
사용자 영역	my_vector.push_back(x);	my_list.push_back(x);
C++ 라이브러리	1. size < capacity 확인. 2. (재할당 시) 새 메모리 할당, 원소 이동, 기존 메모리 해제. 3. end 위치에 x 생성 후 size 증가.	1. new Node(x)로 새 노드 동적 할당. 2. 기존 마지막 노드의 next 포인터가 새 노드를 가리키게 함. 3. 새 노드의 prev 포인터가 기존 마지막 노드를 가리키게 함. 4. list의 tail 포인터를 새 노드로 업데이트. 5. size 증가.
OS (커널 영역)	(재할당 시) mmap 또는 brk 같은 시스템 콜로 큰 메모리 청크 요청.	new 연산 시마다 malloc을 통해 작은 메모리 조각을 요청. 이는 내부적으로 OS의 힙 관리자를 호출.
하드웨어 (CPU/MMU)	연속된 메모리 접근으로 캐시 히트율 높음. 재할당 시 대규모 메모리 복사 발생.	포인터를 따라다니는 불연속적인 메모리 접근으로 캐시 미스율 높음.

 

4. 비교 요약 및 사용 사례

특징	std::vector	std::list
메모리 구조	연속된 메모리 (배열)	불연속적인 메모리 (노드)
임의 접근	O(1)	O(n)
중간 삽입/삭제	O(n)	O(1) (반복자 있을 시)
끝 삽입/삭제	분할 상환 O(1)	O(1)
메모리 오버헤드	낮음	높음 (원소당 포인터 2개)
캐시 지역성	매우 높음	매우 낮음
반복자 무효화	삽입/재할당 시 기존 반복자/포인터가 무효화될 수 있음	원소 삭제 시에만 해당 원소의 반복자가 무효화됨

언제 무엇을 써야 할까?

• std::vector를 사용해야 하는 경우:
  • 기본적인 선택지. 특별한 이유가 없다면 vector를 우선적으로 고려.
  • 원소에 대한 임의 접근(인덱싱)이 빈번하게 필요할 때.
  • 데이터 순회가 많고, 캐시 성능이 중요할 때 (대부분의 경우).
  • 컨테이너의 끝에서만 삽입/삭제가 주로 일어날 때.
• std::list를 사용해야 하는 경우:
  • 컨테이너의 중간에서 원소의 삽입/삭제가 매우 빈번하게 일어날 때.
  • 삽입/삭제 후에도 기존 원소를 가리키는 반복자나 포인터의 유효성이 보장되어야 할 때.
  • 임의 접근이 전혀 필요 없을 때.
  • (주의) list의 O(1) 삽입/삭제는 이론적인 장점이며, 실제로는 노드 할당 비용과 캐시 미스로 인해 vector의 O(n) 이동보다 느릴 수 있다. 데이터 크기가 작고 이동 비용이 클 때 list의 장점이 부각될 수 있다.

 

5. 요약

vector와 list는 둘 다 데이터를 순서대로 저장하는 도구인데, 내부적으로 동작하는 방식이 완전히 다릅니다.

vector는 데이터를 메모리에 차곡차곡 연속으로 쌓아두는 '배열' 같은 방식이라서, 특정 위치의 데이터를 한 번에 찾아가는 건(임의 접근) 아주 빠릅니다(O(1)). 그리고 데이터가 모여있어서 CPU 캐시가 좋아해 순차적으로 훑을 때도 성능이 좋습니다. 하지만 중간에 데이터를 끼워 넣거나 빼려면 그 뒤에 있는 모든 데이터를 밀거나 당겨야 해서 느려집니다(O(n)).

반면에 list는 데이터를 '노드'라는 상자에 하나씩 담고, 각 상자들이 이전-다음 상자를 가리키는 '포인터'로 연결된 '기차' 같은 구조입니다. 그래서 중간에 상자를 끼워 넣거나 빼는 건 포인터 몇 개만 바꾸면 되니까 아주 빠릅니다(O(1)). 하지만 특정 상자를 찾으려면 처음부터 하나씩 따라가야 해서 느리고(O(n)), 데이터들이 메모리에 흩어져 있어 캐시 효율도 나쁩니다.

결론적으로, 대부분의 상황에서는 캐시 효율이 좋고 접근이 빠른 vector를 쓰는 것이 좋습니다. list는 데이터의 중간 삽입/삭제가 극도로 빈번하고, 그로 인한 성능 저하가 다른 모든 이점을 압도할 만큼 심각한 아주 특별한 상황에서만 고려해볼 만한 선택지입니다.

 

6. 실습 코드

#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <chrono>
#include <numeric>

// 게임 아이템을 표현하는 구조체
struct Item {
    int id;
    std::string name;
    int quantity;

    Item(int i, std::string n, int q) : id(i), name(std::move(n)), quantity(q) {}
};

// 인벤토리를 출력하는 함수 (vector 버전)
void printInventory(const std::vector<Item>& inventory) {
    std::cout << "--- Vector Inventory ---" << std::endl;
    for (const auto& item : inventory) {
        std::cout << "ID: " << item.id << ", Name: " << item.name << ", Quantity: " << item.quantity << std::endl;
    }
    std::cout << "------------------------" << std::endl;
}

// 인벤토리를 출력하는 함수 (list 버전)
void printInventory(const std::list<Item>& inventory) {
    std::cout << "--- List Inventory ---" << std::endl;
    for (const auto& item : inventory) {
        std::cout << "ID: " << item.id << ", Name: " << item.name << ", Quantity: " << item.quantity << std::endl;
    }
    std::cout << "----------------------" << std::endl;
}

int main() {
    // 시뮬레이션에 사용할 아이템 개수
    const int NUM_ITEMS = 10000;

    // --- 1. Vector 시뮬레이션 ---
    std::cout << ">>> Starting Vector Simulation..." << std::endl;
    std::vector<Item> vectorInventory;
    
    // vector에 아이템을 순차적으로 추가 (push_back)
    auto start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < NUM_ITEMS; ++i) {
        // Q1. 이 루프에서 capacity가 변경될 때 어떤 일이 발생하며, 성능에 어떤 영향을 미칠까요?
        // 제출: 
        vectorInventory.push_back(Item(i, "Item " + std::to_string(i), 1));
    }
    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::milli> vector_add_duration = end - start;
    std::cout << "Vector push_back time: " << vector_add_duration.count() << " ms" << std::endl;

    // vector 중간에 아이템 삭제
    start = std::chrono::high_resolution_clock::now();
    for (auto it = vectorInventory.begin(); it != vectorInventory.end(); ) {
        if (it->id % 10 == 0) { // 10의 배수 ID를 가진 아이템 삭제
            // Q2. 여기서 원소를 삭제한 후, 반복자(iterator)를 계속 사용해도 안전할까요? 그 이유는 무엇인가요?
            // 제출: 
            it = vectorInventory.erase(it);
        } else {
            ++it;
        }
    }
    end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::milli> vector_erase_duration = end - start;
    std::cout << "Vector erase time: " << vector_erase_duration.count() << " ms" << std::endl;
    std::cout << "Final vector size: " << vectorInventory.size() << std::endl << std::endl;


    // --- 2. List 시뮬레이션 ---
    std::cout << ">>> Starting List Simulation..." << std::endl;
    std::list<Item> listInventory;

    // list에 아이템을 순차적으로 추가 (push_back)
    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < NUM_ITEMS; ++i) {
        // Q3. vector와 비교했을 때, 여기서 아이템을 추가하는 방식의 메모리 및 성능상 장단점은 무엇일까요?
        // 제출: 
        listInventory.push_back(Item(i, "Item " + std::to_string(i), 1));
    }
    end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::milli> list_add_duration = end - start;
    std::cout << "List push_back time: " << list_add_duration.count() << " ms" << std::endl;

    // list 중간에 아이템 삭제
    start = std::chrono::high_resolution_clock::now();
    for (auto it = listInventory.begin(); it != listInventory.end(); ) {
        if (it->id % 10 == 0) { // 10의 배수 ID를 가진 아이템 삭제
            // Q4. list에서 원소를 삭제하는 것이 vector보다 빠른 이유는 무엇이며, 삭제 후 반복자는 어떻게 될까요?
            // 제출: 
            it = listInventory.erase(it);
        } else {
            ++it;
        }
    }
    end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::milli> list_erase_duration = end - start;
    std::cout << "List erase time: " << list_erase_duration.count() << " ms" << std::endl;
    std::cout << "Final list size: " << listInventory.size() << std::endl << std::endl;


    // --- 3. 결과 비교 ---
    std::cout << ">>> Simulation Summary" << std::endl;
    std::cout << "Push_back: Vector was " << (list_add_duration.count() / vector_add_duration.count()) << "x faster than List." << std::endl;
    std::cout << "Erase: List was " << (vector_erase_duration.count() / list_erase_duration.count()) << "x faster than Vector." << std::endl;

    return 0;
}