[C++] Sequence Container (array, vector, duque, forward_list, list)

Sequence Container

• 데이터를 순차적으로 저장하는 구조
• 구현이 단순하고 가볍고 빠르기에 저장할 데이터가 정렬 상태를 계속 유지할 필요가 없을 때 선택

 

std::array

#include <iostream>

using namespace std;

int main() {
	int arr[5] = {1, 2, 3, 4, 5}
    int searchValue = 3;
    int changeValue = 6;
    
    for (int i = 0; i < 5; ++i) {
		cout << arr[i] << " ";
    }
    
    for (int i = 0; i < 5; ++i) {
    	if(arr[i] == searchValue){
        	arr[i] = changeValue;
        }
    }
    
    return 0;
}

 

 

• 특징
  • 크기 고정 (컴파일 타임에 크기가 고정 필요)
  • 요소는 연속된 메모리 공간에 저장
  • 인덱스를 사용하여 O(1) 시간 복잡도로 접근 가능
  • 크기 변경이 불가능
• 사용 시기
  • 요소의 수가 고정되어 있고 변경될 가능성이 없는 경우.
  • 메모리 효율이 중요한 경우
  • 빠른 인덱스 접근이 필요한 경우

 

std:vector

#include <iostream>
#include <vector>
#include <algorithm> // std::find
#include <iterator>  // std::distance

using namespace std;

int main() {
	vector<int> vec = {1, 2, 3, 4, 5}
    int serachValue = 3;
    
    vec.push_back(6);
    
    vec.insert(vec.begin() + 2, 7) // 2번 인덱스에 7 삽입
    
    vec.erase(vec.begin() + 4) // 4번 인덱스 삭제
    
    auto it = std:find(vec.begin(), vec.end(), searchValue);
    if(it != vec.end()) {
    	cout << searchValue << 
    }
    
    // std::distance는 두 반복자 사이의 거리를 계산
    for (size_t i = 0; i < vec.size(); ++i) {
    	cout << vec[i] << " " << distance(vec.begin(), it) << endl;
    }
    
    return 0;
}

 

 

• 특징
  • 크기를 동적으로 조절 가능 (런타임에서 조절 가능)
  • 포인터 3개로 구현
    • 할당된 배열의 시작 주소를 가리키는 포인터
    • 다음에 데이터가 삽입될 위치를 가리키는 포인터
    • 할당된 배열의 끝 주소를 가리키는 포인터
  • 요소는 연속된 메모리 공간에 저장된다.
  • 인덱스를 사용하여 O(1) 시간 복잡도로 접근 가능하다.
  • 요소의 추가 및 삭제는 평균적으로 O(1) 시간 복잡도를 가진다. (마지막 위치에 추가할 때)
    
    • 맨 뒤에 원소를 추가하는 push_back 연산은 상수 시간복잡도를 가지지만, 할당된 공간이 전부 차면 배열을 통째로 복사해 새로운 vector에 할당하는 reallocation이 발생해 시간이 많이 소요됨
    • 알고리즘 문제에서는 가급적 vector의 크기를 충분히 확보한 상태로 사용!
  • 임의의 위치에 요소를 추가 및 삭제하는 것은 O(n)으로 상당히 느림
    • 임의의 위치 뒤에 오는 원소들을 모두 한 칸씩 이동시켜 줘야 하기 때문
• 사용 시기
  • 요소의 수가 가변적일 때
  • 메모리 연속성을 유지하면서도 크기를 조절하고 싶은 경우
  • 빈번한 읽기 작업과 마지막 위치에서의 삽입/삭제 작업이 많은 경우
• 멤버 함수
  • operator[](size_type pos): 지정한 위치의 요소에 접근
  • at(size_type pos): 지정한 위치의 요소에 접근하고, 범위를 벗어나면 예외를 던짐
  • front(): 첫 번째 요소에 접근
  • back(): 마지막 요소에 접근
  • data(): 내부 배열의 포인터를 반환 (벡터의 첫 번째 요소를 가리키는 포인터를 반환, 비어있으면 nullptr)
  • empty(): 벡터가 비어 있는지 확인
  • size(): 벡터의 현재 크기를 반환
  • max_size(): 벡터가 가질 수 있는 최대 크기를 반환
  • reserve(size_type new_cap): 최소한의 저장 용량을 예약
  • capacity(): 벡터의 현재 저장 용량을 반환
  • shrink_to_fit(): 벡터의 용량을 현재 크기에 맞춤
  • clear(): 벡터의 모든 요소를 제거
  • insert(const_iterator pos, const T& value): 지정한 위치에 값을 삽입
  • insert(const_iterator pos, T&& value): 지정한 위치에 값을 이동하여 삽입
  • insert(const_iterator pos, size_type count, const T& value): 지정한 위치에 count개의 값을 삽입
  • insert(const_iterator pos, InputIt first, InputIt last): 지정한 위치에 다른 범위의 요소들을 삽입
  • insert(const_iterator pos, std::initializer_list<T> ilist): 지정한 위치에 초기화 리스트의 요소들을 삽입
  • erase(const_iterator pos): 지정한 위치의 요소를 제거
  • erase(const_iterator first, const_iterator last): 지정한 범위의 요소들을 제거
  • push_back(const T& value): 벡터의 끝에 값을 추가
  • push_back(T&& value): 벡터의 끝에 값을 이동하여 추가
  • pop_back(): 벡터의 마지막 요소를 제거
  • resize(size_type count): 벡터의 크기를 조정
  • resize(size_type count, const value_type& value): 벡터의 크기를 조정하고 새 요소를 value로 초기화
  • begin(): 벡터의 시작 반복자를 반환
  • cbegin() const: 벡터의 시작 반복자를 상수형으로 반환
  • end(): 벡터의 끝 반복자를 반환
  • cend() const: 벡터의 끝 반복자를 상수형으로 반환
  • rbegin(): 벡터의 역방향 시작 반복자를 반환
  • crbegin() const: 벡터의 역방향 시작 반복자를 상수형으로 반환
  • rend(): 벡터의 역방향 끝 반복자를 반환
  • crend() const: 벡터의 역방향 끝 반복자를 상수형으로 반환

begin, end, size, capcaity

 

 

std::deque

#include <iostream>
#include <deque>

using namespace std;

int main() {
	deque<int> deq = {1, 2, 3, 4, 5};
    
    deq.push_front(0);
    
    deq.push_back(0);
    
    for (size_t i = 0; i < deq.size(); ++i) {
    	std::cout << deq[i] << " ";
    }
    
    return 0;
}

• 특징
  • double-ended queue 
  • 양쪽 끝에서의 삽입 및 삭제가 O(1)
  • 중간에서의 삽입과 삭제는 벡터와 유사하게 O(n) 시간 복잡도
  • 연속된 메모리 블록이 아닌 여러 블록에 걸쳐 요소를 저장 (= 여러 개의 버퍼에 데이터를 나눠서 저장)
    • deque는 메모리 상에서 연속적으로 존재하지 않음
    • 따라서 원소들이 어디에 저장되어 있는지에 대한 정보를 보관하기 위해서 추가적인 메모리가 더 필요
    • vector는 할당된 공간이 전부 차면 배열을 통째로 새로 할당해야 했지만, deque는 새로운 블록(버퍼) 하나를 할당하고 연결시키기만 하면되기에 처음과 끝 삽입 시 크기가 전부 차는 경우에도 O(1)으로 삽입 가능
  • 인덱스를 사용하여 O(1) 시간 복잡도로 접근 가능
• 사용 시기
  • 양쪽 끝에서 빈번한 삽입/삭제 작업이 필요한 경우
  • 크기가 가변적이며, 중간 삽입/삭제보다는 양끝에서의 작업이 많은 경우
• 멤버 함수
  
  • at(size_type pos): 지정한 위치의 요소에 접근하고, 범위를 벗어나면 예외를 던짐
  • front(): 첫 번째 요소에 접근
  • back(): 마지막 요소에 접근
  • empty(): 덱이 비어 있는지 확인합
  • size(): 덱의 현재 크기를 반환
  • max_size(): 덱이 가질 수 있는 최대 크기를 반환
  • shrink_to_fit(): 덱의 용량을 현재 크기에 맞춤
  • clear(): 덱의 모든 요소를 제거
  • insert(const_iterator pos, const T& value): 지정한 위치에 값을 삽입
  • insert(const_iterator pos, T&& value): 지정한 위치에 값을 이동하여 삽입
  • insert(const_iterator pos, size_type count, const T& value): 지정한 위치에 count개의 값을 삽입
  • insert(const_iterator pos, InputIt first, InputIt last): 지정한 위치에 다른 범위의 요소들을 삽입
  • insert(const_iterator pos, std::initializer_list<T> ilist): 지정한 위치에 초기화 리스트의 요소들을 삽입
  • erase(const_iterator pos): 지정한 위치의 요소를 제거
  • erase(const_iterator first, const_iterator last): 지정한 범위의 요소들을 제거
  • push_back(const T& value): 덱의 끝에 값을 추가
  • push_back(T&& value): 덱의 끝에 값을 이동하여 추가
  • push_front(const T& value): 덱의 앞에 값을 추가
  • push_front(T&& value): 덱의 앞에 값을 이동하여 추가
  • pop_back(): 덱의 마지막 요소를 제거
  • pop_front(): 덱의 첫 번째 요소를 제거
  • resize(size_type count): 덱의 크기를 조정
  • resize(size_type count, const value_type& value): 덱의 크기를 조정하고 새 요소를 value로 초기화
  • begin(): 덱의 시작 반복자를 반환
  • cbegin() const: 덱의 시작 반복자를 상수형으로 반환
  • end(): 덱의 끝 반복자를 반환
  • cend() const: 덱의 끝 반복자를 상수형으로 반환
  • rbegin(): 덱의 역방향 시작 반복자를 반환
  • crbegin() const: 덱의 역방향 시작 반복자를 상수형으로 반환
  • rend(): 덱의 역방향 끝 반복자를 반환
  • crend() const: 덱의 역방향 끝 반복자를 상수형으로 반환

 

Vector vs Deque

양쪽 끝에서의 빈번한 삽입/삭제 -> Deque가 유리 (Vector는 끝에서만)

C배열의 라이브러리와 상호작용이 필요하거나 공간지역성 고려 -> Vector가 유리(deque는 메모리 상에서 연속적으로 존재하지 않음)

 

 

std:list

#include <iostream>
#include <list>
#include <algorithm>
#include <iterator> // std::advance

using namespace std;

int main() {
	list<int> myList = {1, 2, 3, 4, 5};
    
    auto it = find(myList.begin(), myList.end(), 3);
    if (it != myList.end()) {
    	myList.insert(++it, 6);
    }
    
    // 요소 추가
    lst.push_back(6);  // 끝에 추가
    lst.push_front(0); // 앞에 추가

    // 요소 삭제
    lst.pop_back();    // 끝에서 삭제
    lst.pop_front();   // 앞에서 삭제

    // 임의 접근 (리스트에서는 비효율적이므로 주의)
    auto it = lst.begin();
    std::advance(it, 2);
    std::cout << "Element at index 2: " << *it << std::endl;

    // 중간 삽입
    lst.insert(it, 10);

    // 중간 삭제
    it = lst.begin();
    std::advance(it, 2); // 반복자(it)를 지정된 거리(2)만큼 이동시키는 데 사용
    lst.erase(it);

    // 리스트 출력
    for (int val : lst) {
        std::cout << val << " ";
    }
    
    return 0;
}

• 특징
  • 각 노드는 이전 및 다음 노드에 대한 포인터를 가짐 (doubly-linked list)
  • O(1) 시간 복잡도로 어느 위치에도 요소를 삽입/삭제 가능 (포인터를 갖고 있는 경우)
  • 시작 원소와 마지막 원소의 위치만 기억하기 때문에 random access (Container의 i번째 데이터에 O(1)에 접근)은 불가능
  • 불연속적 메모리 공간
  • 양방향 순회가 가능
• 사용 시기
  • 빈번한 삽입/삭제 작업이 리스트의 임의의 위치에서 일어나는 경우
  • 메모리 사용이 불연속적이어도 괜찮은 경우
  • 양방향 순회가 필요한 경우
• 멤버 함수
  • empty(): 리스트가 비어 있는지 확인
  • size(): 리스트의 현재 크기를 반환
  • max_size(): 리스트가 가질 수 있는 최대 크기를 반환
  • front(): 첫 번째 요소에 접근
  • back(): 마지막 요소에 접근
  • assign(size_type count, const T& value): count개의 value로 리스트를 채움
  • assign(InputIt first, InputIt last): 다른 범위의 요소들로 리스트를 채움 ex) lst.assign(vec.begin(), vec.end());
  • assign(std::initializer_list<T> ilist): 초기화 리스트의 요소들로 리스트를 채움 ex) lst.assign({10, 20, 30, 40, 50});
  • clear(): 리스트의 모든 요소를 제거
  • insert(const_iterator pos, const T& value): 지정한 위치에 값을 삽입
  • insert(const_iterator pos, T&& value): 지정한 위치에 값을 이동하여 삽입
  • insert(const_iterator pos, size_type count, const T& value): 지정한 위치에 count개의 값을 삽입
  • insert(const_iterator pos, InputIt first, InputIt last): 지정한 위치에 다른 범위의 요소들을 삽입
  • insert(const_iterator pos, std::initializer_list<T> ilist): 지정한 위치에 초기화 리스트의 요소들을 삽입
  • erase(const_iterator pos): 지정한 위치의 요소를 제거
  • erase(const_iterator first, const_iterator last): 지정한 범위의 요소들을 제거
  • push_back(const T& value): 리스트의 끝에 값을 추가
  • push_back(T&& value): 리스트의 끝에 값을 이동하여 추가
  • push_front(const T& value): 리스트의 앞에 값을 추가
  • push_front(T&& value): 리스트의 앞에 값을 이동하여 추가
  • pop_back(): 리스트의 마지막 요소를 제거
  • pop_front(): 리스트의 첫 번째 요소를 제거
  • resize(size_type count): 리스트의 크기를 조정
  • resize(size_type count, const value_type& value): 리스트의 크기를 조정하고 새 요소를 value로 초기화
  • swap(list& other) noexcept: 다른 리스트와 요소를 교환

 

std::forward_list

#include <iostream>
#include <forward_list>

int main() {
    // forward_list 생성 및 초기화
    std::forward_list<int> flst = {1, 2, 3, 4, 5};

    // 요소 추가
    flst.push_front(0); // 앞에 추가

    // 요소 삭제
    flst.pop_front(); // 앞에서 삭제

    // 요소 접근
    std::cout << "First element: " << flst.front() << std::endl;

    // 중간 삽입
    auto it = flst.before_begin(); // 첫 번째 요소 이전 위치
    std::advance(it, 2); // 두 번째 요소 이전 위치로 이동
    flst.insert_after(it, 10);

    // 리스트 출력
    std::cout << "List elements: ";
    for (const auto& val : flst) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}

 

• 특징
  • singly-linked list 
  • 각 노드는 다음 노드에 대한 포인터를 가짐
  • O(1) 시간 복잡도로 앞쪽에 요소를 삽입/삭제 가능
  • doubly-linked list에 비해 포인터를 하나 덜 가지므로 기본적인 연산이 빠르고 메모리를 적게 사용
  • 불연속적인 메모리 공간
  • 양방향 순회가 불가능하며, 역방향 접근이 불가능하다
• 사용 시기
  • 메모리 사용이 불연속적이지만 삽입/삭제 작업이 빈번할 때
  • 양방향 순회나 역방향 접근이 필요하지 않은 경우
  • 단방향 리스트의 메모리 오버헤드가 문제가 되지 않을 때
  • doubly-linked list의 기능까지 필요하지 않으면 더 가볍고 빠른 forward_list가 유리
• 멤버 함수
  • front(): 첫 번째 요소에 접근
  • front() const: 첫 번째 요소에 상수형으로 접근
  • assign(size_type count, const T& value): count개의 value로 리스트를 채움
  • assign(InputIt first, InputIt last): 다른 범위의 요소들로 리스트를 채움
  • assign(std::initializer_list<T> ilist): 초기화 리스트의 요소들로 리스트를 채움
  • clear(): 리스트의 모든 요소를 제거
  • insert_after(const_iterator pos, const T& value): 지정한 위치 뒤에 값을 삽입
  • insert_after(const_iterator pos, T&& value): 지정한 위치 뒤에 값을 이동하여 삽입
  • insert_after(const_iterator pos, size_type count, const T& value): 지정한 위치 뒤에 count개의 값을 삽입insert_after(const_iterator pos, InputIt first, InputIt last): 지정한 위치 뒤에 다른 범위의 요소들을 삽입
  • insert_after(const_iterator pos, std::initializer_list<T> ilist): 지정한 위치 뒤에 초기화 리스트의 요소들을 삽입
  • emplace_after(const_iterator pos, Args&&... args): 지정한 위치 뒤에 요소를 직접 생성하여 삽입
  • erase_after(const_iterator pos): 지정한 위치 뒤의 요소를 제거
  • erase_after(const_iterator first, const_iterator last): 지정한 범위의 요소들을 제거
  • push_front(const T& value): 리스트의 앞에 값을 추가
  • push_front(T&& value): 리스트의 앞에 값을 이동하여 추가
  • emplace_front(Args&&... args): 리스트의 앞에 요소를 직접 생성하여 추가
  • pop_front(): 리스트의 첫 번째 요소를 제거
  • resize(size_type count): 리스트의 크기를 조정
  • resize(size_type count, const value_type& value): 리스트의 크기를 조정하고 새 요소를 value로 초기화
  • merge(forward_list& other): 두 리스트를 병합. 두 리스트는 이미 정렬되어 있어야 함
  • merge(forward_list&& other): 두 리스트를 병합. 두 리스트는 이미 정렬되어 있어야 함
  • splice_after(const_iterator pos, forward_list& other): other 리스트의 요소들을 pos 위치 뒤에 삽입
  • splice_after(const_iterator pos, forward_list&& other): other 리스트의 요소들을 pos 위치 뒤에 삽입
  • splice_after(const_iterator pos, forward_list& other, const_iterator it): other 리스트의 단일 요소를 pos 위치 뒤에 삽입
  • splice_after(const_iterator pos, forward_list&& other, const_iterator it): other 리스트의 단일 요소를 pos 위치 뒤에 삽입
  • splice_after(const_iterator pos, forward_list& other, const_iterator first, const_iterator last): other 리스트의 범위 요소를 pos 위치 뒤에 삽입
  • splice_after(const_iterator pos, forward_list&& other, const_iterator first, const_iterator last): other 리스트의 범위 요소를 pos 위치 뒤에 삽입
  • remove(const T& value): 리스트에서 value와 동일한 값을 가진 모든 요소를 제거
  • remove_if(UnaryPredicate p): 조건자 p를 만족하는 모든 요소를 제거
  • reverse(): 리스트의 요소 순서를 반전시킴
  • unique(): 연속된 중복 요소를 제거
  • sort(): 리스트의 요소를 정렬
  • sort(Compare comp): 비교 함수 comp를 사용하여 리스트의 요소를 정렬
  • begin(): 리스트의 시작 반복자를 반환
  • cbegin() const: 리스트의 시작 반복자를 상수형으로 반환
  • end(): 리스트의 끝 반복자를 반환
  • cend() const: 리스트의 끝 반복자를 상수형으로 반환
  • before_begin() noexcept: 첫 번째 요소 이전의 위치를 나타내는 반복자를 반환
  • cbefore_begin() const noexcept: 첫 번째 요소 이전의 위치를 나타내는 상수 반복자를 반환

#include <iostream>
#include <forward_list>
#include <string>

int main() {
    std::forward_list<std::string> flst = {"apple", "banana", "cherry"};
    auto it = flst.before_begin(); // 첫 번째 요소 이전 위치

    // 첫 번째 요소 이후 위치에 "orange" 생성
    flst.emplace_after(it, "orange");

    auto it = flst.before_begin(); // 첫 번째 요소 이전 위치

    // 첫 번째 요소 이후 위치에 10 삽입
    flst.insert_after(it, 10);
	
     // 리스트의 맨 앞에 "apple" 생성
    flst.emplace_front("apple");

    return 0;
}