STL - list / vector / array

📒 list / vector / array

🔍 들어가기에 앞서...

• 시퀀스 컨테이너에 대해 알아보자.
• https://velog.io/@liz/C-sequence-container-%EB%B3%B5%EC%8A%B5%EC%9D%84-%EC%9C%84%ED%95%B4-%EC%9E%91%EC%84%B1%ED%95%98%EB%8A%94-%EA%B8%80-2023-11-13
  
  

📌 C 스타일 배열의 단점

• 메모리 할당과 해제를 수동으로 해야 한다.
• 메모리를 해제하지 못하면 메로리 누수(memory leak)가 발생할 수 있다.
• operator[]에서 배열 크기보다 큰 원소를 참조하는 것을 검사하지 못하기 때문에 잘못 사용 시, 세그멘테이션 결함(segmentation fault) 또는 메모리 손상으로 이어질 수 있다.
• 배열을 중첩해서 사용할 경우 코드가 복잡해 보이게 된다.
• 깊은 복사(deep copy)가 기본적으로 동작하지 않는다. (수동으로 구현해야 함)
• 위 문제점들을 보완하기 위해, C++은 C 스타일의 배열을 대체할 수 있는 여러 시퀀스 컨테이너를 제공한다.
  
  

📌 list란?

• C++ STL에서 제공하는 양방향 연결 리스트(double linked list)로 구현된 컨테이너이다.
• List는 STL에서 시퀀스 컨테이너 중 하나로, vector와 달리 메모리 할당이 연속적으로 이루어지지 않는다.
  
  

📌 list의 특징

• 요소를 선형 배열 형태로 저장한다.
• 시퀀스 내의 모든 위치에서 효율적인 삽입 및 삭제가 가능하다.
• 양방향으로 연결되어 있어, 앞과 뒤로 모두 이동이 가능하다.
• merge, reverse, remove, remove_if에 대한 작업에 최적화 되어있다.
• 요소를 탐색할 때, 임의 접근(random access)은 불가능하나, 양방향 반복자(++, --)를 이용하여 탐색이 가능하다.
  
  

📌 list의 멤버 함수와 연산자

• https://learn.microsoft.com/ko-kr/cpp/standard-library/list-class?view=msvc-170
  
  

📌 vector란?

• C++ STL에서 제공하는 동적 배열 컨테이너이다.
• C의 배열과 유사하지만, 자동으로 배열의 크기 조절과 요소의 추가와 삭제가 가능하다.
• 시퀀스 컨테이너 중 하나로, 메모리 할당이 연속적으로 이루어져 있다.
  
  

📌 vector의 특징

• 임의 접근(random access)이 가능하다.
• 크기가 자동으로 늘어난다.
• 속도 측면에서는 배열보다 떨어지지만, 메모리를 효율적으로 관리할 수 있다.
• 메모리 재할당이 발생할 수 있고, 발생할 때 오버헤드가 생긴다.
• 그 때문에, 빈번한 데이터 삽입 및 삭제가 발생할 때는 비효율적이다.
  
  

📌 vector의 멤버 함수와 연산자

• https://learn.microsoft.com/ko-kr/cpp/standard-library/vector-class?view=msvc-170
  
  

📌 array란?

• C++ STL에서 제공하는 고정 크기의 배열 컨테이너이다.
• 메모리 할당이 연속적으로 이루어져 있다.
• 기존의 C 배열과 같은 형태를 유지하면서(오버헤드가 없음), C++에서 추가된 반복자 및 대입 연산자 등을 사용할 수 있다.
  
  

📌 array의 특징

• 임의 접근(random access)이 가능하다.
• 크기가 고정 길이이다.
  
  

📌 array의 멤버 함수와 연산자

• https://learn.microsoft.com/ko-kr/cpp/standard-library/array-class-stl?view=msvc-170
  
  

📌 list / vector / array 비교

list

• 비연속적 메모리 구조이다.
• double linked list로 구현되어 있다.
• 메모리를 선할당 하지 않는다.
• 모든 위치에서 삽입 및 삭제가 빠르다. (비용이 적게 듦)
• 중간 원소 접근이 어렵다. (처음 또는 뒤부터 선형 탐색해야 함, 비용이 많이 듦)
• 연결 정보를 저장하기 위해 메모리가 추가 사용된다.
• 컨테이너 내 순회 속도가 느리다. (forward 및 reverse만 가능)
• 리스트에서 요소를 추가 및 삭제할 때, iterator는 유효하게 남아있다.

vector

• 컨테이너의 끝에 데이터를 추가 및 삭제할 때 매우 빠르게 동작한다.
• 메모리가 연속적이다.
• 메모리를 선할당 한다.
• 임의 접근 반복자를 사용한다. (+, -, +=, -=, operator[] 연산 가능)
• 요소를 추가 및 삭제하면 iterator는 무효가 된다.
• 개별 원소에 대한 접근 속도가 빠르다.
• push_back 함수의 시간 복잡도는 항상 O(1)이다. (끝에서 추가)
• 끝이 아닌 다른 곳에 요소를 추가할 때는 O(n)이다.
• 컨테이너의 중간에서 삽입 및 삭제가 비효율적이다. (모든 원소를 한 칸씩 당기거나 밀어야 함)
• 요소를 추가할 때 자동적으로 메모리를 재할당하게 되는데, 여기서 오버헤드가 발생한다.

array

• 크기가 정적이다.
• 검색이 빠르다.
• 메모리가 연속적이다.
• 컴파일 시점에 크기가 확정된다.
• 배열의 크기를 미리 선언해야 한다.
• 삽입 및 삭제가 자주 일어날 경우 비효율적이다.