[C++] STL #1 순차 컨테이너 (Sequence Container) [array, vector, deque, list]

 목차

1. STL

2. array

3. vector

4. deque

5. list

---

1. STL의 구성요소 

STL는 표준 템플릿 라이브러리(Standard Template Library)의 약자이다.

 

컨테이너, 반복자, 알고리즘, 함수자 네 가지의 구성 요소를 제공한다.

가. 컨테이너(Container)

- 데이터를 저장해주는 객체

 

나. 반복자(Iterator)

- 컨테이너에서 보유하고 있는 내부 원소들을 순회할 수 있는 객체

- 포인터와 비슷한 역할을 한다.

 

다. 알고리즘(algorithm)

- 컨테이너 내부 객체를 다루기 위해 검색, 비교, 정렬, 수정 등의 동작을 한다.

- 컨테이너에 따라 사용가능한 알고리즘이 정해져있다. (효율성 때문에 적합하지 않은 컨테이너 미지원)

 

라. 함수자(functor)

- 인자를 받아 알고리즘의 동작을 지원해주고 변형 해주는 객체

- 산술 연산, 비교 연산, 논리 연산에 대한 함수자가 제공된다.

 

 

---

이번 글에서는 STL 컨테이너 중 연속 컨테이너들에 대해 다룰 것 이다.

 

가-A. 순차 컨테이너 (Sequence Container)

- 메모리 상에서 모든 요소가 순차적으로 존재한다.

(※ list 는 주소값 인접은 아니지만 포인터 주소값을 통해서 순차적으로 존재)

벡터 컨테이너 예시

- 연속된 순서로 배치되어 특정 위치에 접근 및 참조가 가능하다 (ex. 3번 인덱스 위치 참조)

 

 

2. std::array

- 고정된 길이의 배열이다. (선언시 배열 크기를 지정해줘야한다)

- 요소의 삽입 및 삭제가 불가능하다.

- 지정된 메모리만 사용하므로 메모리 효율성이 높다.

 

가. 선언 및 초기화

template<typename T>    //template ≒ 자유 자료형

std::array<T,N>        //T : 배열에 담길 자료형, N : 임의의 양의 정수

 

- array<int, 5> arr1 = { 0, 1, 2, 3, 4 };  // 생성과 동시에 초기화

- array<char, 3> arr2;                         // 초기화를 하지 않아 기본 값이 담겨있음. (숫자형은 0, 문자형은 공백)

- array<int, 5> arr3 = {3, 6, 9};            // 선언된 3, 6, 9만 들어있고  나머지는 기본값 0이 담겨있음.

- array<string, 5> arr4;                        

  arr4 = { "one", "two", "three", "four", "five" };    // 생성 이후 초기화도 가능

 

 

나. 멤버 함수             ( ※ 기준 :  array<int, 5> arr = { 0, 1, 2, 3, 4 }; )

※ Iterators(반복자)는 포인터와 비슷한 역할로서 요소의 위치를 가르킨다.

하지만 주소값은 아니기 때문에 일반적인 출력 (ex. cout << itr;) 은 불가능 하며

포인터를 사용하여 위치의 인자를 반환할 수는 있다 (ex. cout << *itr;)

iterators 사용 예시

 

Operations - fill (string 형) 예시

Operations - swap예시

 

 

3. std::vector

- 배열의 길이가 동적으로 변함.

- 자료를 배열 뒤에만 추가 가능 (push_back())

데이터를 넣을 때도 꺼낼 때도 맨 뒤부터 가능하다.

- 요소의 삽입과 삭제가 가능 (배열의 가장 끝에서는 빠르나 앞이나 중간에서는 느리다)

(ex. 만약 index 4번 요소를 삭제하고 싶다면 7 6 5 를 꺼내고 4를 삭제한 뒤 4의 자리부터 5 6 7 을 다시 넣는 방식으로 처리한다)

- 연속된 메모리 공간이 부족할 경우 이전 크기의 1.5배로 키워 새로운 공간에 재할당 하여 확장한다.

메모리 공간 확장 (재할당) 예시

 

 

가. 선언 및 초기화

template<typename T>

std::vector<T>

 

- vector<int> vet1 = { 1, 2, 3, 4, 5};   // 생성과 동시에 초기화

- vector<char> vet2(5);                     // 기본 값이 담겨있는 크기 5의 벡터 생성

- vector<string> vet3(3, "A")              // 모든 원소가 "A" 로 초기화 된 크기 3의 벡터 생성

- vector<int> vet4(vet1)                      // v1의 값을 복사하여 v2 벡터 생성

- vector<int> vet5;                              // 빈 배열 생성

   vet5 = { 0, 1, 2 };                              // 생성 이후 초기화도 가능

- char sample[] = { 'a', 'b', 'c' };                 

   vector<char> vet6(begin(sample), end(sample));  // 다른 배열의 값을 사용해 초기화 가능

 

나. 멤버 함수  (※ 기준 : vector<int> vet = { 1, 2, 3, 4, 5}; )

Element access(요소 접근)
vet.at(N)	N 번째 인자를 반환한다.
vet[N]	N 번째 인자를 반환한다.
vet.front()	첫 번째 인자를 반환한다. (예시 기준 1)
vet.back()	마지막 인자를 반환한다. (예시 기준 5)
vet.data()	배열 주소를 반환한다. (배열의 첫 번째 주소 반환)
Iterators(반복자)
vet.begin()	첫 번째 위치를 가리킨다.
vet.end()	배열의 마지막 위치의 다음을 가리킨다.
vet.rbegin()	배열을 역순으로 뒤집고 첫 번째 위치를 가리킨다.
vet.rend()	배열을 역순으로 뒤집고 마지막 위치의 다음을 가리킨다.
※ vet.cbegin(), vet.cend(), vet.crbegin(), vet.crend()는 (앞에 c가 붙은 멤버 함수)는    위와 같은 역할을 하지만 const가 적용되어 수정이 불가능 하다.
Capacity(용량)  size(), capacity(), max_size() 비교 예시 참조
vet.empty()	배열이 비어있는지 확인하고 bool 값 반환
vet.size()	배열의 크기를 반환한다.
vet.max_size()	배열이 담을 수 있는 최대 크기를 반환 (capacity와는 다르다, 벡터 컨테이너가 가질 수 있는 가장 큰 수를 반환한다)
vet.reserve(N)	N의 크기로 배열의 크기를 지정해둔다. (사용할 크기를 지정하므로서 재할당 횟수를 줄일 수 있다.)
vet.capacity()	배열에 할당 된 공간을 반환한다. (가용공간)
vet.shrink_to_fit()	배열의 가용공간을 배열의 크기로 줄여준다. (capacity를 size로 줄여 대기 중인 공간 제거)
Modifiers(수식어)
vet.clear()	배열의 모든 요소를 지운다. (size만 0가 되고 capacity는 그대로)
vet.insert(iterator, N, num) (N 생략 시 1개만 삽입)	iterator로 지정된 위치에서 부터 N개 만큼 num을 삽입한다. (삽입 위치 뒤의 원소들은 하나씩 뒤로 밀려나고 size는 삽입한 만큼 커진다.) Modifiers - insert 예시 참조
vet.emplace(iterator, num)	insert와 비슷하나 한번에 하나만 추가할 수 있다. 결과는 같으나 생성 과정이 다름.
vet.erase (iterator, iterator)	iterator에서 iterator 전 까지의 원소를 삭제한다. (ex. vet.erase(vet.begin(), vet.begin()+3); => vet = { 3,4,5 };
vet.push_back(num)	배열 끝에 num을 삽입한다.
vet.emplace_back(num)	배열 끝에 num을 삽입한다.
vet.pop_back()	배열의 마지막 원소를 제거한다
vet.resize(N) vet.resize(N, num)	배열의 크기를 N으로 재지정한다. (재할당이 아니므로 주소 동일, capacity 그대로) (크기가 줄어 들면 초과된 요소는 삭제, 늘어났다면 추가된 요소는 num으로 초기화)
vet.swap(vet2)	vet와 vet2의 배열 인자를 교환한다.

※ push_back와 emplace, emplace_back의 차이점!!

- push_back는 배열 외부에서 객체를 생성한 뒤 넣어주고 외부 객체를 지우는 식으로 동작한다.
- emplace는 배열 내부에 바로 값을 넣어준다.

 

※ 그렇다면 외부 생성 과정이 없는 emplace가 더 좋은 것인가??? 아니다!

 

- emplace의 경우 모든 유형의 생성자를 호출하고 push_back 은 암시적으로 해당 벡터가 선언한 타입만 호출한다.

- 이렇게 되면 당장의 에러는 발생하지는 않지만 잘못된 자료가 들어가도 프로그래머가 찾기 어려워진다!!

  즉, 기본적으로 push_back를 사용하는 것이 안전하고 생성량이 많아 이동비용이 비싼 경우에만 emplace를 사용하는 것 이 좋다.

 

 

size(), capacity(), max_size() 비교 예시

 

Modifiers - insert 예시 (index 3 부터 5개의 5를 삽입함)

 

4.std::deque

- vector와 다르게 양쪽에서 삽입, 삭제 접근이 가능하다.

- 연속되어 있는 것 처럼 보이지만 실제 메모리는 쪼개서 보관한다. (인덱스는 연결되어있지만 실제 메모리는 끊겨있음)

ㄴ 확장시 새로운 공간에 재할당 할 필요가 없고 큰 공간을 찾을 필요가 없어 메모리 관리가 효과적이다.

- 단, 실제 메모리가 이어지지 않았기 때문에 포인터 연산이 불가능 하다.

 

- 배열의 앞과 뒤에서 삽입 삭제 속도가 빠르다. (vector에 비해 개선됨)

 

가. 기본 사용법

template<typename T>

std::deque<T>

 

- deque<int> dq1 = { 0, 1, 2, 3, 4 };          // 생성과 동시에 초기화

- deque<double> dq2(10);                       // 기본값이 담겨있는 크기 10의 데크 생성

- deque<char> dq3(5, 'A');                       // 모든 원소가 'A' 로 초기화 된 크기 5의 데크 생성

- deque<int> dq4(dq1);                            // dq1을 복사하여 dq4 데크 생성

- deque<string> dq5;                                // 빈 배열 생성

  dq5 = { "one", "two", "three", "four" };      // 생성 이후 초기화도 가능

- char sample[] = { 'a', 'b', 'c' };                 

   deque<char> dq6(begin(sample), end(sample));  // 다른 배열의 값을 사용해 초기화 가능

 

 

나. 멤버 함수 (※ 기준 : deque<int> vet = { 1, 2, 3, 4, 5 }; )

 

Element access(요소 접근)
dq.at(N)	N 번째 인자를 반환한다.
dq[N]	N 번째 인자를 반환한다.
dq.front()	첫 번째 인자를 반환한다. (예시 기준 1)
dq.back()	마지막 인자를 반환한다. (예시 기준 5)
Iterators(반복자)
dq.begin()	첫 번째 위치를 가리킨다.
dq.end()	배열의 마지막 위치의 다음을 가리킨다.
dq.rbegin()	배열을 역순으로 뒤집고 첫 번째 위치를 가리킨다.
dq.rend()	배열을 역순으로 뒤집고 마지막 위치의 다음을 가리킨다.
※ dq.cbegin(), dq.cend(), dq.crbegin(), dq.crend()는 (앞에 c가 붙은 멤버 함수)는    위와 같은 역할을 하지만 const가 적용되어 수정이 불가능 하다.
Capacity(용량)
dq.empty()	배열이 비어있는지 확인하고 bool 값 반환
dq.size()	배열의 크기를 반환한다.
dq.max_size()	배열이 담을 수 있는 최대 크기를 반환 (데크 컨테이너가 가질 수 있는 가장 큰 수를 반환한다)
dq.shrink_to_fit()	배열의 사용하지 않는 메모리를 해제한다. (데이터가 삭제 되어도 메모리는 할당된 상태기 때문에 사용)
Modifiers(수식어)
dq.clear()	배열의 모든 요소를 지운다.
dq.insert(iterator, N,num) (N 생략 시 1개만 삽입)	iterator로 지정된 위치에서 부터 N개 만큼 num를 삽입한다. (삽입 위치 뒤의 원소들은 하나씩 뒤로 밀려나고 size는 삽입한 만큼 커진다.)
dq.emplace(iterator, num)	insert와 비슷하나 한번에 하나만 추가할 수 있다. 결과는 같으나 생성 과정이 다름.
dq.erase (iterator, iterator)	iterator에서 iterator 전 까지의 원소를 삭제한다. (ex. dq.erase(dq.begin(), dq.begin()+3); => dq= { 3,4,5 };
dq.push_back(num)	배열 끝에 num을 삽입한다.
dq.emplace_back(num)	배열 끝에 num을 삽입한다.
dq.pop_back()	배열의 마지막 원소를 제거한다
dq.push_front(num)	배열 시작에 num을 삽입한다.
dq.emplace_front(num)	배열 시작에 num을 삽입한다.
dq.pop_front()	배열 시작 원소를 제거한다.
dq.resize(N) dq.resize(N, num)	배열의 크기를 N으로 재지정한다. (크기가 줄어 들면 초과된 요소는 삭제, 늘어났다면 추가된 요소는 num으로 초기화)
dq.swap(dq2)	dq와 dq2의 배열 인자를 교환한다.

 

5. list

- 노드 기반 컨테이너

ㄴ 노드란?     원소의 값 과 다음 원소를 가리키는 주소 값을 가진 형태

양방향 노드

 

- 연속 컨테이너긴 하지만 노드 기반이므로 [], .at()을 통해 임의 접근이 불가능하다.

- 배열 중간에 원소를 삽입 / 삭제 하는 속도가 빠르다.

  (새로 추가/ 삭제된 노드와 인접한 주소 포인터 값만 수정해주면 되기 때문)

 

가. 선언 및 초기화

template<typename T> 

std::list<T>        

 

- list<int> li1= { 0, 1, 2, 3, 4 };                   // 생성과 동시에 초기화

- list<double> li2(10);                               // 기본값이 담겨있는 크기 10의 리스트 생성

- list<char> li3(5, 'A');                               // 모든 원소가 'A' 로 초기화 된 크기 5의 리스트 생성

- list<int> li4(li1);                                      // li1을 복사하여 li4 데크 생성

- list<string> li5;                                       // 빈 배열 생성

  li5 = { "one", "two", "three", "four" };       // 생성 이후 초기화도 가능

- char sample[] = { 'a', 'b', 'c' };                  

   list<char> li6(begin(sample), end(sample));  // 다른 배열의 값을 사용해 초기화 가능

 

나. 멤버 함수         ( ※ 기준 :  list<int> li = { 1, 2, 3, 4, 5 }; )

 

Element access(요소 접근)
li.front()	첫 번째 인자를 반환한다. (예시 기준 0)
li.back()	마지막 인자를 반환한다. (예시 기준 5)
Iterators(반복자)
li.begin()	첫 번째 위치를 가리킨다.
li.end()	배열의 마지막 위치의 다음을 가리킨다.
li.rbegin()	배열을 역순으로 뒤집고 첫 번째 위치를 가리킨다.
li.rend()	배열을 역순으로 뒤집고 마지막 위치의 다음을 가리킨다.
※ li.cbegin(), li.cend(), li.crbegin(), li.crend()는 (앞에 c가 붙은 멤버 함수)는    위와 같은 역할을 하지만 const가 적용되어 수정이 불가능 하다.
Capacity(용량)
li.empty()	배열이 비어있는지 확인하고 bool 값 반환
li.size()	배열의 크기를 반환한다.
li.max_size()	배열이 담을 수 있는 최대 크기를 반환 (리스트 컨테이너가 가질 수 있는 가장 큰 수를 반환한다)
Modifiers(수식어)
li.clear()	배열의 모든 요소를 지운다.
li.insert(iterator, N,num) (N 생략 시 1개만 삽입)	iterator로 지정된 위치에서 부터 N개 만큼 num을 삽입한다.
li.emplace(iterator, num)	insert와 비슷하나 한번에 하나만 추가할 수 있다. 결과는 같으나 생성 과정이 다름.
li.erase (iterator, iterator)	iterator에서 iterator 전 까지의 원소를 삭제한다. (ex. auto target = li.begin();   advance(target, 2);        li.erase(li.begin(), target);  => li = { 3, 4, 5 };
li.push_back(num)	배열 끝에 num을 삽입한다.
li.emplace_back(num)	배열 끝에 num을 삽입한다.
li.pop_back()	배열의 마지막 원소를 제거한다
li.push_front(num)	배열 시작에 num을 삽입한다.
li.emplace_front(num)	배열 시작에 num을 삽입한다.
li.pop_front()	배열 시작 원소를 제거한다.
li.resize(N) li.resize(N, num)	배열의 크기를 N으로 재지정한다. (크기가 줄어 들면 초과된 요소는 삭제, 늘어났다면 추가된 요소는 num으로 초기화)
li.swap(li2)	li와 li2의 배열 인자를 교환한다.
Operations(운영)
li.merge(li2)	li와 li2를 병합한다. (뒤에 이어 붙인다)
li3.splice (li3_itr, li1, start_itr, end_itr) (iterator => itr)	li1에서 지정한 만큼 잘라서 li3의 지정 위치에 붙여준다. (붙일 리스트 위치, 자를 대상, 자르기 시작, 자르기 끝) operations - splice 예시 참조
li.remove(num) li.remove_if(조건문)	리스트 내에서 num인 요소를 모두 제거한다. 조건문에 해당되는 요소를 모두 제거한다.
li.reverse()	리스트의 원소를 역순으로 바꾼다.
li.unique()	리스트의 원소가 연속으로 중복되는 요소가 있다면 제거해준다.
li.sort()	리스트의 원소를 정렬한다. (기본 오름차순, 다른 정렬 방식은 sort 함수 내부에 조건 작성) ( ex. 내림차순 : li.sort(greater<int>()); )

 

 

operations - splice 예시 (advance 는 iterator을 받아 두번째 인수만큼 iterator을 증가시켜 준다)

 

 

 

 

※ 참조

emplace_back 과 push_back의 차이 : https://openmynotepad.tistory.com/10

c++ reference : https://en.cppreference.com/