[C++/STL Container] Vector, List, Array에 대해

Vector

• 내부 구현: 동적 배열 기반. 요소들이 메모리 상에서 연속적으로 저장 (요소끼리 간격 없음)

[요소1][요소2][요소3][요소4]...[요소n]

• 접근 시간: 인덱스를 통한 랜덤 접근 : O(1)의 시간 복잡도
• 메모리 할당
  • 초기에는 일정 크기의 메모리 블록을 할당하여 요소 저장. 공간이 가득 차면 현재 크기의 두 배에 해당하는 새로운 메모리 블록을 할당하고, 기존 요소들을 복사한 뒤 기존 메모리를 해제
• 삽입과 삭제: 메모리 상에서 요소가 연속적으로 위치하기 때문에, 중간에 요소를 삽입하거나 삭제하는 작업은 O(n)의 시간 복잡도, 맨 끝에 요소를 추가하거나 삭제하는 작업은 상수 시간 복잡도(O(1))를 가짐

 

• vector 예시

#include <iostream>
#include <vector>

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

    // 요소 추가
    vec.push_back(10);
    vec.push_back(20);
    vec.push_back(30);

    // 인덱스를 사용한 요소 접근
    std::cout << "Element at index 1: " << vec[1] << std::endl;

    // 요소 순회
    std::cout << "Vector elements: ";
    for(int i : vec) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    // 요소 삭제 (마지막 요소)
    vec.pop_back();

    return 0;
}

 

 

List

• 내부 구현: 이중 연결 리스트(double-linked list) 기반. 이는 각 요소가 메모리 상에서 이전 및 다음 요소를 가리키는 포인터를 포함하고 있음을 의미합니다.

[요소1|*]->[<-|요소2|*]->[<-|요소3|*]->...[<-|요소n]
    ^                                    ^
    |------------------------------------|

• 접근 시간: list는 요소들이 메모리 상에서 연속적이지 않기 때문에, 인덱스를 통한 랜덤 접근이 지원되지 않습니다. 특정 위치의 요소에 접근하기 위해서는 처음부터 순차적으로 탐색해야 하므로, 접근 시간은 O(n)입니다.
• 메모리 할당
  • 각 요소는 개별적으로 메모리에 할당. 다음 요소와 이전 요소를 가리키는 포인터를 통해 서로 연결됨. -> 메모리의 재할당과 요소의 복사 없이 요소를 추가하거나 삭제 가능
• 삽입과 삭제: list는 중간 위치에 요소를 삽입하거나 삭제하는 작업이 매우 효율적. 해당 위치의 반복자만 있으면, 삽입이나 삭제 작업은 O(1)의 시간 복잡도를 가집니다.

 

• list 예시

#include <iostream>
#include <list>

int main() {
    // 초기 리스트 생성
    std::list<int> myList = {1, 2, 4, 5};

    // 반복자를 사용해 두 번째 위치를 찾음
    auto it = myList.begin();
    std::advance(it, 2); // it는 이제 '4'를 가리킴

    // '4' 앞에 '3' 삽입
    myList.insert(it, 3);

    // 리스트 출력 (삽입 후)
    std::cout << "After insertion: ";
    for (int value : myList) {
        std::cout << value << " ";
    }
    std::cout << std::endl;

    // '3'을 가리키는 반복자를 다시 얻음 (이 예에서는 같은 위치임)
    --it; // it는 이제 '3'을 가리킴

    // '3' 삭제
    myList.erase(it);

    // 리스트 출력 (삭제 후)
    std::cout << "After deletion: ";
    for (int value : myList) {
        std::cout << value << " ";
    }
    std::cout << std::endl;

    return 0;
}

 

 

 

 

Array

• 컴파일 시간에 크기가 결정, 메모리 상에서 연속적인 공간 차지
• 빠른 인덱스 기반 접근 가능
• 배열의 크기는 선언 시점에 고정, 실행 시간에 크기 변경 불가능

[요소0] [요소1] [요소2] [요소3] ... [요소N]

 

#include <iostream>

int main() {
    // 크기가 5인 정수 배열 선언 및 초기화
    int myArray[5] = {1, 2, 3, 4, 5};

    // 배열의 특정 요소에 접근 및 출력
    std::cout << "The second element is: " << myArray[1] << std::endl;

    // 배열의 요소 수정
    myArray[2] = 10; // 배열의 세 번째 요소를 10으로 변경

    // 배열의 모든 요소 순회 및 출력
    std::cout << "Array elements: ";
    for (int i = 0; i < 5; ++i) {
        std::cout << myArray[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

 

 

요약

- vector: 연속적인 메모리 공간, 인덱스로 빠른 접근 가능, 크기 조정 시에 비용 발생

- list: 비연속적인 메모리 공간, 포인터 기반 구조이기 때문에 중간 위치에서의 삽입과 삭제가 효율적

- array: 컴파일 시 고정된 크기를 가지며, 메모리 상에서 연속적인 공간을 차지