Hyun JaeHoon

공부용 블로그, 각종 조언들 감사합니다

3 분 소요

std::list 와 std::vector의 차이점?

List

  • 이중 연결 리스트를 기반으로
    각 데이터가 ‘노드’로서 포인터로 연결됨
struct Node {
    Node* prev;
    Node* next;
    T     value;
};
  • 전/후 를 가리키는 노드 포인터를 사용하여
    ‘이전/다음’ 노드를 확인 가능
    • 보통 ‘끊김’을 nullptr 등으로 확인

  • 이러한 노드들은 각각이 ‘별도’로 생성되기에
    Heap 영역에 각각 흩어져 있음

  • 삽입/삭제는 위치를 안다는 가정하에 O(1)이 가능
    • prev와 next의 연결을 끊은 후,
      그 사이에 새로운 Node를 연결하는 방식으로
      포인터 대입 연산을 4번 정도 하는 편
  • 다만, 직접적인 ‘i’번째 인덱스 접근이 안되며
    앞 or 뒤에서 차례대로 접근(O(N))
    • 그렇기에 사실상 ‘접근’이 탐색이 됨
    • 그렇기에 위쪽의 삽입/삭제 위치를 모른다면
      O(N)이 되어버린다

  • 보통 다음 노드를 가리키는 포인터가 필요하기에
    추가적인 메모리가 필요함

  • 작은 데이터들이 여러 공간에 흩어져 있게 되어
    메모리 파편화가 발생할 수 있음

  • 삭제 연산 등을 진행하여도 기본적으로
    prev/next 자체가 변동되지는 않기에
    ‘안전한 삽입/삭제’를 원하는 경우라면 고려 가능

  • 단일로 사용하기 보다는 커스텀 자료구조 등에서
    iterator에 대한 ‘안정성’이 필요한 경우 고려 가능

Vector

  • 동적 배열로서
    하나의 ‘큰 메모리’에 원소들이 차례대로 저장
class Vector{
    T* data; // 데이터 시작
    size_t size;      // 현재 원소 개수
    size_t capacity;  // 현재 할당된 전체 칸수
};
  • capacity를 넘어서게 되면
    새로운 할당 가능 영역을 찾아 Heap 영역을 배회,
    이후, 기존 원소들을 이동시키고 원래 있던 곳은 delete
    • TMI : 보통 새로운 capacity는 이전의 2배로 잡음
    • reserve() 로 초기 vector의 사이즈를 잡아두는 것이 최적화에 도움이 되는 이유
      (첫 동적 할당을 필요한 만큼 잡아 재할당 가능성을 적게 함)
  • ‘연속된 메모리’에 존재하기에
    임의의 인덱스 접근이 O(1)
    • ‘연속된 메모리’에 존재하므로 캐시가 긁어올 때
      한번에 긁어와서 캐시 친화적인 자료 구조
  • 다만 ‘삽입/삭제’는 기본적으로 O(N)
    • 맨 뒤의 추가/삭제는 O(1)이나
      그 외의 경우는 데이터를 ‘당겨야’ 함
    • TMI : 예외적으로 ‘삭제’를 O(1)로 만드는 경우도 존재는 함
      • 삭제 위치의 값을 ‘back()’ 값을 집어넣어 버리고
        맨 뒤의 값을 pop_back()
        다만 이 경우, 기존 vector의 정렬 순서가 깨지는 단점이 존재함
    • 삽입/삭제 가 진행된 경우
      Iterator 들의 안정성이 보장되지 않는 점에 유의
  • 대부분의 상황에서 범용적으로 선택되는 자료구조

정리 표

관점 std::vector std::list
내부 구조 동적 배열 이중 연결 리스트
메모리 배치 연속 노드별 따로
캐시 성능 매우 좋음 나쁨
임의 접근 O(1) 가능 ([i]) 불가(O(n))
끝 삽입/삭제 평균 O(1) O(1)
중간 삽입/삭제 O(n) (원소 이동) O(1) (iterator 알고 있을 때)
메모리 오버헤드 작음 큼 (prev/next 포인터, 파편화)
iterator 안정성 재할당/중간 삽입 시 대량 무효 해당 노드만 제외하고 대부분 안정적
실제 추천도 기본 선택지 정말 특수한 경우에만 고려

TMI : 메모리 단편화?

  • 메모리 총량은 남아 있으나, ‘연속된 공간으로 쪼개져’
    실제로는 못쓰는 현상

  • 분명 충분한 메모리 량이 있음에도
    할당이 실패하는 현상이 발생한다면 단편화를 의심해 보아야 함

외부 단편화

빈 공간들이 서로 떨어져 있어서 큰 연속 블록 할당이 불가능한 상태

[ 8K Free ][ 4K used ][ 8K Free ][ 4K used ][ 8K Free ]

  • Free의 총 용량은 24K이나
    16k 할당은 불가능한 상황!

  • 동적 할당 & 해제의 반복 구조에서 생기게 됨

내부 단편화

할당은 되었으나, 실제 사용량보다
더 큰 할당량을 가져가서
불필요한 공간 낭비가 발생

요청: 30 bytes
할당단위: 64 bytes
=> 실제 34 bytes 낭비
  • ‘고정 사이즈 할당’ 시스템이라면 발생

대응 전략

  • ‘연속된 메모리’ 사용 권장
    • ex) vector
  • 사용 영역을 잡아두기
    • 재할당 횟수 감소
    • 메모리 이동과 단편화를 완화시킴
vec.reserve(10000);
  • Pool 기법
    필요한 객체들을 ‘미리 생성’해두고
    이들을 ‘제거’하지 않고 재사용 하는 방식

정리표

구분 외부 단편화 내부 단편화
원인 빈 블록들이 흩어짐 할당 단위가 실제 요구보다 큼
결과 큰 연속 블록 요청 실패 메모리 낭비
심각도 치명적 보통
발생 주체 list, new/delete 남발 alignment, pool
대응 vector + pool 적절한 size-class

TMI 2 : 복잡도

관련 포스팅

  • 입력한 데이터에 ‘늘어남’에 따라 다음의 요소가 얼마나 늘어나는지 측정
    • 시간 복잡도 : ‘실행 시간’
    • 공간 복잡도 : ‘필요 공간’

보통 빅 O 표기법으로 표현하며
알고리즘의 성능을 나타내는 척도

  • 빅 O 표기법
    ‘대략 그 함수 정도’ (order of the function)이란 의미
    알고리즘의 실행 시간을 일반화하여 표기하며
    ‘실행 시간 증가’에 가장 큰 영향을 미치는 부분만 적용

TMI 3 : list.sort()?

  • list는 노드 기반의 컨테이너이기에
    std::sort를 사용 불가
    iterator를 기반으로 ‘연속 메모리 접근’이 가능한
    자료구조만 sort를 사용 가능함

  • 그렇기에 자체적인 sort 멤버를 가지고
    내부적으로 병합 정렬을 사용

  • std::sort 사용이 가능하려면
    ‘Random Access Iterator’를 가져
    임의의 위치로 건너띄는 연산이 가능해야 함

sort 사용이 가능한 경우

컨테이너 사용 가능 이유
std::vector ✅ 연속 메모리 → Random Access
std::deque ✅ 분할 저장이지만 RA 지원
std::array ✅ 고정 배열 → RA
C 배열 ✅ Pointer = Random Access Iterator
C-style array pointer range ✅ 동일

사용이 불가능한 경우

컨테이너 불가 이유
std::list Bidirectional → 점프 불가
std::forward_list Forward only
std::set / multiset Iterator category OK여도 구조상 “정렬 상태 유지” + 직접 요소 이동 불가
std::map / multimap Key immutable (정렬 구조 변경 불가)
std::unordered_set/map 순서 없음 + 해시 기반

댓글남기기

참고