[C++] 스터디 CPPALOM 8주차: 뇌를 자극하는 C++ STL Chap 5-6
파워 포인트 파일(.pptx)을 Markdown으로 변환하여 업로드하였음)
# <br>CPPALOM
# <br>8주차 – 뇌를 자극하는 C++ STL Chap 5-6
한수빈
# <br>STL이란
* STL은 표준 C++ 라이브러리의 일부분으로 Standard Template Library의 약자이다.
* 다음은 STL의 구성 요소이다:
* 컨테이너(Container): 객체를 저장하는 객체로 컬렉션 혹은 자료구조라고도 한다.
* 반복자(Iterator): 원소를 가리키고, 가리키는 원소에 접근하여 다음 원소를 가리키게 한다.
* 알고리즘(Algorithm): 정렬, 삭제, 검색, 연산 등을 해결하는 일반화된 방법을 제공하는 함수 템플릿이다.
* 함수 객체(Function Object): 함수처럼 동작하는 객체로 operator() 연산자를 오버로딩한 객체이다. 컨테이너와 알고리즘 등에 클라이언트 정책을 반영하도록 한다.
* 어댑터(Adaptor): 구성 요소의 인터페이스를 변경해 새로운 인터페이스를 갖는 구성 요소로 변경한다.
* 할당기(Allocator): 컨테이너의 메모리 할당 정책을 캡슐화한 클래스 객체이다.
# <br>컨테이너
표준 시퀀스 컨테이너: 컨테이너 원소가 자신만의 삽입 위치(순서)를 가지는 컨테이너
표준 연관 컨테이너: 저장 원소가 삽입 순서와 다르게 특정 정렬 기준에 의해 자동 정렬되는 컨테이너
배열 기반 컨테이너: vector, deque
노드 기반 컨테이너: list, set, multiset, map, multimap
# <br>vector 컨테이너
* vecto는 시퀀스 컨테이너이므로 추가한 순서대로 출력된다.
* 또한, 배열 기반 컨테이너이므로 operator[] 연산자로 저장 원소에 접근할 수 있다.
```C++
#include <iostream>
#include <vector>
using namespace std;
void main( )
{
vector<int> v; // 정수를 저장하는 컨테이너 v 생성
v.push_back(10); // v에 정수 추가
v.push_back(20);
v.push_back(30);
v.push_back(40);
v.push_back(50);
for(unsigned int i = 0 ; i < v.size() ; ++i)
cout << v[i] << endl; // v[i]는 i번째 index의 정수 반환
}
```
# <br>반복자
* 반복자는 컨테이너에 저장된 원소를 순회하고 접근하는 일반화된 방법을 제공한다.
* 컨테이너와 알고리즘이 하나로 동작하게 묶어주는 인터페이스 역할을 한다.
* 반복자는 다음과 같은 특징을 지녔다:
* 반복자는 컨테이너 내부의 원소(객체)를 가리키고 접근할 수 있다. (*연산자 제공)
* 반복자는 다음 원소로 이동하고 컨테이너의 모든 원소를 순회할 수 있어야 한다. (증감 연산자 및 비교 연산자 제공)
* 주의할 점은 순차열의 시작과 끝에서 끝은 실제 원소가 아닌 끝을 표시(past-the-end)하는 원소라는 점이다.
```C++
#include <iostream>
#include <vector>
using namespace std;
void main( )
{
vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);
v.push_back(50);
vector<int>::iterator iter; // 반복자 생성(아직 원소를 가리키지 않음)
for(iter = v.begin() ; iter != v.end() ; ++iter)
cout << *iter << endl; // 반복자가 가리키는 원소를 역참조
}
```
* 반복자는 다음과 같이 다섯 범주로 나뉜다:
* 입력 반복자: 현 위치의 원소를 한 번만 읽을 수 있는 반복자
* 출력 반복자: 현 위치의 원소를 한 번만 쓸 수 있는 반복자
* 순방향 반복자: 입력, 출력 반복자 기능에 순방향으로 이동이 가능한 재할당될 수 있는 반복자
* 양방향 반복자: 순방향 반복자 기능에 역방향으로 이동이 가능한 반복자
* 임의 접근 반복자: 양방향 반복자 기능에 +, -, +=, -=, [] 연산이 가능한 반복자
# <br>vector의 임의 접근 반복자
iter[i]: iter+i번째 원소에 접근
iter += n: iter를 n만큼 이동
iter2 = iter – n: iter에서 –n만큼 이동한 반복자를 iter2에 대입
```C++
#include <iostream>
#include <vector>
using namespace std;
void main( )
{
vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);
v.push_back(50);
vector<int>::iterator iter=v.begin(); //시작 원소를 가리키는 반복자
cout << iter[0] << endl; // [] 연산자
cout << iter[1] << endl;
cout << iter[2] << endl;
cout << iter[3] << endl;
cout << iter[4] << endl;
cout << endl;
iter += 2; // += 연산
cout << *iter << endl;
cout << endl;
vector<int>::iterator iter2 = iter+2; // + 연산
cout << *iter2 << endl;
}
```
```C++
10
20
30
40
50
30
50
```
# <br>deque의 임의 접근 반복자
deque 역시 vector와 동일한 결과를 얻을 수 있다.
```C++
#include <iostream>
#include <deque>
using namespace std;
void main( )
{
deque<int> dq;
dq.push_back(10);
dq.push_back(20);
dq.push_back(30);
dq.push_back(40);
dq.push_back(50);
deque<int>::iterator iter=dq.begin(); //시작 원소를 가리키는 반복자
cout << iter[0] << endl; // [] 연산자
cout << iter[1] << endl;
cout << iter[2] << endl;
cout << iter[3] << endl;
cout << iter[4] << endl;
cout << endl;
iter += 2; // += 연산
cout << *iter << endl;
cout << endl;
deque<int>::iterator iter2 = iter+2; // + 연산
cout << *iter2 << endl;
}
```
```C++
10
20
30
40
50
30
50
```
# <br>알고리즘
* STL은 순차열의 원소를 조사, 변경, 관리, 처리할 목적으로 알고리즘이라는 구성 요소를 제공한다.
* STL 알고리즘은 7가지의 범주로 분류한다:
* 원소를 수정하지 않는 알고리즘
* 원소를 수정하는 알고리즘
* 제거 알고리즘
* 변경 알고리즘
* 정렬 알고리즘
* 정렬된 범위 알고리즘
* 수치 알고리즘
# <br>find 알고리즘
* 알고리즘은 아주 일반적이다.
* find 알고리즘은 순방향 반복자를 요구하기 때문에 순방향 반복자만 지원하는 컨테이너(순차열)라면 어떤 컨테이너가 와도 알고리즘을 수행할 수 있다.
* 컨테이너 원소가 정수, 실수, 문자열 혹은 사용자 정의 타입이어도 가능하다.
```C++
#include <iostream>
#include <vector>
#include <algorithm> // find 사용
using namespace std;
void main( )
{
vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);
v.push_back(50);
vector<int>::iterator iter;
iter = find(v.begin(), v.end(), 20); //[begin, end)에서 20 찾기
cout << *iter << endl;
iter = find(v.begin(), v.end(), 100); //[begin, end)에서 100 찾기
if( iter == v.end() ) // 100이 없으면 iter==v.end() 임
cout << "100이 없음!" << endl;
}
```
# <br>sort 알고리즘
다음은 vector와 list 컨테이너의 순차열에 sort 알고리즘을 수행한다.
```C++
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;
void main( )
{
vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);
v.push_back(50);
list<int> lt;
lt.push_back(10);
lt.push_back(20);
lt.push_back(30);
lt.push_back(40);
lt.push_back(50);
sort(v.begin(), v.end()); // 정렬 가능(vector는 임의 접근 반복자)
sort(lt.begin(), lt.end()); // 에러!(list는 양방향 반복자)
}
```
# <br>함수 객체
* 함수 객체는 클라이언트가 정의한 동작을 다른 구성 요소에 반영하려 할 때 사용한다.
* 함수 객체를 사용하면 STL 구성 요소를 더욱 유연하게 사용할 수 있다.
```C++
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;
void main( )
{
vector<int> v;
v.push_back(50);
v.push_back(10);
v.push_back(20);
v.push_back(40);
v.push_back(30);
sort(v.begin(), v.end(), less<int>() ); // 오름차순 정렬
for(vector<int>::iterator iter= v.begin() ; iter != v.end() ; ++iter)
cout << *iter << " ";
cout << endl;
sort(v.begin(), v.end(), greater<int>() ); // 내림차순 정렬
for(vector<int>::iterator iter= v.begin() ; iter != v.end() ; ++iter)
cout << *iter << " ";
cout << endl;
}
```
```C++
10 20 30 40 50
50 40 30 20 10
```
# <br>어댑터
* 어댑터는 구성 요소의 인터페이스를 변경한다.
* 컨테이너 어댑터: stack, queue, priority_queue
* 반복자 어댑터: reverse_iterator, back_insert_iterator, front_insert_iterator, insert_iterator
* 함수 어댑터: 바인더(binder), 부정자(negator), 함수 포인터 어댑터(adaptor for pointers to functions)
* 대표적인 컨테이너 어댑터는 stack이다.
* stack 컨테이너 어댑터는 일반 컨테이너를 LIFO 방식으로 변환한다.
```C++
#include <iostream>
#include <stack>
using namespace std;
void main( )
{
stack<int> st; //stack 컨테이너 생성
st.push( 10 ); // 데이터 추가(입력)
st.push( 20 );
st.push( 30 );
cout << st.top() << endl; // top 데이터 출력
st.pop(); // top 데이터 삭제
cout << st.top() << endl;
st.pop();
cout << st.top() << endl;
st.pop();
if( st.empty() ) // 스택이 비었는지 확인
cout << "stack이 데이터 없음" << endl;
}
```
```C++
30
20
10
stack에 데이터 없음
```
# <br>vector 컨테이너를 적용한 stack
stack<int, vector<int>> st: vector 컨테이너를 적용한 정수를 저장하는 stack 컨테이너를 생성한다.
```C++
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
void main( )
{
stack<int, vector<int> > st; // vector 컨테이너를 이용한 stack 컨테이너 생성
st.push( 10 ); // 데이터 추가(입력)
st.push( 20 );
st.push( 30 );
cout << st.top() << endl; // top 데이터 출력
st.pop(); // top 데이터 삭제
cout << st.top() << endl;
st.pop();
cout << st.top() << endl;
st.pop();
if( st.empty() ) // 스택이 비었는지 확인
cout << "stack이 데이터 없음" << endl;
}
```
```C++
30
20
10
stack에 데이터 없음
```
# <br>reverse_iterator
* riter는 iterator를 생성자로 받아 방향이 반대인 iterator로 Adapt한다.
* 주의할 점:
* v.end()와 riter(v.end())가 가리키는 값은 다르다!
* end_riter가 past-the-end 반복자가 되어야 하므로, 생성자로부터 받은 위치의 다음을 가리키게 되어있다.
```C++
#include <iostream>
#include <vector>
using namespace std;
void main( )
{
vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);
v.push_back(50);
for( vector<int>::iterator iter= v.begin(); iter != v.end(); ++iter)
cout << *iter << " ";
cout << endl;
//일반 반복자 iterator를 역방향 반복자 reverse_iterator로 변환
reverse_iterator< vector<int>::iterator > riter(v.end());
reverse_iterator< vector<int>::iterator > end_riter(v.begin());
for( ; riter != end_riter ; ++riter )
cout << *riter << " ";
cout << endl;
}
```
```C++
10 20 30 40 50
50 40 30 20 10
```
# <br>vector의 reverse_iterator
* STL 컨테이너의 역방향 반복자가 필요한 경우라면 직접 생성하지 않고도 역방향 반복자를 얻을 수 있다.
* 모든 컨테이너는 자신의 역방향 반복자를 정의하며 rbegin(), rend() 멤버 함수로 반복자 쌍을 반환한다.
```C++
#include <iostream>
#include <vector>
using namespace std;
void main( )
{
vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);
v.push_back(50);
for( vector<int>::iterator iter= v.begin(); iter != v.end(); ++iter)
cout << *iter << " ";
cout << endl;
// STL 모든 컨테이너는 반복자 어댑터 reverse_iterator를 typedef 타입으로 정의하며
// rbegin(), rend()로 컨테이너의 역방향 반복자를 반환함.
vector<int>::reverse_iterator riter(v.rbegin());
for( ; riter != v.rend() ; ++riter )
cout << *riter << " ";
cout << endl;
}
```
```C++
10 20 30 40 50
50 40 30 20 10
```
# <br>reverse_iterator
normal_iter와 reverse_iter는 같은 위치를 가리키지만 실제 원소의 출력 값은 다르다.
--연산자를 사용하지 않고 ++연산자만으로 정방향, 역방향의 순회가 모두 가능하다.
```C++
#include <iostream>
#include <vector>
using namespace std;
void main( )
{
vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);
v.push_back(50);
vector<int>::iterator normal_iter= v.begin()+3; //40 원소를 가리키는 정방향 반복자
vector<int>::reverse_iterator reverse_iter(normal_iter);// normal_iter의 역방향 반복자
cout << "정방향 반복자의 값: " << *normal_iter << endl;
cout << "역방향 반복자의 값: " << *reverse_iter << endl;
cout << endl;
for(vector<int>::iterator iter= v.begin(); iter != normal_iter ; ++iter)
cout << *iter << " "; //정방향 출력
cout << endl;
for(vector<int>::reverse_iterator riter= reverse_iter; riter != v.rend() ; ++riter)
cout << *riter << " "; //역방향 출력
cout << endl;
}
```
```C++
정방향 반복자의 값: 40
역방향 반복자의 값: 30
10 20 30
30 20 10
```
* not2는 조건자 함수 객체를 반대 의미의 조건자 함수 객체로 변경하는 어댑터이다.
* not1은 단항 조건자에, not2는 이항 조건자에 사용된다.
```C++
#include <iostream>
#include <functional> //not2 사용
using namespace std;
void main( )
{
cout << less<int>()(10, 20) << endl; //임시 less 객체로 비교
cout << less<int>()(20, 20) << endl;
cout << less<int>()(20, 10) << endl;
cout << "==============" <<endl;
cout << not2( less<int>() )(10, 20) << endl;// 임시 객체 less에 not2 어댑터 적용
cout << not2( less<int>() )(20, 20) << endl;
cout << not2( less<int>() )(20, 10) << endl;
cout << endl;
less<int> l;
cout << l(10, 20) << endl; // less 객체 l로 비교
cout << l(20, 20) << endl;
cout << l(20, 10) << endl;
cout << "==============" <<endl;
cout << not2( l )(10, 20) << endl; // less 객체 l에 not2 어댑터 적용
cout << not2( l )(20, 20) << endl;
cout << not2( l )(20, 10) << endl;
}
```
```C++
1
0
0
===============
0
1
1
1
0
0
===============
0
1
1
```
# <br>할당기
* 할당기는 컨테이너의 메모리 할당 정보와 정책(메모리 할당 모델)을 캡슐화한 STL 구성 요소이다.
* 프로그램 대부분은 STL에서 제공하는 기본 할당기만으로 충분하므로 우리는 할당기를 자세히 다루지 않는다.
* 모든 컨테이너는 템플릿 매개변수에 할당기를 인자로 받는다.
* 기본 할당기는 allocator<T>이다.
* vector<typename T, typename alloc = alloctor<T>>
```C++
#include <iostream>
#include <vector>
#include <set>
#include <map>
using namespace std;
void main( )
{
//vector<typename T, typename Alloc = allocator<T> >
// vector<int> 와 같음
vector< int, allocator<int> > v;
v.push_back( 10 );
cout << *v.begin() << endl;
//set<typename T, typename Pred = less< T >, typename Alloc = allocator<T> >
// set<int> 와 같음
set< int, less<int>, allocator<int> > s;
s.insert( 10 );
cout << *s.begin() << endl;
}
```
# <br>vector 컨테이너
vector 컨테이너는 대표적인 시퀀스 컨테이너로 배열과 비슷하여 사용이 쉬우므로 자주 사용된다.
* vector는 앞쪽이 막혀 있는 형태로 앞쪽에는 원소를 추가/제거할 수 없으며 뒤쪽에만 추가/제거할 수 있다.
* 다른 시퀀스 컨테이너(list, deque)는 앞쪽에 원소를 추가/제거할 수 있는 push_front()와 pop_front()를 가진다.
```C++
#include <iostream>
#include <vector>
using namespace std;
void main( )
{
vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);
v.push_back(50);
for(int i = 0 ; i < v.size() ; ++i)
cout << v[i] << endl;
}
```
```C++
#include <iostream>
#include <vector>
using namespace std;
void main( )
{
vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);
v.push_back(50);
for(vector<int>::size_type i = 0 ; i < v.size() ; ++i)
cout << v[i] << endl;
cout << typeid(vector<int>::size_type).name() << endl;
}
```
```C++
10
20
30
40
50
unsigned int
```
* vector는 크기를 반환하는 세 멤버 함수 size(), capacity(), max_size()를 갖는다.
* size()는 저장 원소의 개수, capacity()는 실제 할당된 메모리 공간의 크기, max_size()는 컨테이너가 담을 수 있는 최대 원소의 개수이다.
* capacity()와 size()가 다른 것은, 가변 길이의 배열을 효율적으로 구현하기 위함이다.
```C++
#include <iostream>
#include <vector>
using namespace std;
void main( )
{
vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);
v.push_back(50);
for(vector<int>::size_type i = 0 ; i < v.size() ; ++i)
cout << v[i] << " ";
cout << endl;
cout << v.size() << endl;
cout << v.capacity() << endl;
cout << v.max_size() << endl;
}
```
```C++
10 20 30 40 50
5
6
1073741823
```
# <br>vector capacity()
```C++
#include <iostream>
#include <vector>
using namespace std;
void main( )
{
vector<int> v;
cout <<"size: "<< v.size() <<" capacity: " << v.capacity() <<endl;
v.push_back(10);
cout <<"size: "<< v.size() <<" capacity: " << v.capacity() <<endl;
v.push_back(20);
cout <<"size: "<< v.size() <<" capacity: " << v.capacity() <<endl;
v.push_back(30);
cout <<"size: "<< v.size() <<" capacity: " << v.capacity() <<endl;
v.push_back(40);
cout <<"size: "<< v.size() <<" capacity: " << v.capacity() <<endl;
v.push_back(50);
cout <<"size: "<< v.size() <<" capacity: " << v.capacity() <<endl;
v.push_back(60);
cout <<"size: "<< v.size() <<" capacity: " << v.capacity() <<endl;
v.push_back(70);
cout <<"size: "<< v.size() <<" capacity: " << v.capacity() <<endl;
v.push_back(80);
cout <<"size: "<< v.size() <<" capacity: " << v.capacity() <<endl;
v.push_back(90);
cout <<"size: "<< v.size() <<" capacity: " << v.capacity() <<endl;
for(vector<int>::size_type i = 0 ; i < v.size() ; ++i)
cout << v[i] << " ";
cout << endl;
}
```
* capacity는 필요에 의해서 확장, 축소된다.
* 이 때, 데이터들은 전부 새로운 메모리에 재할당되므로, 오버헤드가 발생한다.
* 컴파일러마다 서로 다른 정책을 사용할 수 있다.
```C++
size: 0 capacity: 0
size: 1 capacity: 1
size: 2 capacity: 2
size: 3 capacity: 3
size: 4 capacity: 4
size: 5 capacity: 6
size: 6 capacity: 6
size: 7 capacity: 9
size: 8 capacity: 9
size: 9 capacity: 9
10 20 30 40 50 60 70 80 90
```
# <br>vector reserve()
```C++
#include <iostream>
#include <vector>
using namespace std;
void main( )
{
vector<int> v;
v.reserve(8);
cout <<"size: "<< v.size() <<" capacity: " << v.capacity() <<endl;
v.push_back(10);
cout <<"size: "<< v.size() <<" capacity: " << v.capacity() <<endl;
v.push_back(20);
cout <<"size: "<< v.size() <<" capacity: " << v.capacity() <<endl;
v.push_back(30);
cout <<"size: "<< v.size() <<" capacity: " << v.capacity() <<endl;
v.push_back(40);
cout <<"size: "<< v.size() <<" capacity: " << v.capacity() <<endl;
v.push_back(50);
cout <<"size: "<< v.size() <<" capacity: " << v.capacity() <<endl;
v.push_back(60);
cout <<"size: "<< v.size() <<" capacity: " << v.capacity() <<endl;
v.push_back(70);
cout <<"size: "<< v.size() <<" capacity: " << v.capacity() <<endl;
v.push_back(80);
cout <<"size: "<< v.size() <<" capacity: " << v.capacity() <<endl;
v.push_back(90);
cout <<"size: "<< v.size() <<" capacity: " << v.capacity() <<endl;
for(vector<int>::size_type i = 0 ; i < v.size() ; ++i)
cout << v[i] << " ";
cout << endl;
}
```
* reserve()는 클라이언트가 capacit를 결정한다.
* 여전히, 필요에 의해서 capacity가 변할 수 있다.
```C++
size: 0 capacity: 8
size: 1 capacity: 8
size: 2 capacity: 8
size: 3 capacity: 8
size: 4 capacity: 8
size: 5 capacity: 8
size: 6 capacity: 8
size: 7 capacity: 8
size: 8 capacity: 8
size: 9 capacity: 12
10 20 30 40 50 60 70 80 90
```
# <br>vector constructor
```C++
#include <iostream>
#include <vector>
using namespace std;
void main( )
{
vector<int> v1(5); //0으로 초기화된 size가 5인 컨테이너
v1.push_back(10); //10 추가
v1.push_back(20); //20 추가
v1.push_back(30); //30 추가
v1.push_back(40); //40 추가
v1.push_back(50); //50 추가
for(vector<int>::size_type i = 0 ; i < v1.size() ; ++i)
cout << v1[i] << " ";
cout << endl;
vector<int> v2(5); //0으로 초기화된 size가 5인 컨테이너
v2[0] = 10; // 0에서 10로 수정
v2[1] = 20; // 0에서 20로 수정
v2[2] = 30; // 0에서 30로 수정
v2[3] = 40; // 0에서 40로 수정
v2[4] = 50; // 0에서 50로 수정
for(vector<int>::size_type i = 0 ; i < v2.size() ; ++i)
cout << v2[i] << " ";
cout << endl;
}
```
* 생성자를 사용해서 size를 미리 확보할 수 있다.
* vector<int> v(n): v는 n개의 size를 갖고 기본값(int())으로 초기화된다.
```C++
0 0 0 0 0 10 20 30 40 50
10 20 30 40 50
```
```C++
#include <iostream>
#include <vector>
using namespace std;
void main( )
{
vector<int> v1(5); //기본값 0으로 초기화된 size가 5인 컨테이너
for(vector<int>::size_type i = 0 ; i < v1.size() ; ++i)
cout << v1[i] << " ";
cout << endl;
vector<int> v2(5,0); //지정값 0으로 초기화된 size가 5인 컨테이너
for(vector<int>::size_type i = 0 ; i < v2.size() ; ++i)
cout << v2[i] << " ";
cout << endl;
vector<int> v3(5,10); //지정값 10으로 초기화된 size가 5인 컨테이너
for(vector<int>::size_type i = 0 ; i < v3.size() ; ++i)
cout << v3[i] << " ";
cout << endl;
}
```
* 두 번째 인자를 이용하여 원소의 초기값을 정할 수도 있다.
* vector<int> v2(5, 0): v2는 0으로 초기화된 size가 5인 컨테이너를 생성한다.
* vector<int> v3(5, 10: v3는 10으로 초기화된 size가 5인 컨테이너를 생성한다.
```C++
0 0 0 0 0
0 0 0 0 0
10 10 10 10 10
```
# <br>vector resize()
```C++
#include <iostream>
#include <vector>
using namespace std;
void main( )
{
vector<int> v(5); //기본값 0으로 초기화된 size가 5인 컨테이너
v[0] = 10;
v[1] = 20;
v[2] = 30;
v[3] = 40;
v[4] = 50;
for(vector<int>::size_type i = 0 ; i < v.size() ; ++i)
cout << v[i] << " ";
cout << endl;
cout <<"size: "<< v.size() <<" capacity: " << v.capacity() <<endl;
v.resize(10); //기본값 0으로 초기화된 size가 10인 컨테이너로 확장
for(vector<int>::size_type i = 0 ; i < v.size() ; ++i)
cout << v[i] << " ";
cout << endl;
cout <<"size: "<< v.size() <<" capacity: " << v.capacity() <<endl;
v.resize(5); //size가 5인 컨테이너로 축소 capacity는 변화 없음.
for(vector<int>::size_type i = 0 ; i < v.size() ; ++i)
cout << v[i] << " ";
cout << endl;
cout <<"size: "<< v.size() <<" capacity: " << v.capacity() <<endl;
}
```
* resize()를 이용해 컨테이너의 크기를 변경할 수 있다.
* size를 키울 때는 capacity도 늘어나지만, size를 줄일 때는 capacity가 줄지 않는다.
```C++
10 20 30 40 50
size: 5 capacity: 5
10 20 30 40 50 0 0 0 0 0
size: 10 capacity: 10
10 20 30 40 50
size: 5 capacity: 10
```
# <br>vector clear(), empty()
```C++
#include <iostream>
#include <vector>
using namespace std;
void main( )
{
vector<int> v(5);
v[0] = 10;
v[1] = 20;
v[2] = 30;
v[3] = 40;
v[4] = 50;
for(vector<int>::size_type i = 0 ; i < v.size() ; ++i)
cout << v[i] << " ";
cout << endl;
cout <<"size: "<< v.size() <<" capacity: " << v.capacity() <<endl;
v.clear(); // v를 비운다.
cout <<"size: "<< v.size() <<" capacity: " << v.capacity() <<endl;
if( v.empty() ) // v가 비었는가?
{
cout << "v에 원소가 없습니다." << endl;
}
}
```
clear()는 컨테이너의 모든 원소를 제거한다.
empty()는 컨테이너가 비었는지 여부를 반환한다.
size는 0이 되지만, capacity는 변하지 않는다!
```C++
10 20 30 40 50
size: 5 capacity: 5
size: 0 capacity: 5
```
# <br>vector swap()을 이용한 할당 메모리 제거
* capacity를 0으로 만드는 함수는 존재하지 않지만 C++에서 권장하는 swap 방법이 있다.
* 모든 컨테이너는 컨테이너 객체끼리 교환할 수 있는 swap() 멤버 함수를 제공한다.
* swap() 함수를 이용해 임시로 생성한(기본 생성자에 의해 size, capacit가 0인) 컨테이너 객체와 swap할 수 있다.
```C++
#include <iostream>
#include <vector>
using namespace std;
void main( )
{
vector<int> v(5);
cout <<"size: "<< v.size() <<" capacity: " << v.capacity() <<endl;
vector<int>().swap(v);// 기본 생성자로 만든 vector컨테이너와 v 컨테어너를 swap한다.
cout <<"size: "<< v.size() <<" capacity: " << v.capacity() <<endl;
}
```
```C++
size: 5 capacity: 5
size: 0 capacity: 0
```
# <br>vector swap()
```C++
#include <iostream>
#include <vector>
using namespace std;
void main( )
{
vector<int> v1;
v1.push_back(10);
v1.push_back(20);
v1.push_back(30);
vector<int> v2;
v2.push_back(100);
v2.push_back(200);
v2.push_back(300);
for(vector<int>::size_type i = 0 ; i < v1.size() ; ++i)
cout << v1[i] << ", " << v2[i] << endl;
cout << endl;
v1.swap(v2); // v1과 v2를 swap합니다.
for(vector<int>::size_type i = 0 ; i < v1.size() ; ++i)
cout << v1[i] << ", " << v2[i] << endl;
cout << endl;
}
```
v1.swap(v2): v1의 멤버 함수 swap()을 호출해 두 컨테이너의 원소 v1과 v2를 교환한다.
```C++
10, 100
20, 200
30, 300
100, 10
200, 20
300, 30
```
# <br>vector front(), back()
시퀀스 컨테이너는 순서 개념이 있으므로 모든 시퀀스 컨테이너 vector, list, deque는 첫 번째 원소의 참조와 마지막 원소의 참조인 front(), back() 멤버 함수를 제공한다.
```C++
#include <iostream>
#include <vector>
using namespace std;
void main( )
{
vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);
v.push_back(50);
for(vector<int>::size_type i = 0 ; i < v.size() ; ++i)
cout << v[i] << " ";
cout << endl;
cout << v[0] <<", " << v.front() << endl; // 첫 번째 원소
cout << v[4] <<", " << v.back() << endl; // 마지막 원소
}
```
```C++
#include <iostream>
#include <vector>
using namespace std;
void main( )
{
vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);
v.push_back(50);
for(vector<int>::size_type i = 0 ; i < v.size() ; ++i)
cout << v[i] << " ";
cout << endl;
v.front() = 100; // 첫 번째 원소를 100으로
v.back() = 500; // 마지막 원소를 500으로
for(vector<int>::size_type i = 0 ; i < v.size() ; ++i)
cout << v[i] << " ";
cout << endl;
}
```
```C++
10 20 30 40 50
10, 10
50, 50
```
```C++
10 20 30 40 50
100 20 30 40 500
```
# <br>vector [], at()
* 시퀀스 컨테이너 중 배열 기반 컨테이너인 vector와 deque는 일반 배열처럼 임의 위치의 원소를 참조하는 두 인터페이스를 제공한다.
* [] 연산자와 at() 멤버 함수이다.
* [] 연산자의 경우 범위 점검을 하지 않아 속도가 빠르다.
* at() 멤버 함수의 경우 범위 점검을 하며 범위를 벗어날 시 out_of_range 예외를 던진다.
```C++
void main( )
{
vector<int> v;
v.push_back(10);
…
v.push_back(50);
for(vector<int>::size_type i = 0 ; i < v.size() ; ++i)
cout << v[i] << " ";
cout << endl;
v[0] = 100; //범위 점검 없는 0 index 원소의 참조
v[4] = 500; //범위 점검 없는 4 index 원소의 참조
for(vector<int>::size_type i = 0 ; i < v.size() ; ++i)
cout << v[i] << " ";
cout << endl;
v.at(0) = 1000; //범위 점검 있는 0 index 원소의 참조
v.at(4) = 5000; //범위 점검 있는 4 index 원소의 참조
for(vector<int>::size_type i = 0 ; i < v.size() ; ++i)
cout << v.at(i) << " ";
cout << endl;
}
```
```C++
10 20 30 40 50
100 20 30 40 500
1000 20 30 40 5000
```
# <br>vector out_of_range
at() 멤버 함수를 [] 연산자로 바꾼다면 범위 점검을 하지 않고 메모리 접근 오류가 발생한다.
```C++
#include <iostream>
#include <vector>
using namespace std;
void main( )
{
vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);
v.push_back(50);
try
{
cout << v.at(0) << endl;
cout << v.at(3) << endl;
cout << v.at(6) << endl; //throw out_of_range 예외
}
catch(out_of_range &e)
{
cout << e.what() << endl;
}
}
```
```C++
10
40
invalid vector<T> subscript
```
# <br>vector assign()
* 생성자를 이용하지 않고 컨테이너 생성 이후에도 assign() 멤버 함수를 사용해 일괄적으로 값을 할당할 수 있다.
* 모든 시퀀스 컨테이너는 assign() 멤버 함수를 제공하여 일관적으로 값을 할당할 수 있다.
```C++
#include <iostream>
#include <vector>
using namespace std;
void main( )
{
vector<int> v(5, 1); // 초기값 1의 5개의 원소를 갖는 컨테이너 생성
for(vector<int>::size_type i = 0 ; i < v.size() ; ++i)
cout << v[i] << " ";
cout << endl;
v.assign(5, 2); // 5개의 원소값을 2로 할당
cout << v.size() <<',' << v.capacity() << endl;
for(vector<int>::size_type i = 0 ; i < v.size() ; ++i)
cout << v[i] << " ";
cout << endl;
}
```
```C++
1 1 1 1 1
2 2 2 2 2
```
# <br>vector begin(), end()
STL의 모든 컨테이너는 양방향 반복자 이상의 기능을 제공한다.
컨테이너는 모든 원소의 시작과 끝을 가리키는 반복자 쌍(구간)을 begin()과 end() 멤버 함수로 제공하며 컨테이너의 모든 원소는 구간[begin(), end())로 표현할 수 있다.
```C++
#include <iostream>
#include <vector>
using namespace std;
void main( )
{
vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);
v.push_back(50);
for(vector<int>::size_type i = 0 ; i < v.size() ; ++i)
cout << v[i] << " ";
cout << endl;
for(vector<int>::iterator iter = v.begin(); iter != v.end() ; ++iter)
cout << *iter << " ";
cout << endl;
}
```
```C++
10 20 30 40 50
10 20 30 40 50
```
* 배열 기반 컨테이너인 vector와 deque는 임의 접근 반복자를 제공한다.
* 임의 접근 반복자는 +, -, +=, -=, [] 연산이 가능하다.
```C++
#include <iostream>
#include <vector>
using namespace std;
void main( )
{
vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);
v.push_back(50);
vector<int>::iterator iter=v.begin(); // 시작 원소(10)를 가리킨다.
cout << *iter << endl;
iter += 2; // +2한 위치의 원소(30)를 가리킨다.
cout << *iter << endl;
iter -= 1; // -1한 위치의 원소(20)를 가리킨다.
cout << *iter << endl;
}
```
만약 반복자가 가리키는 원소의 값을 변경하지 않는다면 상수 반복자를 사용하는 것이 좋다.
```C++
#include <iostream>
#include <vector>
using namespace std;
void main( )
{
vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);
v.push_back(50);
vector<int>::iterator iter = v.begin();
vector<int>::const_iterator citer = v.begin();
cout << *iter << endl; //가리키는 원소의 참조
cout << *citer << endl; //가리키는 원소의 상수 참조
cout << *++iter << endl; //다음 원소로 이동한 원소의 참조
cout << *++citer << endl; //다음 원소로 이동한 원소의 상수 참조
*iter = 100; // 일반 반복자는 가리키는 원소를 변경할 수 있음.
//*citer = 100; // 상수 반복자는 가리키는 원소를 변경할 수 없음.
}
```
reverse_iterator는 vector에 반복자 어댑터로 정의되어 있다.
rbegin()과 rend()는 컨테이너 모든 원소의 역순차열이다.
```C++
#include <iostream>
#include <vector>
using namespace std;
void main( )
{
vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);
v.push_back(50);
vector<int>::iterator iter; //정방향 반복자
vector<int>::reverse_iterator riter; //역방향 반복자
for( iter = v.begin(); iter != v.end() ; ++iter)
cout << *iter << " ";
cout << endl;
for( riter = v.rbegin(); riter != v.rend() ; ++riter)
cout << *riter << " ";
cout << endl;
}
```
```C++
10 20 30 40 50
50 40 30 20 10
```
# <br>vector insert()
insert()는 반복자가 가리키는 위치에 원소를 추가할 수 있다.
erase()는 반복자가 가리키는 위치의 원소를 제거할 수 있다.
삽입 시, 반복자가 가리키는 위치의 원소 자리에 삽입되며, 이후 원소들은 뒤로 밀려난다.
```C++
#include <iostream>
#include <vector>
using namespace std;
void main( )
{
vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);
v.push_back(50);
vector<int>::iterator iter = v.begin()+2;
vector<int>::iterator iter2;
// iter가 가리키는 위치에 정수 100을 삽입.
// iter2는 삽입한 정수를 가리키는 반복자.
iter2 = v.insert(iter, 100);
for( iter = v.begin(); iter != v.end() ; ++iter)
cout << *iter << " ";
cout << endl;
cout << "iter2: " << *iter2 << endl;
}
```
```C++
10 20 100 30 40 50
iter2: 100
```
```C++
#include <iostream>
#include <vector>
using namespace std;
void main( )
{
vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);
v.push_back(50);
vector<int>::iterator iter = v.begin()+2;
// iter가 가리키는 위치에 정수 100을 3개 삽입.
v.insert(iter, 3, 100);
for( iter = v.begin(); iter != v.end() ; ++iter)
cout << *iter << " ";
cout << endl;
/////////////////////////////////////////////////////
vector<int> v2;
v2.push_back(100);
v2.push_back(200);
v2.push_back(300);
iter = v2.begin()+1;
// iter가 가리키는 위치에 [v.begin(), v.end()) 구간의 원소를 삽입.
v2.insert(iter, v.begin(), v.end());
for( iter = v2.begin(); iter != v2.end() ; ++iter)
cout << *iter << " ";
cout << endl;
}
```
여러 개의 원소를 한 번에 삽입하는 버전의 insert()와 반복자 구간을 이용하여 원소를 삽입할 수 있는 버전의 insert()를 제공한다.
```C++
10 20 100 100 100 30 40 50
100 10 20 100 100 100 30 40 50 200 300
```
# <br>vector erase()
```C++
#include <iostream>
#include <vector>
using namespace std;
void main( )
{
vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);
v.push_back(50);
vector<int>::iterator iter;
vector<int>::iterator iter2;
for( iter = v.begin(); iter != v.end() ; ++iter)
cout << *iter << " ";
cout << endl;
iter = v.begin()+2;
// iter가 가리키는 위치의 원소를 제거합니다. iter2는 다음 원소 40
iter2 = v.erase(iter);
for( iter = v.begin(); iter != v.end() ; ++iter)
cout << *iter << " ";
cout << endl;
// [v.begin()+1, v.end()) 구간의 원소를 제거합니다.
iter2 = v.erase(v.begin()+1, v.end()); // iter2는 다음 원소 v.end()
for( iter = v.begin(); iter != v.end() ; ++iter)
cout << *iter << " ";
cout << endl;
}
```
erase()를 이용해 원소를 제거할 수 있으며, 이 역시 반복자를 이용해 제거할 수 있다.
```C++
10 20 30 40 50
10 20 40 50
10
```
# <br>반복자로 동작하는 assign(), constructor
vector의 생성자는 반복자를 통해서 초기화될 수 있으며 assign() 역시 반복자를 통해 할당될 수 있다.
```C++
#include <iostream>
#include <vector>
using namespace std;
void main( )
{
vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);
v.push_back(50);
vector<int> v2( v.begin(), v.end() ); // 순차열 [v.begin(), v.end())로 v2를 초기화.
vector<int>::iterator iter;
for( iter = v2.begin(); iter != v2.end() ; ++iter)
cout << *iter << " "; // v2 출력
cout << endl;
vector<int> v3;
v3.assign( v.begin(), v.end() ); // v3에 순차열 [v.begin(), v.end())을 할당.
for( iter = v3.begin(); iter != v3.end() ; ++iter)
cout << *iter << " "; // v3 출력
cout << endl;
}
```
```C++
10 20 30 40 50
10 20 30 40 50
```
# <br>vector 비교
* vector에는 ==, !=, <, <=, >, >= 연산자를 사용할 수 있다.
* v1 == v2: v1과 v2의 모든 원소가 같다면 참 아니면 거짓이다.
* v1 != v2: v1과 v2의 모든 원소가 같다면 거짓 아니면 참이다.
* v1 < v2: v1과 v2의 순차열의 원소를 하나씩 순서대로 비교하여 v2의 원소가 크다면 참 아니면 거짓이다.
```C++
#include <iostream>
#include <vector>
using namespace std;
void main( )
{
vector<int> v1;
v1.push_back(10);
v1.push_back(20);
v1.push_back(30);
v1.push_back(40);
v1.push_back(50);
vector<int> v2;
v2.push_back(10);
v2.push_back(20);
v2.push_back(50);
if( v1 == v2 )
cout << "v1 == v2" << endl;
if( v1 != v2 )
cout << "v1 != v2" << endl;
if( v1 < v2 )
cout << "v1 < v2" << endl;
}
```
```C++
v1 != v2
v1 < v2
```
# <br>vector 주요 특징
* vector는 임의 접근 반복자를 지원하는 배열 기반 컨테이너이다.
* 원소가 하나의 메모리 블록에 연속하게 저장된다.
* 원소가 연속하게 저장되므로 원소에 접근하는 at()이나 v[i] 등의 연산은 속도가 빠르지만 insert(), erase(), push_back() 등이 빈번하게 호출되어야 하는 프로그램이라면 다른 컨테이너의 선택을 고려해야 한다.
# <br>deque 컨테이너
* deque 컨테이너는 vector 컨테이너와 기능과 동작이 가장 비슷한 컨테이너로 vector 단점을 보완하는 몇 가지 특징을 지닌다.
* deque도 배열 기반 컨테이너이다.
# <br>deque push_back()
deque 역시 push_back() 멤버 함수를 이용해 원소를 추가할 수 있다.
deque는 vector의 단점을 해결하기 위해 여러 개의 메모리 블록을 할당하고 사용자에게는 하나의 블록처럼 보이게 하는 정책을 사용한다.
```C++
#include <iostream>
#include <deque>
using namespace std;
void main( )
{
deque<int> dq;
for(deque<int>::size_type i = 0 ; i < 10 ; ++i)
dq.push_back( (i+1)*10 );
for( deque<int>::size_type i = 0 ; i < dq.size() ; ++i)
cout << dq[i] << ' ';
cout << endl;
}
```
```C++
10 20 30 40 50 60 70 80 90 100
```
# <br>deque push_front()
push_front()는 컨테이너 앞쪽에 원소를 추가할 수 있다.
```C++
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
void main()
{
vector<int> v(4, 100); //100으로 초기화한 4개의 원소를 갖는 컨테이너 v
deque<int> dq(4, 100); //100으로 초기화한 4개의 원소를 갖는 컨테이너 dq
v.push_back( 200 ); // v에 200 추가
dq.push_back( 200 ); // dq에 200 추가
for(vector<int>::size_type i = 0 ; i < v.size() ; ++i)
cout << v[i] << " ";
cout << endl;
for(deque<int>::size_type i = 0 ; i < dq.size() ; ++i)
cout << dq[i] << " ";
cout << endl;
}
```
```C++
10 20 30 40 50
200 100 10 20 30 40 50
```
# <br>deque 반복자
```C++
void main()
{
deque<int> dq;
dq.push_back( 10 );
dq.push_back( 20 );
dq.push_back( 30 );
dq.push_back( 40 );
dq.push_back( 50 );
deque<int>::iterator iter;
for(iter = dq.begin(); iter != dq.end() ; ++iter)
cout << *iter << " ";
cout << endl;
iter = dq.begin()+2; //반복자에 +2합니다.
cout << *iter << endl;
iter += 2; //반복자에 +2합니다.
cout << *iter << endl;
iter -= 3; //반복자에 -3합니다.
cout << *iter << endl;
}
```
* deque는 임의 접근 반복자를 지원한다.
* 마찬가지로 +, -, +=, -=, [] 연산을 모두 수행할 수 있다.
```C++
10 20 30 40 50
30
50
20
```
# <br>deque insert()
* deque는 여러 개의 조각으로 메모리를 관리하므로, insert()를 좀 더 효율적으로 구현할 수 있다.
* 여전히 비효율적이다!
```C++
#include <iostream>
#include <deque>
using namespace std;
void main( )
{
deque<int> dq;
for(int i = 0 ; i < 10 ; i++)
dq.push_back( (i+1)*10 );
deque<int>::iterator iter;
deque<int>::iterator iter2;
for(iter = dq.begin(); iter != dq.end(); ++iter)
cout << *iter << ' ';
cout << endl;
iter = dq.begin()+2;
iter2 = dq.insert( iter , 500);
cout << *iter2 << endl;
for(iter = dq.begin(); iter != dq.end(); ++iter)
cout << *iter << ' ';
cout << endl;
}
```
```C++
10 20 30 40 50 60 70 80 90 100
500
10 20 500 30 40 50 60 70 80 90 100
```
# <br>deque 주요 특징
* deque는 시퀀스 컨테이너이며 배열 기반 컨테이너이다.
* vector와 유사한 특징을 가지며 임의 접근 반복자를 지원한다.
* 차이점은 원소가 여러 개의 메모리 블록에 나뉘어 저장된다는 것이다.
* deque는 원소를 앞쪽과 뒤쪽에 모두 추가할 수 있으며 배열 기반 컨테이너의 특징을 가지면서도 vector보다 조금 더 효율적으로 동작한다.
# <br>list 컨테이너
* list 컨테이너는 vector와 deque처럼 시퀀스 컨테이너로 원소가 상대적인 순서를 유지한다.
* 그러나 list는 노드 기반 컨테이너로 원소가 노드 단위로 저장되며 list는 이중 연결 리스트로 구현된다.
# <br>list 원소 추가와 반복자
list는 원소를 앞쪽, 뒤쪽에 모두 추가할 수 있다.
양방향 반복자를 제공하므로 ++ 연산과 * 연산 != 연산으로 list의 모든 원소를 출력할 수 있다.
list의 가장 큰 특징 중 하나는 순차열 중간에 원소를 삽입 및 제거하더라도 상수 시간 복잡도의 수행 성능을 보인다는 점이다.
```C++
#include <iostream>
#include <list>
using namespace std;
void main( )
{
list<int> lt;
lt.push_back(10);
lt.push_back(20);
lt.push_back(30);
lt.push_back(40);
lt.push_back(50);
list<int>::iterator iter;
for(iter = lt.begin(); iter != lt.end(); ++iter)
cout << *iter << ' ';
cout << endl;
lt.push_front(100);
lt.push_front(200);
for(iter = lt.begin(); iter != lt.end(); ++iter)
cout << *iter << ' ';
cout << endl;
}
```
```C++
10 20 30 40 50
200 100 10 20 30 40 50
```
```C++
#include <iostream>
#include <list>
using namespace std;
void main( )
{
list<int> lt;
lt.push_back(10);
lt.push_back(20);
lt.push_back(30);
lt.push_back(40);
lt.push_back(50);
list<int>::iterator iter = lt.begin();
list<int>::iterator iter2;
++iter;
++iter;
iter2 = lt.erase(iter); //iter(30)의 원소를 제거합니다.
for(iter = lt.begin(); iter != lt.end(); ++iter)
cout << *iter << ' ';
cout << endl;
cout << "iter2 : " << *iter2 << endl;
iter = iter2;
iter2 = lt.insert(iter, 300); //iter2(40)이 가리키는 위치에 300을 삽입합니다.
for(iter = lt.begin(); iter != lt.end(); ++iter)
cout << *iter << ' ';
cout << endl;
cout << "iter2 : " << *iter2 << endl;
}
```
* 노드 기반 컨테이너의 삽입과 제거 동작은 반복자를 무효화 시키지 않는다.
* 반복자가 가리키는 원소 자체가 제거되지 않는 한 반복자가 가리키는 원소는 그대로 존재한다.
* 배열 기반 컨테이너의 반복자는 원소의 삽입과 제거 동작이 발생하면 메모리가 재할당되거나 원소가 이동할 수 있으므로 반복자가 무효화된다.
```C++
10 20 40 50
iter : 40
10 20 300 40 50
iter2 : 300
```
# <br>list remove()
```C++
#include <iostream>
#include <list>
using namespace std;
void main( )
{
list<int> lt;
lt.push_back(10);
lt.push_back(20);
lt.push_back(30);
lt.push_back(10);
lt.push_back(40);
lt.push_back(50);
lt.push_back(10);
lt.push_back(10);
list<int>::iterator iter;
for(iter = lt.begin(); iter != lt.end(); ++iter)
cout << *iter << ' ';
cout << endl;
lt.remove(10); // 10 원소의 노드를 모두 제거
for(iter = lt.begin(); iter != lt.end(); ++iter)
cout << *iter << ' ';
cout << endl;
}
```
* list의 remove()는 컨테이너의 모든 원소를 순차적으로 검색하며 해당하는 원소들을 삭제한다.
* remove()는 erase()처럼 해당 값의 노드만을 제거하므로 속도가 빠르며 유일하게 list만이 remove() 멤버 함수를 갖는다.
* 조건자를 이용해 원소를 제거해야 한다면 remove_if()를 사용할 수 있다.
```C++
10 20 30 10 40 50 10 10
20 30 40 50
```
# <br>list remove_if()
```C++
#include <iostream>
#include <list>
using namespace std;
bool Predicate(int n) // 단항 조건자
{
return 10 <= n && n <= 30;
}
void main( )
{
list<int> lt;
lt.push_back(10);
lt.push_back(20);
lt.push_back(30);
lt.push_back(40);
lt.push_back(50);
lt.push_back(10);
list<int>::iterator iter;
for(iter = lt.begin(); iter != lt.end(); ++iter)
cout << *iter << ' ';
cout << endl;
lt.remove_if(Predicate); // 조건자가 참인 모든 원소를 제거합니다.
for(iter = lt.begin(); iter != lt.end(); ++iter)
cout << *iter << ' ';
cout << endl;
}
```
* remove_if() 멤버 함수는 단항 조건자가 참인 모든 원소를 제거한다.
* 조건자는 bool 형식을 반환하는 함수류이다.
```C++
10 20 30 40 50 10
40 50
```
# <br>list splice()
```C++
void main( )
{
list<int> lt1;
list<int> lt2;
lt1.push_back(10);
lt1.push_back(20);
lt1.push_back(30);
lt1.push_back(40);
lt1.push_back(50);
lt2.push_back(100);
lt2.push_back(200);
lt2.push_back(300);
lt2.push_back(400);
lt2.push_back(500);
iter = lt1.begin();
++iter;
++iter; // 30 원소의 위치를 가리킴
lt1.splice(iter, lt2); //iter가 가리키는 위치에 lt2의 모든 원소를 잘라 붙임
cout << "lt1: ";
for(iter = lt1.begin(); iter != lt1.end(); ++iter)
cout << *iter << ' ';
cout << endl;
cout << "lt2: ";
for(iter = lt2.begin(); iter != lt2.end(); ++iter)
cout << *iter << ' ';
cout << endl;
}
```
* 순서가 있는 노드 기반 컨테이너 list는 splice()를 제공한다.
* splice()는 다른 list 컨테이너의 순차열을 잘라붙일 수 있다.
* splice() 동작은 상수 시간의 실행 동작을 보인다.
```C++
lt1: 10 20 100 200 300 400 500 30 40 50
lt2:
```
```C++
…
list<int>::iterator iter1;
list<int>::iterator iter2;
iter1 = lt1.begin();
++iter1;
++iter1; // 30 원소의 위치를 가리킴
iter2 = lt2.begin();
++iter2; // 200 원소의 위치를 가리킴
//iter1이 가리키는 위치에 iter2가 가리키는 위치의 lt2의 원소를 잘라 붙임
lt1.splice(iter1, lt2, iter2);
cout << "lt1: ";
for(iter1 = lt1.begin(); iter1 != lt1.end(); ++iter1)
cout << *iter1 << ' ';
cout << endl;
cout << "lt2: ";
for(iter2 = lt2.begin(); iter2 != lt2.end(); ++iter2)
cout << *iter2 << ' ';
cout <<endl << "=============" << endl;
//lt1.end()가 가리키는 위치에 순차열 [lt2.begin(), lt2.end())를 잘라 붙임
lt1.splice(lt1.end(), lt2, lt2.begin(), lt2.end());
cout << "lt1: ";
for(iter1 = lt1.begin(); iter1 != lt1.end(); ++iter1)
cout << *iter1 << ' ';
cout << endl;
cout << "lt2: ";
for(iter2 = lt2.begin(); iter2 != lt2.end(); ++iter2)
cout << *iter2 << ' ';
cout <<endl;
}
```
splice(iter1, lt2, iter2): iter1(30)이 가리키는 위치에 iter2가 가리키는 원소(200)를 잘라 붙인다.
splice(lt1.end(), lt2, lt2.begin(), lt2.end()): lt1.end()가 가리키는 위치에 구간 [lt2.begin(), lt2.end())의 순차열을 잘라붙인다.
```C++
lt1: 10 20 200 30 40 50
lt2: 100 300 400 500
==================
lt1: 10 20 200 30 40 50 100 300 400 500
lt2:
```
# <br>list reverse()
reverse()는 이중 연결 리스트의 탐색 경로를 서로 바꿈으로써 순차열을 리버스시킨다.
```C++
#include <iostream>
#include <list>
using namespace std;
void main( )
{
list<int> lt;
lt.push_back(10);
lt.push_back(20);
lt.push_back(30);
lt.push_back(40);
lt.push_back(50);
list<int>::iterator iter;
for(iter = lt.begin(); iter != lt.end(); ++iter)
cout << *iter << ' ';
cout << endl;
lt.reverse();
for(iter = lt.begin(); iter != lt.end(); ++iter)
cout << *iter << ' ';
cout << endl;
}
```
```C++
10 20 30 40 50
50 40 30 20 10
```
# <br>list unique()
unique()는 인접한 원소를 중복되지 않게 하나씩만 남긴다.
```C++
#include <iostream>
#include <list>
using namespace std;
void main( )
{
list<int> lt;
lt.push_back(10);
lt.push_back(10);
lt.push_back(20);
lt.push_back(30);
lt.push_back(30);
lt.push_back(30);
lt.push_back(40);
lt.push_back(50);
lt.push_back(10);
list<int>::iterator iter;
for(iter = lt.begin(); iter != lt.end(); ++iter)
cout << *iter << ' ';
cout << endl;
lt.unique();
for(iter = lt.begin(); iter != lt.end(); ++iter)
cout << *iter << ' ';
cout << endl;
}
```
```C++
10 10 20 30 30 30 40 50 10
10 20 30 40 50 10
```
```C++
#include <iostream>
#include <list>
using namespace std;
bool Predicate(int first, int second)
{
return second-first <= 0 ;
}
void main( )
{
list<int> lt;
lt.push_back(10);
lt.push_back(10);
lt.push_back(20);
lt.push_back(30);
lt.push_back(30);
lt.push_back(30);
lt.push_back(40);
lt.push_back(50);
lt.push_back(10);
list<int>::iterator iter;
for(iter = lt.begin(); iter != lt.end(); ++iter)
cout << *iter << ' ';
cout << endl;
lt.unique(Predicate);
for(iter = lt.begin(); iter != lt.end(); ++iter)
cout << *iter << ' ';
cout << endl;
}
```
* unique(Predicate): 이항 조건자가 참이면 원소를 제거한다.
* second: 다음 원소
* first: 현재 원소
```C++
10 10 20 30 30 30 40 50 10
10 20 30 40 50 10
```
# <br>list sort()
```C++
#include <iostream>
#include <list>
using namespace std;
void main( )
{
list<int> lt;
lt.push_back(20);
lt.push_back(10);
lt.push_back(50);
lt.push_back(30);
lt.push_back(40);
list<int>::iterator iter;
for(iter = lt.begin(); iter != lt.end(); ++iter)
cout << *iter << ' ';
cout << endl;
lt.sort( ); // 오름차순( less, < 연산) 정렬
for(iter = lt.begin(); iter != lt.end(); ++iter)
cout << *iter << ' ';
cout << endl;
}
```
* list는 정렬을 위한 멤버 함수 sort(()를 제공한다.
* vector와 deque는 sort() 알고리즘을 사용하여 빠르게 정렬할 수 있지만, list는 sort() 알고리즘을 수행할 수 없다.
* sort() 알고리즘은 임의 접근 반복자를 지원하는 컨테이너만 사용할 수 있기 때문이다.
* 따라서 list는 자체 정렬 멤버 함수 sort()를 제공한다.
```C++
20 10 50 30 40
10 20 30 40 50
```
# <br>list merge()
```C++
void main( )
{
list<int> lt1;
list<int> lt2;
lt1.push_back(10);
lt1.push_back(20);
lt1.push_back(30);
lt1.push_back(40);
lt1.push_back(50);
lt2.push_back(25);
lt2.push_back(35);
lt2.push_back(60);
list<int>::iterator iter;
cout << "lt1: ";
for(iter = lt1.begin(); iter != lt1.end(); ++iter)
cout << *iter << ' ';
cout << endl; cout << "lt2: ";
for(iter = lt2.begin(); iter != lt2.end(); ++iter)
cout << *iter << ' ';
cout << endl << "===============" << endl;
lt1.merge(lt2); // lt2를 lt1으로 합병 정렬합니다. 정렬 기준은 less
cout << "lt1: ";
for(iter = lt1.begin(); iter != lt1.end(); ++iter)
cout << *iter << ' ';
cout << endl; cout << "lt2: ";
for(iter = lt2.begin(); iter != lt2.end(); ++iter)
cout << *iter << ' ';
cout << endl;
}
```
* merge()를 이용해 두 list를 합병할 수 있다.
* 합병은 정렬된 두 list를 하나의 정렬된 list로 합병한다.
* 따라서 두 list는 정렬되어 있어야 한다!
```C++
lt1: 10 20 30 40 50
lt2: 25 35 60
==============
lt1: 10 20 25 30 35 40 50 60
lt2:
```
```C++
#include <iostream>
#include <list>
using namespace std;
void main( )
{
list<int> lt1;
list<int> lt2;
lt1.push_back(50);
lt1.push_back(40);
lt1.push_back(30);
lt1.push_back(20);
lt1.push_back(10);
// lt1과 lt2는 정렬 방식이 같다.
// greater 조건자( > 연산 ) 정렬 기준을 사용함
lt2.push_back(60);
lt2.push_back(35);
lt2.push_back(25);
// lt2를 lt1으로 합병 정렬합니다.
// 두 list의 정렬 기준이 > 연산인 greater라는 것을 predicate로 지정합니다.
lt1.merge(lt2, greater<int>() );
cout << "lt1: ";
for(iter = lt1.begin(); iter != lt1.end(); ++iter)
cout << *iter << ' ';
cout << endl;
cout << "lt2: ";
for(iter = lt2.begin(); iter != lt2.end(); ++iter)
cout << *iter << ' ';
cout << endl;
}
```
* 만약 정렬 기준이 다르다면 조건자를 이용해서 합병할 수 있다.
* 정렬 기준이 틀렸거나 합병할 list가 정렬되어 있지 않았다면 merge() 멤버 함수는 실패하며 오류가 발생한다.
```C++
lt1: 10 20 25 30 35 40 50 60
lt2:
```
# <br>list 주요 특징
* list는 시퀀스 컨테이너이며 노드 기반 컨테이너이다.
* 순차열 중간에 삽입, 제거가 빈번하게 발생하며 원소의 상대적인 순서가 중요하다면 list 컨테이너를 사용한다.
* list는 이중 연결 리스트 구조로 원소를 앞, 뒤에 모두 추가할 수 있다.
* 노드 기반 컨테이너이므로 []나 at() 멤버 함수는 제공하지 않는다.
* insert(), erase()는 효율적으로 동작한다.
* list는 다른 list와 결합할 때 좋은 컨테이너이다. splice(), merge() 등을 효율적으로 활용할 수 있다.
* list는 노드 기반 컨테이너이므로 양방향 반복자를 지원한다.
댓글
댓글 쓰기