컨테이너 탐색: 비교 횟수와 메모리 접근을 따로 봅니다

vector가 연속이라는 말의 범위를 정합니다

C++ N4950의 vector는 bool 이외 원소에서 연속 컨테이너입니다. 포인터를 원소로 갖는 vector라면 연속인 것은 포인터 배열이지 포인터가 가리키는 객체 전체가 아닙니다. 재할당은 원소를 가리키는 기존 참조·포인터의 유효성에도 영향을 주므로 탐색 시간만으로 교체를 결정하지 않습니다.

C++ N4950 · vector 개요

비교 횟수가 적다고 반드시 시간이 짧은 것은 아닙니다

작은 데이터 집합의 선형 스캔은 더 많은 원소를 비교하더라도 연속 접근과 단순한 제어 흐름의 이점을 얻을 수 있습니다. 반면 집합이 커지면 비교 횟수가 중요해집니다. 정렬된 vector의 이진 탐색은 인접 원소를 차례로 읽는 스캔과 다릅니다. “O(n)이 O(log n)보다 빠르다”는 일반 법칙으로 바꾸지 않습니다.

Intel 데이터 배치 사례

갱신과 사용하는 필드까지 포함합니다

vector 중간의 삽입·삭제는 원소 수에 비례하는 이동 비용을 만들 수 있습니다. 조회에서 일부 필드만 쓰는 큰 구조체는 쓰지 않는 데이터도 함께 가져올 수 있으므로 AoS와 SoA를 비교할 이유가 됩니다. 하지만 분리한 배열을 여러 필드에 걸쳐 함께 갱신한다면 또 다른 비용과 일관성 조건이 생깁니다.

vector 갱신의 복잡도

같은 답을 내는 작업을 비교합니다

키 분포와 적중·실패 비율을 고정하고 준비·정렬 비용을 포함할지 명시합니다. 결과를 소비해 컴파일러가 탐색을 없애지 못하게 하고, warm·cold 조건을 나누어 반복 측정합니다. 먼저 전체 시간을 확인한 뒤 cache miss·branch·stall 지표로 원인을 좁힙니다. 캐시 라인 크기나 SIMD 사용을 모든 CPU의 고정 상수로 가정하지 않습니다.

이 글은 표준과 공개 데이터 배치 사례를 대조한 선택 기준입니다. 원본 카드 이미지의 수치나 이 사이트에서 수행한 성능 측정 결과를 제시하는 글은 아닙니다.

이어서 읽기

• 주소 변환과 메모리 접근
• 실행 경로와 성능 관측