뇌를 자극하는 C++ STL 6장) 시퀀스 컨테이너(vector, deque, list)

암흑기를 극복하고 돌아왔다!! 오늘부터 다시 화이팅하는 마음으로 시퀀스 컨테이너를 공부하고자 한다.

 

(혹시 저작권에 문제가 있다면 수정하겠습니다!! 개인적인 공부용으로 정리함을 알려드립니당)

 

https://m.hanbit.co.kr/store/books/book_view.html?p_code=B5912645820

뇌를 자극하는 C++ STL

 

시퀀스 컨테이너 : 저장 원소에 상대적인 순서가 있는 컨테이너

Ex) vector, deque, list

 

모든 컨테이너가 제공하는 멤버함수

clear(), empty()

 

시퀀스 컨테이너가 제공하는 멤버함수

size(), max_size(), front(), back()

 

시퀀스 컨테이너 중 배열 기반 컨테이너가 제공하는 멤버함수(vector, deque)

✔️ []연산자, at()

	속도	안정성
[]연산자	빠름	낮음
at()	느림	높음

 

✔️ 임의 접근 반복자로 +, -, +=, -=, [] 연산 가능

✔️ 반복자를 가리키는 원소의 값을 변경하지 않는다면 상수 반복자를 사용하는 것을 추천한다.

반복자 종류	포인터와의 유사점	비고
일반 반복자(iterator) 예시 : vector<int>::iterator	포인터(int*)	-
상수 반복자(const_iterator) 예시 : vector<int>::const_iterator	상수포인터(const_iterator)	가리키는 원소 변경 불가
cf) const vector<int>::iterator	int * const	반복자를 이동할 수 없음

 

✔️역방향 반복자

정방향 반복자	역방향 반복자	비고
iterator	reverse_iterator
begin()	rbegin()	[begin(), end())
end()	rend()	[rbegin(), rend())

✔️추가 : insert() , 삭제 : erase(), 할당 : assign()

✔️컨테이너 연산자 : ==, !=, <, <=, >=,> 

 

vector

- 크기

size() : 저장 원소의 개수

capacity() : 실제 할당된 메모리 공간의 크기

🔹유일하게 vector만 가진 멤버함수로 원소가 추가될 때마다 새로운 메모리를 재할당할 때의 비효율성을 극복

🔹메모리 확장 정책(이전 capacity + 이전 capacity / 2) 등 컴파일러마다 상이함

max_size() : 컨테이너가 담을 수 있는 최대 원소의 개수

reserve() :  메모리 예약 함수

※ size를 키울 때 capacity가 늘어나지만, size를 줄일 때 capacity가 줄어들지 않는다. 

 

🔸clear() 후 vector의 size는 0이 되지만 capacity는 0이 아니다. 이 경우 swap을 이용해 임시로 생성한 컨테이너 객체 바꾸면 된다.

 

-멤버원소

front(), back() : 첫번째와 마지막 원소의 참조 ➡️원소의 값 수정 가능

 

vector : 하나의 원소가 하나의 메모리 블록에 연속(배열 기반 컨테인)하게 저장된다. insert(), erase(), push_back() 등이 빈번하게 호출된다면 다른 컨테이너를 사용하면 좋다. 

#include <iostream>
#include <vector>
using namespace std;

int main() {
	vector<int> v;

	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);

	//vector<int>::size_type은 vector의 크기, 첨자 형식을 위한 typedef 멤버 형식(unsigned int)
	for (vector<int>::size_type i = 0; i < v.size(); i++)
		cout << v[i] << endl;
	//iterator
	for (vector<int>::iterator iter = v.begin(); iter!= v.end(); ++iter)
		cout << *iter << endl;
	
	v.clear();
	cout << "size : "<< v.size() << " capacity : " << v.capacity() << endl;

	vector<int>().swap(v);
	cout << "size : " << v.size() << " capacity : " << v.capacity() << endl;

}

 

deque

vector은 원소에 접근하고 빠르게 값을 읽고 쓸 수 있으나 새로운 원소가 추가될 때 메모리 재할당과 이전 원소 복사 문제가 발생하여 성능이 저하될 수 있다.

반면 deque는 여러 개의 메모리 블록을 할당하고 사용자에게 하나의 블록처럼 보이게 하는 정책을 사용한다. 원소의 추가 시 메모리가 부족할 때마다 일정한 크기의 새로운 메모리 블록을 할당한다. 

 

🔹앞/뒤으로 삽입 가능 : push_front(), push_back() 

🔹deque의 insert() 멤버 함수는 vector보다 효율적으로 동작한다.

 

deque : vector와 비슷하지만 하나의 메모리 블록이 아닌 여러 메모리 블록에 나뉘어 저장되기 때문에 vector보다 insert(), erase() 멤버 함수가 더 효율적으로 작동한다. 

 

list

list는 노드 기반 컨테이너로 원소가 노드 단위로 저장되며 list는 이중 연결 리스크로 구현된다. 

 

list에만 있는 멤버함수

멤버함수	설명	멤버함수	설명
lt. merge(lt2)	합병 정렬	lt.reverse()	순차열 뒤집기
lt.remove(x)	원소 x 모두 제거	lt.splice(p. lt2)	p가 가리키는 위치에 lt2붙이기

※ merge함수 : 정렬된 두 list를 합병해야 함(정렬 방식은 따르 지정 가능)

 

list에는 없는 멤버함수

노드 기반 컨테이너이므로 at()과 []연산자가 없으며 임의 접근 반복자가 아닌 양방향 반복자를 제공한다.

 

🔹insert(), erase(), splice() : 상수 시간 복잡도

🔹노드 기반 컨테이너의 insert()와 erase() 동작은 반복자를 무효화시키지 않는다. 반복자가 가리키는 원소 자체가 제거되지 않으면 반복자는 그대로 존재한다. 

🔹unique() : 인접한 원소를 유일하게 만드는 멤버함수(모든 원소가 유일하게 만들려면 정렬 + unique())

 

list: 중간에 삽입, 제거가 빈번하고, 원소의 상대적인 순서가 중요할 때 사용하는 컨테이너로 다른 list와 결합할 때 유용하다(splice, merge 등)