C++ STL

STL 은 간단하게 객체를 담는 '컨테이너', 객체에 접근하는 '반복자', 객체를 다루는 '알고리즘'으로 이루어졌다고 할 수 있다.

 

 

STL 컨테이너 종류(container)

선형 컨테이너

• array
  • #include <array>

• vector
  • #include <vector>

• list
  • #include <list>

• forward_list
  • #include <forward_list>

• deque
  • #include <deque>

컨테이너 어답터

• stack
  • #include <stack>
• queue
  • #include <queue>
• priority_queue
  • #include <queue>

연관 컨테이너

• set (tree)
  • #include <set>
• map (tree)
  • #include <map>
• unorder_set (hash table)
  • #include <unorder_set>
• unorder_map (hash table)
  • #include <unorder_map>

 

STL 컨테이너의 공통적인 특징

1. 대부분 컨테이너의 멤버 함수가 동일하다

STL의 장점으로 코드를 수정하지 않고 컨테이너 교체가 가능하다

 

앞에 넣기 / 빼기

• push_front()
• pop_front()
• front()

뒤에 넣기 / 빼기

• push_back()
• pop_back()
• back()

중간에 넣기 / 빼기

• insert()
• erase()

주의) vector 는 push_front() 가 없음!

(자료구조 특성상 앞쪽에 요소를 넣는 것이 성능에 좋지 않으므로...)

 

2. 제거와 반환을 동시에 하지 않는다

pop_front() / pop_back() 함수는 제거만 하고,

front() / back() 함수는 반환만 한다!

 

 

컨테이너 생성하는 방법

#include <iostream>
#include <list>
#include <vector>


int main() {
	std::list<int> s1;
	std::list<int> s2(10); // 10개를 0으로 초기화
	std::list<int> s3(10, 3); // 10개를 3으로 초기화
	std::list<int> s4{10, 3}; // 2개를 10, 3으로 초기화
	std::list<int> s5 = {10, 3};
	std::list<int> s6 = {1,2,3,4,5,6,7};
	std::list<int> s7{1,2,3,4,5,6,7};
	std::list s8 = {1,2,3,4,5,6,7}; // std::list<int> 로 초기화 C++17 부터 사용 가능
}

 

 

---

 

예제

1. 1~10으로 초기화된 vector 만들기
2. push_back 함수를 사용해서 끝에 20을 추가하세요
3. 모든 요소를 출력해 보세요
   1.  [ ] 연산자 사용 - vector, deque는 가능하지만 list는 불가능
   2. range for 사용 (for (auto &n : v)) - list 도 사용 가능
   3. 반복자를 사용
4. 정렬하고 합을 구하고 검색,등 보다 많은 작업 하려면 알고리즘 을 알아야 한다

#include <iostream>
#include <vector>

int main() {
	std::vector<int> v = {1,2,3,4,5,6,7,8,9,10};

	v.push_back(20);

	for (int i = 0; i <v.size(); i++) {
		std::cout << v[i] << std::endl;
	}

	for(auto& n : v) {
		std::cout << n << std::endl;
	}

}

 

 

 

 

STL 반복자 (iterator)

배열 요소에 접근하는 방법

• 배열의 연산자를 사용
• 포인터를 사용해서 접근

#include <iostream>
#include <vector>
#include <list>

int main() {
	int x[10] = {1,2,3,4,5,6,7,8,9,10};
	int *p1 = x;
	++p1;
	*p1 = 20;
}

반복자 (iterator) 란?

• 포인터와 유사하게 동작하는 객체로서, 반복자를 사용하면 컨테이너의 모든 요소를 순차적으로 접근할 수 있다.

반복자의 장점

• 컨테이너의 내부 구조(메모리 구조)에 상관없이 동일한 방법으로 요소에 접근 가능하다

#include <iosteram>
#include <vector>
#include <list>

int main() {
	std::list<int> v = {1,2,3,4,5,6,7,8,9,10};
	auto p2 = v.begin();
	++p2;
	*p2  20;
	++p2;
	std::cout << *p2 << std::endl;
}

 

 

반복자의 데이터 타입

컨테이너 이름 :: iterator

ex) std::vector<int>::iterator

 

#include <iostream>
#include <vector>
#include <list>


int main() {

	std::vector<int> v = {1,2,3,4,5,6,7,8,9,10};
	// std::vector<int>::iterator p1 = v.begin();
	auto p1 = v.begin(); // 1을 가리킴

	auto p2 = v.end(); // end는 10을 가리키는게 아니라 10 다음을 가리키게 됨
}

주의) end() 로 얻은 반복자는 컨테이너의 마지막 다음을 가리킨다

• past the end
• end() 로 얻은 반복자를 사용해서 요소에 접근하면 안된다
• 끝에 도달했는지 확인하는 용도로 사용한다.

while(p1 != p2) {
	std::cout << *p1 << std::endl;
	++ p1;
}

 

 

반복자를 꺼내는 방법

#include <iostream>
#include <vector>
#include <list>

int main() {
	// std::list<int> v = {1,2,3,4,5,6,7,8};
	int v[10] = {1,2,3,4,5,6,7,8};
	// auto p1 = v.begin();
	// auto p2 = v.end();
	auto p1 = std::begin(v);
	auto p2 = std::end(v);

	while(p1 != p2) {
		std::cout << *p1 << std::endl;
		++p1;
	}
}

1. 멤버 함수 사용

v.begin() / v.end()

** 배열에 사용할 수 없다

 

2. 일반 함수 사용 (C++11 부터)

std::begin(v) / std::end(v)

** 배열에 사용할 수 있다

 

 

컨테이너의 모든 요소를 열거하는 방법

1. 배열 연산자 ([])

연속된 메모리와 유사한 구조를 가진 경우만 가능

vector , array, deque, string

• list 나 forward_list 는 [] 연산자 사용 불가능

for (int i = 0; i < v.size(); i++) {
	std::cout << v[i] << std::endl;
}

배열에서도 사용 가능하도록 v.size() 대신 std::size(v) 사용

 

 

2. 반복자 사용

모든 컨테이너 사용 가능

auto p1 = std::begin(v);

while(p1 != std::end(v)) {
	std::cout << *p1 << std::endl;
	++p1;
}

 

 

3. range for 구문 사용

모든 컨테이너 사용 가능

for (auto &n : v) {
	std::cout << n << std::endl;
}

복사본을 만들지 않기 위해 & 를 붙여주자

 

 

 

 

 

---

STL 알고리즘 특징

알고리즘 이란?

어떤 문제를 해결하기 위한 절차, 방법, 명령어 들의 집합

STL 알고리즘 이란?

C++ 표준 라이브러리인 STL 이 제공하는 함수

• 정렬, 검색, 순열, 등 다양한 알고리즘 구현한 함수의 집합

STL 알고리즘의 특징

• 멤버 함수가 아닌 일반 함수 (템플릿) 으로 제공 된다

→ 하나의 함수(템플릿)으로 다양한 컨테이너에 사용할 수 있다 (자료구조에 독립적)

→ 대부분 알고리즘은 함수의 인자와 반환 타입으로 반복자를 사용

반복자를 사용하게 되면, 컨테이너의 내부 구조에 상관없이 동일한 방법으로 요소에 접근할 수 있다

• <algorithm> 헤더가 필요하다
• 대부분의 알고리즘이 반복자 를 필요로 한다

 

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>

int main() {
	std::list<int> s = {1,2,3,4,5,6,7,8,9,10};
	std::vector<int> v= {1,2,3,4,5,6,7,8,9,10};

	// s.find(5); X

	std::find(begin(v), end(v), 3);

}

 

 

검색 알고리즘 (find)

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>

int main() {
	int x[10] = {1,2,3,4,5,6,7,8,9,10};
	std::list<int> s = {1,2,3,4,5,6,7,8,9,10};
	std::vector<int> v= {1,2,3,4,5,6,7,8,9,10};

	// auto p = std::find(begin(v), end(v), 3);
	auto p = std::find(x, x+10, 3); // x+9 가 아니라 x의 다음주소인 x+10 넣어야 한다

}

• 2개의 반복자 ([first, last), 구간) 와 검색할 값을 받아 선형검색을 수행하는 알고리즘
  • first 는 검색 대상에 포함되지만, last는 검색 대상에 포함되지 않는다

반환값

검색 성공시 - 요소를 가리키는 반복자

실패시 - last // null 아님!

if ( p == end(v)) {
	// 실패
} else {
	// 성공
    std::cout << *p << std::endl;
}

 

 

STL 알고리즘과 조건자

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
	std::vector <int> v = {10,9,8,7,6,5,4,3,2,1};
	// v 안에서 처음 나오는 3의 배수를 구해보세요
	auto p = std::find(begin(v), end(v), 3);
	std::cout << *p << std::endl;

}

find_if ([first, last),함수)

bool foo(int n) {
	return n % 3 = 0;
}


...

auto p = std::find_if(begin(v), end(v), foo);

 

 

 

조건자 predicator

• bool 을 반환하는 함수, 함수 객체, 람다 표현식
• _if 로 끝나는 알고리즘에 전달되어 정책으로 사용된다

auto p = std::find_if(begin(v), end(v), [](int n) { return n % 3 == 0;});

 

 

 

더많은 알고리즘 종류를 보고 싶다면?

cppreference.com algorithm library 참조

 

 

 

 

---

예제

1. -1을 입력할 때 까지 입력을 받아 vector에 보관해라 → push_back 사용
2. 입력한 값 중 10 보다 큰 값은 모두 0 으로 변경해라 → replace / replace_if 알고리즘 사용
3. 모든 요소의 합을 구해서 출력해라 → accumulate 알고리즘 사용 (numeric 헤더에 존재)
4. vector의 모든 요소를 내림차순 정렬(sort) 해서 출력하세요 → sort 알고리즘 + 조건자 사용
5. vector의 모든 요소를 1로 채워서 출력해보세요 → fill 알고리즘 사용

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>


using namespace std;

int main() {
	vector<int> v;
	int n = 0;

	while(1) {
		cin >> n;
		if (n == -1) break;
		v.push_back(n);
	}

	for (auto &n : v) {
		if (n >= 10) n = 0;
	}
	// replace 알고리즘 사용
	replace_if(begin(v), end(v), [](int n) { return n>=10; }, 0);

	// 모든요소의 합을 구하는 알고리즘 -> accumulate 알고리즘
	int sum = accumulate(begin(v), end(v), 0);

	// sort (begin(v), end(v)); // 오름차순, 퀵소트
	sort(begin(v), end(v), [](int a, int b) { return a > b; }); // 내림차순 정렬
	
	// 모든 요소 1로 채우기
	fill(begin(v), end(v), 1);

}