개념
-
정의 (위키백과)
표준 템플릿 라이브러리(STL: Standard Template Library)는 C++을 위한 라이브러리로서 C++ 표준 라이브러리의 많은 부분에 영향을 끼쳤다. 이것은 알고리즘, 컨테이너, 함수자 그리고 반복자라고 불리는 네가지의 구성 요소를 제공한다.
STL은 컨테이너와 연관 배열 같은 C++을 위한 일반 클래스들의 미리 만들어진 집합을 제공하는데, 이것들은 어떤 빌트인 타입과도 그리고 어떤 사용자 정의 타입과도 같이 사용될 수 있다. STL 알고리즘들은 컨테이너들에 독립적인데, 이것은 라이브러리의 복잡성을 눈에 띄게 줄여주었다.
STL은 결과를 템플릿의 사용을 통해 달성한다. 이 접근법은 전통적인 런타임 다형성에 비해 훨씬 효과적인 컴파일 타임 다형성을 제공한다. 현대의 C++ 컴파일러들은 STL의 많은 사용에 의해 야기되는 어떤 추상화 패널티도 최소화하도록 튜닝되었다.
STL은 제네릭 알고리즘과 C++을 위한 데이터 구조체들의 첫 번째 라이브러리로서 만들어졌다. 이것은 다음의 네가지를 기초로 한다. 제네릭 프로그래밍, 효율성을 잃지 않은 추상화, 폰 노이만 구조 그리고 밸류 시멘틱스(value semantics)가 그것이다.
-
구성요소
-
컨테이너(container): 데이터를 저장하는 객체의 집합으로, 연속 컨테이너(sequence container)와 연관 컨테이너(associative container)로 분류됨.
-
반복자(iterator): 컨테이너에 저장된 객체를 참조하는 포인터.
-
알고리즘(algorithm): 정렬, 삭제, 검색 등에 대한 함수를 제공
-
함수 객체(function object): operator()를 오버로드하는 클래스의 인스턴스로, 함수처럼 동작하는 객체. C++에서는 사칙 연산과 관련해서 몇 가지 함수 객체를 제공함. 예를 들면, plus<자료형>()과 times<자료형>() 이 있음. STL의 알고리즘의 인자로 함수 객체를 넘길 수 있는데, 이는 C 언어에서 함수 포인터를 사용했을 때보다 훨씬 빠르게 동작함. 그 이유는 함수 포인터는 실행될 때까지 확인될 수 없기 때문에 인라인(inline)으로 만들어질 수 없으나, 함수 객체는 컴파일 시에 결정되기 때문에 컴파일러는 operator() 호출을 인라인으로 만들어 성능이 증가하기 때문임.
-
어댑터(container adaptor): STL 구성 요소를 새로운 구성 요소로 보이게 하는 기능으로, 다른 컨테이너들을 사용하면서 특정한 인터페이스와 함께하는 컨테이너
-
할당기(allocator): 컨테이너의 메모리 할당 정책을 담당
-
연속 컨테이너 (Sequence Container)
-
표준 연속 컨테이너들은 vector, deque, 그리고 list를 포함.
-
-
STL에서 가장 많이 사용되는 컨테이너 라이브러리
-
C 배열과 같은 동적 배열로서 객체를 삽입하거나 제거할 때 자동으로 자신의 크기를 조정하는 능력을 갖는다.
-
vector의 end에 요소를 삽입하는 것은 상환 상수 시간(amortized constant time)을 필요로 한다.
-
마지막 요소를 제거하는 것은 단지 상수 시간을 필요로 하는데, 크기 조정이 일어나지 않기 때문이다.
-
처음 또는 중간에 삽입하거나 삭제하는 것은 뒤의 원소들을 뒤나 앞으로 옮겨야하므로 선형 시간이 든다.
-
bool 타입을 위한 특수화가 존재하는데 이것은 불린 값을 비트에 저장하기 위해 공간을 최적화한다.
-
메모리 상에서 연속된 위치에 데이터를 저장하므로, memcpy()나 memset() 등의 함수를 이용하여 직접적인 데이터 수정 가능.
-
vector에서 제공하는 자주 쓰이는 멤버 함수로는 push_back(), pop_back(), front(), back() 이 있으며, 함수명에서 알 수 있듯이 뒤쪽에서만 데이터 삽입, 삭제가 가능함. 중간에 데이터를 수정하고 싶다면 다른 라이브러리를 사용해야 함.
-
배열과의 차이점: 크기가 동적으로 변하며, 중간에 데이터 삽입 및 삭제가 가능.
-
배열과의 공통점: 구현이 쉽고, 랜덤 접근(random access)이 가능.
-
미리 크기를 알 수 있는 데이터 저장에 가장 적합하고, 크기가 가변적인 경우라도 뒤쪽에서만 데이터 삽입, 삭제가 빈번하게 발생할 경우 유용하게 사용됨. 그 외에도 랜덤 접근이 자주 발생하고 빠른 속도를 요구할 때 이용됨. 실제로 앞에서 삽입, 삭제가 많이 일어날 경우 다른 컨테이너 사용이 권장됨.
-
vector는 capacity() 함수를 통해 메모리 재할당 없이 최대 늘릴 수 있는 크기를 제공하며, 이는 size() 함수(=원소의 개수)와는 다른 용도임. 즉, 처음 할당 시 지정한 공간보다 넉넉하게 메모리를 잡기 때문에 미리 크기를 알 경우 메모리 재할당에 따른 추가 연산을 막을 수 있음.
-
#include <iostream>
#include <vector>
using namespace std;
int main() {
cout << "Vector" << endl;
vector<int> v;
for (int i = 9; i > 0; i--) {
v.push_back(i);
}
cout << v.front() << endl; // 9
cout << v.back() << endl; // 1
cout << v.size() << endl; // 9
for (vector<int>::iterator iter = v.begin(); iter != v.end(); iter++) {
cout << *iter << ", ";
}
cout << endl;
// or
for (auto it = v.begin(); it != v.end(); it++) {
cout << *it << ", ";
}
cout << endl;
v.pop_back();
cout << v.back() << endl; // 2
cout << v.empty() << endl; // 0 (= false)
// 초기화되지 않은 경우 0으로 채워지지만, 이미 값이 있는 경우 크기만 줄인다.
v.resize(3, 0);
cout << v.size() << endl; // 3
// 9, 8, 7
for (auto it = v.begin(); it != v.end(); it++) {
cout << *it << ", ";
}
cout << endl << "Vector2" << endl;
vector<int> v2;
v2.resize(5, 0);
cout << v2.size() << endl; // 5
for (auto it = v2.begin(); it != v2.end(); it++) {
cout << *it << ", "; // 0
}
cout << endl;
return 0;
}-
-
앞, 뒤 모두에서 데이터 삽입 및 삭제가 가능.
-
다른 기능들이 vector보다 성능이 떨어지기 때문에 자주 사용되지 않음.
-
vector와의 공통점은 메모리 상에 연속된 위치에 데이터가 저장되며, 중간 삽입 및 삭제가 용이하지 않다는 것. 즉, 멤버 함수가 제공되지 않음.
-
대표적인 멤버 함수로는 push_front(), push_back(), pop_front(), pop_back(), front(), back() 이 있음.
-
-
-
자료구조의 이중 연결 리스트를 템플릿으로 구현해 놓은 것으로, 중간에 데이터 삽입 및 삭제가 가장 빠름.
-
메모리 상에서 데이터들이 흩어져서 저장되어 있으므로, vector나 deque처럼 연속된 메모리에 저장되는 컨테이너에 비해 읽는 속도가 굉장히 느림. 캐싱(caching) 작업을 할 때 인접한 메모리들도 함께 가져오기 때문에 list의 경우 캐싱으로 얻는 이점이 다른 컨테이너보다 적음. 또한, list는 각 엔트리마다 이전, 다음 엔트리를 가리키는 포인터를 저장해야 하므로 크기도 vector보다 커서 실제 메모리(물리 메모리) 상에 인접한 곳에 있어도 요소를 적게 가져오게 됨. 따라서 순회가 빈번한 경우 list 는 사용하지 않는 것이 좋음.
-
느린 검색과 접근(선형 시간)을 갖지만, 한 번 위치가 찾아지면 빠른 삽입과 삭제가 가능(상수 시간).
-
대표적인 멤버 함수로는 push_front(), push_back(), pop_front(), pop_back(), front(), back()가 있음.
-
중간에 데이터를 삽입하는 함수로는 insert()가 있고, 삭제하는 함수로는 erase()가 있는데 매개변수에 따라 종류가 3가지로 나뉨.
-
#include <iostream>
#include <list>
#include <vector>
using namespace std;
int main () {
list<int> mylist;
list<int>::iterator it;
// set some initial values:
for (int i = 1; i < 6; ++i) mylist.push_back(i); // 1 2 3 4 5
it = mylist.begin();
++it; // it points now to number 2 ^
mylist.insert(it,10); // 1 10 2 3 4 5
// "it" still points to number 2 ^
mylist.insert(it, 2, 20); // 1 10 20 20 2 3 4 5
--it; // it points now to the second 20 ^
vector<int> v(2, 30);
mylist.insert(it, v.begin(), v.end()); // 1 10 20 30 30 20 2 3 4 5
// ^
cout << "mylist contains:";
for (it = mylist.begin(); it != mylist.end(); ++it)
cout << ' ' << *it;
cout << '\n';
return 0;
}
/*
mylist contains: 1 10 20 30 30 20 2 3 4 5
*/#include <iostream>
#include <list>
using namespace std;
int main ()
{
list<int> mylist;
list<int>::iterator it1, it2;
// set some values:
for (int i=1; i<10; ++i) mylist.push_back(i * 10);
// 10 20 30 40 50 60 70 80 90
it1 = it2 = mylist.begin(); // ^^
advance(it2, 6); // ^ ^
++it1; // ^ ^
it1 = mylist.erase(it1); // 10 30 40 50 60 70 80 90
// ^ ^
it2 = mylist.erase(it2); // 10 30 40 50 60 80 90
// ^ ^
++it1; // ^ ^
--it2; // ^ ^
mylist.erase(it1, it2); // 10 30 60 80 90
// ^
cout << "mylist contains:";
for (it1=mylist.begin(); it1!=mylist.end(); ++it1)
cout << ' ' << *it1;
cout << '\n';
return 0;
}
/*
mylist contains: 10 30 60 80 90
*/
연관 컨테이너 (Associative Container)
-
키(Key)와 값(Value)의 짝(pair)으로 이루어진 자료구조(아닌 것도 있으나 자주 사용되지 않음)를 구현한 컨테이너.
-
저장된 자료의 순서와 상관없이 특정 기준에 맞게 저장(주로 키 값의 정렬 순서대로 저장).
-
간단한 연관 컨테이너로 pair와 tuple이 있음.
-
-
데이터 요소의 2-튜플 또는 객체들로(고정된 순서에 따라 변수명.first 그리고 변수명.second로 접근 가능) 이루어짐.
-
STL 내부적으로 많이 사용되며, 함수의 리턴 값이 2개가 필요할 경우 사용됨.
-
map 또는 hash_map 에서 할당된 객체들의 배열은 기본 값으로 pair 타입을 가지며, 배치 및 복사 그리고 비교할 수 있음.
-
비교 시 모든 first 요소들이 유니크 키로서 동작하고 second 요소는 키에 매핑되는 값 혹은 객체로 동작함.
-
다른 컨테이너에 자료형으로 pair를 쓰는 경우 make_pair<자료형, 자료형>(값, 값) 함수로 pair 객체를 만들어서 컨테이너에 저장함.
-
C++11 부터 emplace_back() 이라는 함수를 제공하여 객체를 받는 대신, 객체의 생성자의 매개변수를 받아 vector 내부에서 직접 객체를 생성하므로 임시 객체를 생성하고 파괴 및 복사하는 추가 연산이 필요 없음.
-
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<pair<int, double> > v;
v.push_back(make_pair(3, 5.0)); // same as "v.emplace_back(3, 5.0);"
pair<int, double> p;
p.first = 10;
p.second = 15.5;
v.push_back(p);
cout << p.first << ", " << p.second << endl;
return 0;
}-
-
3개 이상의 값을 반환하거나 저장할 때 사용되는 컨테이너.
-
pair와 유사하게 make_tuple<자료형, 자료형, ..., 자료형>(값, 값, ..., 값) 함수로 객체를 생성할 수 있음.
-
그러나 값을 꺼내올 경우 get<인덱스>(변수명) 를 사용하여야 함. (멤버 함수 아님.)
-
#include <iostream>
#include <tuple>
using namespace std;
int main() {
tuple<int, double, bool> T(10, 15.5, true);
// or
T = make_tuple<int, double, bool>(10, 15.5, true);
cout << get<0>(T) << endl; // 10
cout << get<1>(T) << endl; // 15.5
cout << get<2>(T) << endl; // 1 (=true)
return 0;
}-
표준 연관 컨테이너들은 set, multiset, map, multimap, unordered_set, unordered_map, unordered_multiset 그리고 unordered_multimap를 포함하며, 모두 정렬된 구조.
-
정렬되지 않는 경우 명칭이 "unordered_컨테이너명"가 됨.
-
보통 키를 기준으로 정렬하기 때문에 중복된 키 값을 입력할 수 없으나, mutli-가 붙은 컨테이너들은 중복된 키를 가질 수 있음.
-
-
하나의 데이터 아이템(키)에서 다른 것(값)으로 매핑을 허용.
-
키의 타입은 반드시 비교 연산 < 또는 명시된 커스텀 비교자를 통해 구현되어야 함. (map<자료형, 자료형, 비교자> 로 선언)
-
이러한 비교 연산 또는 비교자 함수는 반드시 strict weak ordering을 보장해야 하며, 아니면 행위가 정의되지 않음.
-
일반적으로 자가 균형 이진 탐색 트리(Red-Black Tree)를 사용해서 구현됨.
-
자주 사용되는 멤버 함수로는 insert(), erase(), find(), count() 등이 있음.
-
정렬된 상태로 많은 데이터를 저장하고, 빠른 검색이 필요하며, 삽입 및 삭제 연산이 빈번하게 일어나지 않는 경우에 굉장히 효율적으로 사용됨.
-
multimap 같은 키(Key)로 여러 개의 값(Value) 입력 가능. #include <map>
-
unordered_map C++11에서 해시 테이블로 구현된 것으로, 정렬되지 않으나, 검색 속도가 빠름. #include <unordered_map>
-
unordered_multimap 같은 키(Key)로 여러 개의 값(Value) 입력 가능하며, 정렬되지 않은 상태로 저장. #include <unordered_multimap>
-
#include <iostream>
#include <map>
using namespace std;
int main() {
map<int, double> m;
// How to insert
m.insert(make_pair<int, double>(5, 10.1));
m.insert(pair<int, double>(3, 15.5));
m.insert({7, 8.123}); // using initializer_list
m.emplace(1, 5.5); // C++11
m[123] = 0.3145723;
// How to read
cout << m[3] << endl; // 15.5
for (auto it = m.begin(); it != m.end(); it++) {
cout << "(" << it->first << ", " << it->second << ")" << endl;
}
// How to delete
map<int, double>::iterator it = m.find(3);
m.erase(it); // erasing by iterator
m.erase(1); // erasing by key
it = m.find(7);
m.erase(it, m.end()); // erasing by range
cout << "After deleting ..." << endl;
for (auto it = m.begin(); it != m.end(); it++) {
cout << "(" << it->first << ", " << it->second << ")" << endl;
}
return 0;
}
/*
$ g++ test.cpp -std=c++11
$ ./a.out
15.5
(1, 5.5)
(3, 15.5)
(5, 10.1)
(7, 8.123)
(123, 0.314572)
After deleting ...
(5, 10.1)
*/-
-
키(Key)만으로 이루어진 이진트리 자료구조로, map과 마찬가지로 자가 균형 이진 탐색 트리(Red-Black Tree)로 구현됨.
-
수학의 집합(set)을 표현한 자료구조이기 때문에, 집합 연산(union, intersection, difference, symmetric difference) 그리고 포함 테스트를 제공.
-
키의 타입은 반드시 비교 연산 < 또는 명시된 커스텀 비교자 함수를 통해서 구현되어야 함.
-
이러한 비교 연산 또는 비교자 함수는 반드시 strict weak ordering을 보장해야 하며, 아니면 행위가 정의되지 않음.
-
map과 마찬가지로 자주 사용되는 멤버 함수로는 insert(), erase(), find() 등이 있음.
-
정렬된 상태로 많은 데이터를 저장하고 빠른 검색 속도를 필요로 하는 경우 (특정 값의 유무를 파악해야 할 때 등) 효율적으로 사용됨.
-
mutliset 중복 요소들을 허용. #include <set>
-
unordered_set C++11에서 해시 테이블로 구현됨. 정렬되지 않은 대신 검색 속도가 빠름. #include <unordered_set>
-
unordered_mutliset 중복 요소 허용 및 정렬되지 않으나 빠른 검색 속도 제공. #include <unordered_set>
-
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> s{9, 7, 5, 1, 3}; // 1, 3, 5, 7, 9
s.insert(4); // 1, 3, 4, 5, 7, 9
s.insert(4); // no new element inserted.
for (auto it = s.begin(); it != s.end(); it++)
cout << (*it) << ", ";
cout << endl;
auto found = s.find(5);
if (found != s.end())
cout << "Found:" << *found << endl;
cout << endl << "After inserting 123:" << endl;
s.insert(found, 123);
for (auto it = s.begin(); it != s.end(); it++)
cout << (*it) << ", ";
cout << endl;
cout << endl << "After inserting an array:" << endl;
int arr[] = {20, 21, 23, 25};
s.insert(arr, arr + 4);
for (auto it = s.begin(); it != s.end(); it++)
cout << (*it) << ", ";
cout << endl;
cout << endl << "After erasing:" << endl;
found = s.find(4);
s.erase(found); // erasing by iterator
s.erase(9); // erasing by key
found = s.find(23);
s.erase(found, s.end()); // erasing by range
for (auto it = s.begin(); it != s.end(); it++)
cout << (*it) << ", ";
cout << endl;
return 0;
}
/*
$ g++ test.cpp -std=c++11
$ ./a.out
1, 3, 4, 5, 7, 9,
Found:5
After inserting 123:
1, 3, 4, 5, 7, 9, 123,
After inserting an array:
1, 3, 4, 5, 7, 9, 20, 21, 23, 25, 123,
After erasing:
1, 3, 5, 7, 20, 21,
*/
반복자(Itrerator)
-
컨테이너 내 객체를 참조하는 포인터로, 컨테이너명<자료형>::iterator 변수명 = ... 으로 선언하여 사용함.
-
++나 --, 그리고 -> 또는 *과 같은 포인터 연산이 대부분 그대로 사용됨.
-
우항에는 일반적으로 컨테이너명.begin(); 이 들어가는데, begin()과 end()는 0번 인덱스와 마지막 인덱스 + 1의 위치를 참조하고 있음.
-
반대로 순회하길 원할 경우 rbegin()과 rend()를 활용하면 됨.
-
반복자의 종류로는 Input, Output, Forward, Bidirectional, Random Access가 있음.
-
Input과 Output은 입/출력을 담당하는 최소한의 기능만을 가진 반복자.
-
Forward와 Bidirectional은 순회하는 방향에 따라 지어진 이름으로, 각각 순방향과 양방향을 의미함. 즉, bidirectional 반복자는 양방향으로 이동하면서 데이터를 참조할 수 있음.
-
Random Access는 말 그대로 무작위로 데이터에 접근할 수 있는 반복자.
-
포함 범위: Input/Output < Forward < Bidirectional < Random Access
-
-
각 컨테이너의 반복자를 반환하는 멤버 함수로 begin(), end(), rbegin(), rend(), cbegin(), cend(), crbegin(), crend()가 있음.
-
begin()과 end()는 순방향으로 데이터를 조회하기 위한 함수.
-
rbegin()과 rend()는 반대로 순회(역방향)하기 위해 각각 마지막 원소와 첫 원소 - 1 의 위치를 참조함.
-
cbegin()과 cend()는 auto 키워드를 사용할 경우 상수 타입(const)의 반복자를 받지 못하는 문제를 개선하기 위해 C++11부터 도입된 것으로 상수 반복자를 반환함.
-
crbegin()과 crend()는 역방향 상수 반복자를 반환.
-
-
auto 키워드 사용 시 상수 반복자를 반환하는 멤버 함수를 사용해야 함.
-
auto it = v.cbegin();
-
'Programming Language > C++' 카테고리의 다른 글
| 표준 템플릿 라이브러리(STL) - 변경 가능 알고리즘 (0) | 2020.11.20 |
|---|---|
| 표준 템플릿 라이브러리(STL) - 변경 불가 알고리즘 (0) | 2020.11.19 |
| 템플릿(Template) (0) | 2020.11.16 |
| 예외 처리(Exception Handling) (0) | 2020.11.16 |
| 객체 지향 프로그래밍(Object-Oriented Programming) - 4 (0) | 2020.11.15 |