- STL을 원하는 만큼 사용 가능
Containers(vector/list/map ...), Algorithms(<algorithm>) - 템플릿은 헤더 파일에 구현
원하면 헤더에 선언하고.tpp파일에 구현해도 됨
ex00 - Easy find
개념
STL(Standard Template Library)
표준 템플릿 라이브러리
- 컨테이너(container): 임의 타입의 객체 보관
- 반복자(iterator): 컨테이너에 보관된 원소에 접근
- 알고리즘(algorithm): 반복자를 가지고 일련의 작업을 수행
컨테이너(container)
https://cplusplus.com/reference/stl/
여러 객체들을 보관하는 보관소
- 클래스 템플릿 형태로 구현되어 있어서 임의 타입의 원소를 위한 컨테이너 생성 가능
- 하나의 컨테이너에는 한 가지 타입의 원소들만 보관할 수 있음
- 각 원소들의 메모리를 관리해주고, 각 원소에 접근하는 멤버 함수를 제공
- 함수를 호출하거나 반복자(iterator)를 이용해서 접근 가능
반복자(iterator)
http://tcpschool.com/cpp/cpp_iterator_intro
https://ansohxxn.github.io/stl/chapter16-2/
컨테이너 원소에 접근할 수 있는 포인터 같은 객체
- 컨테이너의 구조나 원소의 타입과 상관없이 컨테이너에 저장된 데이터를 순회할 수 있음
- 포인터를 일반화한 것
- 컨테이너 멤버 함수인
begin()과end()로 반복자를 얻을 수 있음begin(): 첫 번째 원소를 가리키는 반복자 리턴end(): 마지막 원소 한 칸 뒤를 가리키는 반복자 리턴 (빈 벡터를 표현하기 위함)
- 반복자가 가리키는 값을 바꿀 수 없는
const_iterator(cbegin(),cend())
컨테이너 뒤부터 순회하는reverse_iterator(rbegin(),rend())
두 특징을 모두 갖는const_reverse_iterator(crbegin(),crend())
❗️const반복자들은 C++11 부터 추가됨
알고리즘(algorithm)
https://modoocode.com/225
컨테이너에 대해 반복자를 가지고 여러 작업을 쉽게 수행할 수 있도록 도와주는 라이브러리
- 정렬, 탐색, 조건 삭제 등 가능
시퀀스 컨테이너(sequence container)
http://tcpschool.com/cpp/cpp_container_sequence
배열처럼 객체들을 순차적으로 보관
- vector, list, deque
- 일반적인 상황에서는 벡터 사용
- 중간에 원소를 추가하거나 삭제하는 일이 많고, 순차적인 접근만 하는 경우 리스트 사용
- 맨 처음과 끝에 원소를 추가하거나 삭제하는 일이 많으면 덱 사용
벡터(vector)
가변길이 배열
- 실제로 메모리상에 순차적으로 저장됨
👉 임의 위치의 원소에 빠르게 접근 가능 - 가지고 있는 원소의 개수보더 더 많은 공간을 미리 할당해두기 때문에 맨 뒤에 원소를 추가하거나 삭제하는 작업이 빠름
O(1)- 할당된 공간이 다 찼을 때는 새로운 공간을 다시 할당하고 복사하기 때문에 시간복잡도가
O(n)으로 늘어나지만 이렇게 수행되는 경우가 드물기 때문에 빠르다고 함
- 할당된 공간이 다 찼을 때는 새로운 공간을 다시 할당하고 복사하기 때문에 시간복잡도가
- 임의 위치에 원소를 추가하거나 제거하려면 뒤의 원소들을 이동시켜줘야 하기 때문에 시간복잡도가
O(n)으로 느림 - 원소 접근: 배열처럼
[]를 이용하거나at()함수 사용 - 원소 추가:
push_back()(임의 위치:insert()) - 원소 제거:
pop_back()(임의 위치:erase()) - 원소 개수:
size() - 할당된 메모리에 저장할 수 있는 총 원소 개수:
capacity()
// constructing vectors
#include <iostream>
#include <vector>
int main ()
{
// constructors used in the same order as described above:
std::vector<int> first; // empty vector of ints
std::vector<int> second (4,100); // four ints with value 100
std::vector<int> third (second.begin(),second.end()); // iterating through second
std::vector<int> fourth (third); // a copy of third
// the iterator constructor can also be used to construct from arrays:
int myints[] = {16,2,77,29};
std::vector<int> fifth (myints, myints + sizeof(myints) / sizeof(int) );
std::cout << "The contents of fifth are:";
for (std::vector<int>::iterator it = fifth.begin(); it != fifth.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}리스트(list)
양방향 연결 리스트
- 임의 위치의 원소에 바로 접근할 수 없음 (
[]나at()사용 불가)- 반복자 연산에서
itr++,iter--등은 가능하지만iter + 5처럼 임의의 위치에 접근하는 것도 불가능
👉 원소들이 메모리에 연속적으로 존재하지 않을 수 있기 때문!
- 반복자 연산에서
- 임의 위치에 원소를 추가(
insert())하거나 제거(erase())할 때 앞 뒤 링크만 바꾸면 되므로 빠름O(1)
덱(deque)
- 임의 위치 원소 접근 및 맨 뒤나 맨 앞에 원소 추가 제거 작업이 빠름
O(1)push_front()와pop_front()가능
- 임의 위치 원소 추가 및 제거는 벡터와 마찬가지로
O(n)이지만 더 빠름
👉 새 공간을 할당하고 복사하는 연산 없이 새 블록을 할당하고 추가하기만 하면 되기 때문 - 원소들이 메모리상에 연속적으로 존재하지 않고 일정 크기로 잘려서 각각의 블록 속에 존재
👉 각 블록들의 위치를 저장하기 위한 벡터가 필요하므로 추가 메모리 공간 사용 - 벡터와 다르게 새로 할당 시 앞 뒤 모두에 공간을 남겨둠
구현
함수 템플릿 easyfind() 구현
- 첫 번째 인자는
T, 두 번째 인자는int T는 integer 컨테이너- 두 번째 인자로 전달된 값이 처음으로 등장하는 위치 찾기
👉<algorithm>의find()사용
(해당 값이 존재하지 않으면 마지막 이터레이터를 리턴) - 발견되지 않는 경우 예외를 던지거나 에러 값을 리턴 (둘 중 선택)
- 연관 컨테이너(associative containers)를 다룰 필요는 없음
ex01 - Span
구현
- 최소 10000개의 숫자로 테스트
- 반복자의 범위를 전달하여 숫자를 추가하면
addNumber()를 여러번 추가하는 것을 방지할 수 있음
Span 클래스
- 최대
N개의 정수를 저장 - 생성자에서 unsignend int
N을 받음
멤버 함수
addNumber()Span에 하나의 숫자를 추가- 이미
N개의 원소가 있는데 추가하려고 하면 예외 던지기
shortestSpan(),longestSpan()- 저장된 숫자들 중 가장 값이 작은 차와 큰 차 구하기
- 숫자가 저장되어 있지 않거나 하나만 있어서 값을 찾을 수 없는 경우 예외 던지기
<algorithm>의min_element(),max_element(),sort(),
<numeric>의adjacent_difference()활용
- 한번에 많은 숫자를 추가하는 함수
insert()로 범위에 해당하는 값을 모두 추가할 수도 있음- 두 반복자 사이에 들어갈 수 있는 원소의 개수는
distance()로 구함
테스트 코드
int main(void)
{
Span sp = Span(5);
sp.addNumber(6);
sp.addNumber(3);
sp.addNumber(17);
sp.addNumber(9);
sp.addNumber(11);
std::cout << sp.shortestSpan() << std::endl;
std::cout << sp.longestSpan() << std::endl;
return (0);
}- 결과
$> ./ex01
2
14
$>ex02 - Mutated abomination
개념
컨테이너 어댑터(container adaptor)
기존 컨테이너의 인터페이스를 제한하여 기능이 제한되거나 변형된 컨테이너
- 기반 클래스의 인터페이스를 제한하여 특정 형태의 동작만을 수행
- 반복자를 지원하지 않음
👉 STL 알고리즘 사용 불가 - stack, queue, priority_queue
스택(stack)
LIFO(후입선출) 방식의 구조
template<class T, Class C = deque<T> >
class std::stack {
protected:
C c;
public:
typedef typename C::value_type value_type;
typedef typename C::size_type size_type;
typedef C container_type;
explicit stack(const C& a = C()) : c(a){} // Inherit the constructor
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
value_type& top() const { return c.back(); }
const value_type& top() const { return c.back(); }
void push(const value_type& n) { c.push_back(n); }
void pop() { c.pop_back(); }
};- vector, deque, list로 구현될 수 있지만, 명시하지 않으면 기본적으로 deque 사용
- 멤버 함수
empty()size()top()push()pop()
// constructing stacks
#include <iostream> // std::cout
#include <stack> // std::stack
#include <vector> // std::vector
#include <deque> // std::deque
int main ()
{
std::deque<int> mydeque (3,100); // deque with 3 elements
std::vector<int> myvector (2,200); // vector with 2 elements
std::stack<int> first; // empty stack
std::stack<int> second (mydeque); // stack initialized to copy of deque
std::stack<int,std::vector<int> > third; // empty stack using vector
std::stack<int,std::vector<int> > fourth (myvector);
std::cout << "size of first: " << first.size() << '\n';
std::cout << "size of second: " << second.size() << '\n';
std::cout << "size of third: " << third.size() << '\n';
std::cout << "size of fourth: " << fourth.size() << '\n';
return 0;
}구현
std::stack을 iterable하게 만들기
MutantStack 클래스
std::stack상속하여 모든 멤버 함수 제공- 추가로 iterator 기능도 제공
👉stack은 기반이 되는 컨테이너를 protected 멤버 변수로 가지기 때문에 이를 통해 구현
테스트 코드
int main(void) {
MutantStack<int> mstack;
mstack.push(5);
mstack.push(17);
std::cout << mstack.top() << std::endl;
mstack.pop();
std::cout << mstack.size() << std::endl;
mstack.push(3);
mstack.push(5);
mstack.push(737);
//[...]
mstack.push(0);
MutantStack<int>::iterator it = mstack.begin();
MutantStack<int>::iterator ite = mstack.end();
++it;
--it;
while (it != ite)
{
std::cout << *it << std::endl;
++it;
}
std::stack<int> s(mstack);
return (0);
}- 테스트는
MutantStack을 사용하든std::list같은 다른 컨테이너를 사용하든 결과가 같아야 함- 물론 다른 컨테이너를 테스트할 때는 적절한 함수 사용 (
push()=>push_back()등)
- 물론 다른 컨테이너를 테스트할 때는 적절한 함수 사용 (
