[내일배움캠프 Day31] 순차 컨테이너

순차 컨테이너(sequential container)는 원소들이 선형으로 배열된 데이터 구조를 나타냅니다.

 

컨테이너	헤더	설명
array	<array>	표준 C 언어 스타일 배열
vector	<vector>	활용도가 높은 기본 컨테이너
list	<list>	연결 리스트(linked list)
deque	<deque>	양방향 큐(queue)

 

배열(std::array)

array는 고정된 크기의 배열을 담는 컨테이너입니다. 인덱스를 이용해 원소에 빠르게 접근할 수 있다는 장점이 있습니다.

 

배열 컨테이너 선언

#include <array>
using namespace std;

array<데이터_형식, 크기> 객체_이름;

 

array 컨테이너를 초기화하는 방법은 일반 배열과 같습니다. 또한 일반 배열처럼 [] 연산자로 각 원소에 접근할 수 있습니다. 배열의 유효 범위 밖의 인덱스로 접근을 시도하면 런타임 오류가 발생합니다.

array<int, 5> myArray {1, 2, 3, 4, 5};
cout << myArray[5]; // 런타임 오류!

 

잘못된 접근으로 인한 런타임 오류를 막으려면 at 함수를 사용합니다. 만약 유효 범위를 벗어나는 접근을 시도하면 at 함수가 std::out_of_range라는 예외를 던집니다.

 

벡터(std::vector)

vector는 임의의 위치에 저장된 원소에 빠르게 접근할 수 있고, 동적 배열 관리를 안전하게 수행해 주는 덕분에 표준 컨테이너 가운데 가장 많이 활용됩니다.

 

벡터 컨테이너 선언

#include <vector>
using namespace std;

vector<데이터_형식> 객체_이름;
vector<데이터_형식> 객체_이름(크기);
vector<데이터_형식> 객체_이름(크기, 초깃값);
vector<데이터_형식> 객체_이름 = {값1, 값2, 값3, ...};

 

벡터의 크기는 동적이므로 힙 메모리가 허용하는 한 계속 늘릴 수 있습니다. 따라서 push_back 멤버 함수로 벡터의 끝에 원소를 계속 추가할 수 있습니다.

벡터 컨테이너의 insert와 erase 함수에 반복자를 전달하면 중간에 새로운 원소를 넣거나 지울 수도 있습니다. 삽입, 삭제 과정을 보면 insert 함수는 한 칸씩 뒤로 밀리도록 복사 저장하고, erase 함수는 한 칸씩 앞으로 당겨지도록 복사 저장합니다. 이는 처리 속도 면에서 불리하므로 삽입이나 제거가 빈번하게 발생하면 벡터 대신 다른 컨테이너를 사용하는 것이 좋습니다.

• push_back(value): 맨 뒤에 원소 추가
• pop_back(): 맨 뒤 원소 제거
• size(): 원소 개수 반환
• capacity(): 현재 할당된 메모리 크기
• at(index): 지정된 인덱스의 원소 반환 (범위 초과 시 예외 발생)
• front(): 첫 번째 원소 반환
• back(): 마지막 원소 반환
• clear(): 모든 원소 제거
• insert(iterator, value): 지정된 위치에 원소 삽입
• erase(iterator): 지정된 위치의 원소 제거
• data(): 내부 배열 포인터 반환

 

값을 변경할 수 없는 정적 반복자

반복자는 포인터처럼 동작하는데 std::vector에서 지원하는 반복자 가운데 const_iterator가 있습니다. 정적 포인터처럼 생각하면 쉬운데, 반복자가 가리키는 원솟값을 변경할 수 없습니다.

const_iterator는 cbegin과 cend 함수로 얻을 수 있습니다. 반복자로 지정한 값을 변경하지 않고 참조만 할 때 const iterator을 활용할 수 있습니다.

for (std::vector<int>::const_iterator it = vec.cbegin(); it != vec.cend(); ++it) {
    std::cout << *it << " ";
}

 

거꾸로 동작하는 리버스 반복자

std::vector에서 지원하는 반복자 중에 거꾸로 동작하는 리버스 반복자도 있습니다. 이는 벡터 컨테이너의 뒤부터 앞으로 움직이는 특성이 있습니다.

for (std::vector<int>::reverse_iterator rit = vec.rbegin(); rit != vec.rend(); ++rit) {
    std::cout << *rit << " ";
}

벡터 컨테이너의 시작 위치와 마지막 위치를 반환하는 begin, end 함수와 반대이며, 연산 결과도 반대입니다.

 

리스트(std::list)

C++의 std::list는 연결 리스트(linked list)라는 데이터 구조를 구현한 컨테이너입니다. 연결 리스트는 데이터가 노드라 불리는 개별 객체로 구성되며, 각 노드는 다음 노드를 가리키는 포인터를 포함합니다. 이런 특성 때문에 리스트는 데이터를 삽입하고 삭제하는 데 효율적이며 순서를 유지할 수 있습니다.

• push_back(value): 맨 뒤에 원소 추가
• push_front(value): 맨 앞에 원소 추가
• pop_back(): 맨 뒤 원소 제거
• pop_front(): 맨 앞 원소 제거
• insert(iterator, value): 지정된 위치에 원소 삽입
• erase(iterator): 지정된 위치의 원소 제거

 

리스트 컨테이너도 벡터 컨테이너처럼 삽입된 순서를 유지하는 순차 컨테이너 입니다. 다만 내부 구현 방식이 다릅니다. 벡터는 동적 배열로 구현되어 원소들을 연속된 메모리 공간에 저장합니다. 반면에 리스트는 이중 연결 리스트로 구현되어 각 원소에는 다음 원소와 이전 원소를 가리키는 포인터가 있습니다.

이런 차이점 때문에 벡터는 임의 접근이 가능하며 원소를 상수 시간에 접근할 수 있지만, 리스트는 임의 접근이 불가능하며 원소에 접근하려면 이전 원소들을 차례로 따라가야 합니다. 따라서 벡터는 원소에 자주 접근하고 수정해야 할 때에 주로 사용하고, 리스트는 삽입과 삭제가 빈번할 때에 유용합니다.

 

덱(std::deque)

deque 역시 배열 기반의 컨테이너이며 벡터 컨테이너와 유사합니다. 벡터는 하나의 메모리 블록에 원소들을 저장하지만 deque는 여러 개의 메모리 블록을 나눠서 저장하는 것이 특징입니다. 저장할 공간이 부족하면 일정한 크기의 새로운 메모리 블록을 만들어서 연결해 벡터 컨테이너에서 일어나는 복사 저장이 발생하지 않습니다. 즉, 벡터의 단점을 보완하는 컨테이너입니다.

 

특징	std::deque	std::vector
메모리 할당 방식	메모리의 재할당이 자주 발생하지 않음	메모리의 재할당이 발생할 수 있음
원소 삽입과 삭제	양쪽 끝에서 O(1)의 시간 복잡도로 수행	끝에서 O(1)의 시간 복잡도로 수행, 중간에서 O(n)의 시간 복잡도로 수행
원소 접근	O(1)의 시간 복잡도로 수행	O(1)의 시간 복잡도로 수행

 

• push_back(value): 맨 뒤에 원소 추가
• push_front(value): 맨 앞에 원소 추가
• pop_back(): 맨 뒤 원소 제거
• pop_front(): 맨 앞 원소 제거
• at(index): 지정된 인덱스의 원소 반환 (범위 초과 시 예외 발생)
• front(): 첫 번째 원소 반환
• back(): 마지막 원소 반환
• clear(): 모든 원소 제거
• insert(iterator, value): 지정된 위치에 원소 삽입
• erase(iterator): 지정된 위치의 원소 제거

 

deque 컨테이너는 원소의 삽입과 삭제가 빈번하게 일어나는 상황에서 사용하기에 좋습니다. 벡터와 달리 중간 부분에서도 상수 시간에 원소를 삽입하거나 삭제할 수 있습니다.

 

 

 

출처 : C++ 완전 정복 책