14.STL

STL : Standard template library

템플릿을 사용해 구현된 컨테이너의 집합

널리 사용되는 자료구조와 알고리즘이 구현되어 있음

시간 복잡도는 레퍼런스 문서에서 찾아 볼 수 있다.

Powerful, reusable, adaptable, generic, HUGE

 

구성요쇼

컨테이너

→ 객체 또는 기본 자료형의 집합

→ array, vector, deque, stack, set, map, etc.

→ 각 컨테이너는 관련된 헤더 파일 포함 필요 (#include <컨테이너 이름>)

알고리즘

→ 컨테이너의 요소들을 다루기 위한 알고리즘

→ find, max, count, accumulate, sort, etc.

반복자(iterators)

→ 컨테이너의 요소들에 대한 순회 및 접근

→ forward, reverse, by value, by reference, constant, etc.

 

컨테이너의 종류

Sequential 컨테이너

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

→ array, vector, list, forward_list, deque

Associative 컨테이너

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

→ set, multi set, map, multi map

컨테이너 어댑터

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

→ stack, queue, priority queue

 

컨테이너의 공통 기능

default constructor

overloaded constructors

copy constructors

move constructors

destructor

copy assignment (operator=)

move assignment (operator=)

size()

empty()

insert

operator< and operator≤…

swap

earse

clear

begin and end

rbegin and rend

cbegin and cend

crbegin and crend

 

요소는 복사되어 컨테이너에 저장됨

기본 자료형은 모두 가능

사용자 정의 자료형(클래스)은 복사가 가능하고, 대입이 가능해야 함

→ 즉 복사생성자 / 대입 연산자 필요하다. ← 포인터 멤버 변수가 없다면 ok

Associative 컨테이너의 경우, 비교 연산을 수행할 수 있어야 한다.

→ 즉 operator<, operator== 오버로딩 필요

 

반복자 (iterator)

 

컨테이너의 요소에 대해 추상적인 접근을 가능하게 하는 기능

→ 추상적 : 컨테이너가 무슨 종류인지, 어떻게 구현되어 있는지 알 필요 없다

..포인터와 유사하게 사용 가능

..대부분의 컨테이너는 반복자를 사용해 순환(traverse) 가능

→ stack, queue는 제외

반복자의 선언

반복자가 사용될 컨테이너의 타입을 명시적으로 표기

vector<int>::iterator it1;
//컨테이너 타입<컨테이너 내 요소의 자료형>
list<string>::iterator it2;

map<string, string>::iterator it3;

set<char>::iterator it4;

#include <iostream>
#include <vector>

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

	vector<int>::iterator it1;
	set<int>::iterator it2;

	return 0;
}

 

반복자의 begin과 end

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

// v.begin()은 1
// v.end()은 마지막 요소(3)의 뒤를 가리킴에 주의

 

반복자의 사용

for문과 반복자를 사용한 vector 순환

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

for(auto it = v.begin(); it != v.end(); it++){
	cout << *it << ' ';
}

//1 2 3

while(it != v.end()){
	cout << *it << ' ';
	++it;
}

// 1 2 3

 

반복자의 초기화

vector<int> v{1,2,3}; // 벡터 컨테이너의 선언
vector<int>::iterator it = v.begin();
//벡터 컨테이너의 반복자 선언 및 초기화
auto it = v.begin();
//벡터 컨테이너의 반복자의 효율적인 선언 및 초기화 문법

 

auto 키워드

자동으로 타입을 추정해주는 키워드

타입이 길어질 경우 사용하면 편리

→ 남용할 경우 코드의 가독성을 해칠 수 있다.

int Add(int a, int b){
	return a + b;
}

int main(){
	int a = 5;
	auto b = 5;
	auto c = b;

	auto d = Add(2,3);
}

int main(){
	vector<int> v{1, 4, 7};
	auto it = v.begein();
	it += 2;

	cout << *it; // 7이 출력 됨

 

역 반복자(reverse iterator)

역순으로 동작

마지막 요소가 첫 요소가 되는 반복자

++및 —를 반대 방향으로 생각

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

vector<int>::reverse_iterator it = v.rbegin();

while(it != v.rend()){
	cout << *it <<' ';
	++it;
}

// 3 2 1

 

STL의 알고리즘 (STL Algorithms)

 

반복자에 의해 지정된 요소 집합에 대해 수행되는 알고리즘

매우 다양한 알고리즘이 구현되어 있다.

알고리즘을 사용하기 위해 함수를 인자로써 제공해야 하는 경우가 존재

함수를 인자로써 제공하는 방법

→ Functor

→ Function pointer

→ Lambda expression(C++ 11)

 

알고리즘과 반복자

#include <algorithm>

컨테이너에 따라서 적용할 수 있는 알고리즘이 다름

모든 알고리즘은 반복자를 인자로 필요로 함

 

반복자의 유효성

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

예를 들어 iterator가 가리키고 있는 요소가 삭제되면?

→iterator가 유효하지 않아짐

 

알고리즘 예시 1 : find

find 알고리즘은 컨테이너 내 어떤 요소가 첫 번째로 나타나는 지점을 찾아줌

해당 지점을 가리키는 반복자를 반환하거나, end()를 반환함

→ end()를 반환하는 경우, 해당 요소가 컨테이너 내에 없다는 뜻

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

auto loc = find(v.begin(), v.end(), 3;

if(loc != v.end()){
	cout << *loc << endl; // 2
}

 

find 알고리즘의 사용을 위해서는 요소들을 비교할 수 있어야 함

operator==이 사용되므로, 클래스의 경우 오버로딩이 필요

→ 오버로딩이 되어있어야만 아래 코드처럼 사용 가능

v<Player> team{...}
Player p{"Ha", 100 ,12};

auto loc = find(team.begin(), team.end(), p);

if(loc != v.end()){
	cout << *loc << endl;
}

 

알고리즘 예시 2, for_each

for_each 알고리즘은 컨테이너 내 각 요소를 인자로 함수를 호출

 

컨테이너의 각 요소를 제곱하는 경우의 예제

함수를 인자로 넘기는 방법

→ functor

→ function pointer

→ lambda expression

 

Functor 사용

함수(처럼 사용 가능한) 객체

→( ) 연산자의 오버로딩

struct Square_Functor{
	void operator()(int x) // () 연산자 오버로딩
	{
		cout << x * x << ' ';
	}
};
Square_Functor square; // function object

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

for_each(v.begin(), v.end(), square);
//1 4 9 16

 

function pointer의 사용

함수의 주소값을 인자로 전달

square()와 square의 차이?

→ 함수의 호출 / 함수의 주소값

void square(int x){
	cout << x * x << ' ';
}

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

for_each(v.begin(), v.end(), square);
// 1 4 9 16
//cout << square 을 할 경우 square의 주소값 출력

 

lambda expression의 사용

익명 함수

함수에 이름을 부여하지 않고, 한번 사용하고 버리는 함수 구현에 사용

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

for_each(v.begin(), v.end()), 
	[](int x){
	cout << x * x << ' ';
	}) // lambda

//1 4 9 16