15.STL Containers

list<int> l{1,2,3};

l.front() = 1;
l.back() = 3;

// 1 - > 2 -> 3 포인터를 갖고 있다.

컨테이너의 종류

Sequence 컨테이너

→ 삽입 순서를 유지하는 컨테이너

→ array, vector, deque, list, forward_list

Associative 컨테이너

→ 순서가 없거나, 미리 정해진 규칙에 따라 저장하는 컨테이너

→ set, multi set, map, multi map

컨테이너 어뎁터

→ 다른 컨테이너들의 변형 응용

→ stack, queue, priority queue

 

Sequence Container - Array

std::array (C++11)

#include <array>

고정 크기 배열

기존의 정적 배열(raw array)(ex : int arr[5] = {1,2,3,4,5})와 거의 유사함

요소에 대한 직접 접근(constant time)

STL이므로, iterator와 algorithm을 사용 가능

특별한 이유가 없으면 raw array 대신 STL array를 사용

 

array의 초기화 및 대입

array<int , 5> arr1 { {1,2,3,4,5} }; // C++11 style
array<int, 5> arr1 {1,2,3,4,5}; //C++14 style

array<string, 3> names{
	"Ha",
	"Kim",
	"Lee"
};

arr1 = {2, 4, 6, 8, 10};

 

array의 주요 함수들(1)

array<int, 5> {1,2,3,4,5}; //C++14 style

cout << arr.size(); // 5 (배열의 현재 크기 반환)
cout << arr.at(0); // 1 (배열의 0번째 인덱스 값을 반환)
cout << arr[1]; // 2 (배열의 1번째 인덱스 값을 반환)

cout << arr.front(); // 1 (배열의 0번째 인덱스 값을 반환)
cout << arr.back(); // 5 (배열의 마지막 인덱스 값을 반환

 

array의 주요 함수들(2)

array<int, 5> arr{1,2,3,4,5};
array<int, 5> arr1{10,20,30,40,50};

cout << arr.empty(); // 0 (false) (배열의 요소가 있다면 false)
cout << arr.max_size(); // 5 (배열의 최대 크기 반환)

cout << arr.fill(10); // 배열의 모든 요소를 10으로 채움
arr.swap(arr1); // 두 배열을 swap
int *data = arr.data(); // 배열의 주소를 반환

 

Sequence Container - Vector

 

std::vector

#include <vector>

가변 크기 배열

요소에 대한 직접 접근(constant time)

요소의 끝 위치 삽입(push_back) 및 제거(pop_back)(constant time)

임의 위치에 요소의 삽입 및 제거(linear time)

반복자가 유효하지 않을 수 있다.

 

front / back

vector<int> v{1,2,3};

v.front() = 1;
v.end() = 3;

v.push_back(4); // v = {1, 2, 3, 4}

#include <iostream>
#include <vector>

int main(){
	std::vector<int> v{1,2,3,4,5};

	std::cout << v.size() << std::endl; // 5
	std::cout << v.capacity() << std::endl; // 5

	std::cout << v[0]; // 1
	std::cout << v[1]; // 2
	std::cout << v.at(3); // 4

	std::cout << v[-1]; //runtime error
	std::cout << v.at(-1); //exception error
	//예외처리를 함으로써 at이 더 안전할 수 있다.

	std::cout << v.front(); // 1
	std::cout << v.back(); // 5

 

vector의 주요 함수들

Person p1{"Ha", 20};
vector<Person> v;

v.push_back(p1); // add p1 to the back, copy
v.pop_back(); //remove p1 from the back

v.push_back(Person("Lee", 20});

v.emplace_back("Lee", 20);
//same as above statement, but more efficient
//Check how many copy ctor called in push_back

 

vector의 주요 함수들 2

vector<int> v1{1,2,3,4,5};
vector<int> v2{10,20,30,40,50};

cout << v1.empty(); //0 (false)
v1.swap(v2); // swap 2 vector

sort(v1.begin(), v1.end());

auto it = find(v1.begin(), v1.end(), 3); //값 3을 찾음
v1.insert(it, 10); // 1,2, 10, 3, 4, 5 //it 앞에 값 10을 삽입

it = find(v1.begin(), v1.end(), 4);

v1.insert(it, v2.begin(), v2.end());
//1 2 10 3 10 20 30 40 50 4 5

 

Sequence Container - List & Forward List

 

Sequence 컨테이너

연속된 메모리 공간에 저장되지 않음

요소에 대한 직접 접근 불가(.at() 또는 [ ]로 접근 불가)

요소의 위치가 결정되면, 삽입과 삭제가 매우 효율적

 

std::list(C++11)

.#include <list>

 

가변 크기

양방향 연결 리스트

요소에 대한 직접 접근 불가

임의 위치에 빠른 삽입과 삭제(constant time)

특정 요소를 검색(find)하는 데는 linear time

반복자 유효성 보장 안됨

 

list

list<int> l{1,2,3};

l.front() = 1;
l.back() = 3;

// 1 - > 2 -> 3 포인터를 갖고 있다.

 

 

list의 초기화 및 대입

list<int> l1{1,2,3,4,5};
list<int> l2{10, 100};

list<string> names{"kim", "lee", "park"};

l1 = {2,4,5,8,10};

 

list의 주요 함수들

list<int> l1{1,2,3,4,5};

cout << l1.size(); // 5
cout << l1.max_size(); // very large number

cout << l1.front(); // 1
cout << l1.back(); // 5

 

list의 주요 함수들 2

Person p1{"Kim", 20};
list<Person> l;

l.push_back(p1); // add p1 to the back
l.pop_back(); // remove p1 from back

l.push_front(Person{"lee", 21});
l.pop_front(); //remove front element

l.emplace_front("Choo", 25);

 

list의 주요 함수들 3

list <int> l1{1,2,3,4,5};

auto it = find(l1.begin(), l1.end(), 3);

l1.insert(it, 10); // 1 2 10 3 4 5
l1.erase(it); // 1 2 10 4 5 <- it 유효성 사라짐
l1.resize(2); // 1 2
l1.resize(5); // 1 2 0 0 0

cout << *it; // 3
it++;
cout << *it; // 4
it--;
cout << *it; // 3

 

 

std::forward_list(C++11)

#include <forward_list>

 

가변크기

단방향 연결 리스트(메모리 절약)

요소에 대한 직접 접근 불가

임의 위치에 빠른 삽입과 삭제(constant time)

특정 요소를 검색(find)하는 데는 linear time

반복자 유효성 보장 안됨

reverse iterator 사용 불가

forawrd_list<int> l{1,2,3};

l.front() // 1

 

Associative Container - Set

Associative 컨테이너

Key를 사용한 빠른 데이터 검색이 가능

주로 Balanced binary tree 또는 hashset으로 구현됨

대부분의 연산이 빠르게 이루어짐

 

Set

set

Unordered_set

Multiset

Unordered_multiset

 

std::set

#include <set>

 

집합과 유사(중복된 요소 없음)

key에 따라 정렬

요소에 대한 직접 접근 불가

반복자가 유효하지 않을 수 있다.

 

set의 초기화 및 대입

set<int> s{1,2,3,4,5};
set<string> names{"kim", "ha", "oh"};

s = {2,4,6,8,10};

 

set의 주요 함수들

set<int> s{4,1,1,3,2,5}; // 1 2 3 4 5

cout << s.size(); // 5
cout << s.max_sizel // vary large number

//no front or back

s.insert(7) // 1 3 4 5 7

 

set의 주요 함수들 2

Person p1{"kim", 20};
Person p2{"lee", 21};

set<Person> names;

names.insert(p1); // add p1 to the set
auto result = names.insert(p2); // add p2 to the set

 

정렬을 위해 operator< 오버로딩 필요

insert의 결과로 pair<iterator, bool>반환

iterator는 삽입된 위치, 또는 이미 존재하는 요소를 가리키는 반복자 반환

Bool은 성공 또는 실패 결과 반환

 

set의 주요 함수들 3

set<int> s{1,2,3,4,5};

s.erase(3); // 1 2 4 5

auto it = s.find(5);
//algorithm의 find가 아닌 set의 멤버 변수인 find

if(it != s.end())
		s.erase(it); // 1 2 4

 

set의 주요 함수들 4

set<int> s{1,2,3,4,5};

int n = s.count(1); // 0 or 1
s.clear(); // remove all elements
s.epmty(); // true or false

 

multiset

Key로 정렬

요소의 중복 허용

 

unordered_set

요소의 중복 불가

요소가 정렬되지 않음

요소의 수정 불가

 

unordered_multiset

요소가 정렬되지 않음

요소의 중복 허용

 

Associative Container - Map

Associative 컨테이너

Key를 사용한 빠른 데이터 검색이 가능

주로 Balanced binary tree또는 hashset으로 구현됨

대부분의 연산이 빠르게 이루어짐

 

Map

Map

Unordered_map

Multimap

Unordered_multimap

 

std::map

#include<map>

 

Dictionary(사전)과 유사

요소가 key-value 쌍으로 저장됨

Key 값에 따라 정렬

Key는 유일한 값으로 중복 불가

Key를 통한 직접 접근 가능

반복자가 유효하지 않을 수 있음

 

map의 초기화 및 대입

map<string, int> m1{
	{"kim", 20}, {"lee", 21}, {"kim", 25}
};
//중복되는 뒤에 kim 25는 없어짐
map<string, string> m2{
	{"kim", "student"}, {"Lee", "pro"};

 

map의 주요 함수들 1

map<string, string> m{
	{"kim", "stu"}, {"lee", "pro"}
};

pair<string, string> p1{"park", "assi"};
m.insert(p1);
m.insert(make_pair("Choo", "emp"));

 

map의 주요 함수들 2

map<string, string> m{
	{"kim", "stu"}, {"lee", "pro"}
};

m["park"] = "assi"; // insert
m["kim"] = "emp"; // update value
m.at("park") = "stu"; //update value

int n =m.count("kim"); // 0 or 1
m.clear(); //remove all elements
m.empty(); //true or false

 

multimap

#include <map>에 포함

중복된 요소들 허용

 

unordered map

#include <unordered_map>

요소가 정렬되지 않음

 

unordered multimap

#include <unordered_map>에 포함

요소가 정렬되지 않음

중복된 요소를 허용