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

Vector 내부 구현: 동적 배열 기반. 요소들이 메모리 상에서 연속적으로 저장 (요소끼리 간격 없음) [요소1][요소2][요소3][요소4]...[요소n] 접근 시간: 인덱스를 통한 랜덤 접근 : O(1)의 시간 복잡도 메모리 할당 초기에는 일정 크기의 메모리 블록을 할당하여 요소 저장. 공간이 가득 차면 현재 크기의 두 배에 해당하는 새로운 메모리 블록을 할당하고, 기존 요소들을 복사한 뒤 기존 메모리를 해제 삽입과 삭제: 메모리 상에서 요소가 연속적으로 위치하기 때문에, 중간에 요소를 삽입하거나 삭제하는 작업은 O(n)의 시간 복잡도, 맨 끝에 요소를 추가하거나 삭제하는 작업은 상수 시간 복잡도(O(1))를 가짐 vector 예시 #include #include int main() { std::ve..
개발/C++ 2024. 2. 3. 20:32
1