*이 포스팅은 개인 학습을 위해 내용을 정리한 것이 목적입니다.
6.1 컨테이너의 공통적인 특징 및 동작
6.1.1 컨테이너의 공통적인 특징
- STL컨테이너의 공통적인 특징
1) 모든 컨테이너는 ‘값 의미론’을 제공한다.
- 컨테이너 삽입시 내부적으로 복사본을 생성. 모든 원소는 복사가능해야함. 복사시간이 오래걸릴 경우
객체의 포인터를 가져야 함
2) 일반적으로 모든 원소들은 순서를 가지고 있음.
- 각각의 컨테이너는 자신의 원소를 순회할 수 있도록 반복자를 제공한다.
3) 대부분 STL자체는 예외를 발생하지 않는다.
- 따라서 호출자는 동작에 대한 정확한 인자를 제공하는 것을 보장해 주어야 한다.
6.1.2 컨테이너의 공통적인 동작
1)초기화 관련
- 모든 컨테이너 클래스는 디폴트생성자, 소멸자, 복사생성자등을 제공, 주어진 범위의 원소들로 초기화,
다른컨테이너의 원소,배열, 표준입력으로부터 초기화 하는 기능등을 제공한다.
ex)
ContType c : 빈 컨테이너 생성
ContType c1(c2) : 같은 타입의 컨테이너 복사
ContType c(begin,end) : 컨테이너 생성 후, [begin,end)의 모든 원소들을 복사하여 초기화 함.
* 표준입력을 통한 초기화
|
std::deque<int> c((std::istream_iterator<int>(std::cin)),(std::istream_iterator<int>()); |
괄호에 주의할 것. 괄호가 없을 경우 c는 deque<int>타입을 반환하는 함수처럼 선언된 것.
2) 사이즈 관련
- size() : 컨테이너가 가지고 있는 원소의 개수 반환
- empty() : 컨테이너가 비어있는지 확인 (size() == 0보다 빠름)
- max_size() : 컨테이너가 가질 수 있는 최대 원소의 개수 반환
3) 비교와 관련된 동작
- '==', '!=', '<', '<=', '>', '>=' 의 규칙 3개
i) 두 컨테이너는 같은 타입을 가지고 있을 것
ii) 두 컨테이너의 원소들과 그 순서가 같다면 두 컨테이너는 같음
iii) 다른 컨테이너에 비해 작은 것을 검사하기 위해 사전방식의 비교가 사용됨
4) 할당과 Swap
- 만약 사용자가 컨테이너를 할당한다면, 소스의 모든 원소가 대상으로 복사되는 과정임. 만약 컨테이너
가 같은 타입의 원소를 가지고 있고, 소스가 더 사용되지 않는다면 swap을 이용하여 내부 데이터만을
교체함. 상수복잡도를 보장.
6.2 Vector
- 동적 배열과 비슷한 모델
6.2.1 vector의 능력
- 벡터는 원소를 자신의 내부 동적 배열에 복사. 원소들은 순서를 가짐. 순서가 있는 컬렉션이고, 랜덤 액
세스 제공한다. 그러나 중간에 데이터 삽입/삭제시 낮은 성능을 보인다.
1) 사이즈와 용량
벡터의 성능 향상의 방법으로 원소저장에 필요한 메모리보다 더 많은 메모리를 확보하는 것.
* capacity() : 벡터가 재할당 없이 추가적으로 수용가능한 원소의 개수 반환
* 벡터의 용량이 중요한 이유 2가지
i) 재할당은 원소의 모든 레퍼런스와 포인터, 반복자를 무효화 시킴
ii) 재할당은 시간을 필요로 한다.
* reserve() : 원하는 만큼의 용량을 확보하는 함수. 재할당을 피할 수 있다. 초기화 과정을 통해서도 재할
당을 피할 수 있다. 그러나 초기화과정에 많은 시간이 소요되므로 재할당을 피하기 위해 초
기화를 수행하는 것이라면 reserve를 사용할 것.
* 벡터는 초기에 2k의 메모리를 할당함. 만약 적은 원소를 가지고 많은 벡터를 사용하면 메모리낭비가 심
해짐. -> 다른 vector와 용량을 교체하여 해결할 수 있음.
6.2.2 vector의 동작들
1) 생성, 복사, 소멸동작
2) 수정하지 않는 동작
3) 할당과 관련된 동작
4) 원소 액세스
5) 반복자 함수들
6) 원소의 삽입 및 제거
6.2.3 기존의 배열처럼 벡터 사용하기
- C++표준 라이브러리에서는 벡터의 원소들이 연속된 메모리를 요구하는지에 대한 정의가 없으나 이러한
보장이 대세이므로 수정될 것. 그렇다면 다음과 같은 표현이 유효해질 수 있음
|
&v[i] == &v[0]+i; |
반복자는 포인터와 다르므로, 원소의 주소대신 반복자를 전달하는 것은 안됨
6.2.4 예외 핸들링
- 벡터에서의 예외 검사는 at()에 한해서만 제공됨. 벡터에 의해 호출된 함수에서 예외 발생시 다음과 같은
내용을 보장해 줌.
1) 원소가 push_back()으로 삽입하고 예외 발생시, 아무런 영향도 받지 않음
2) 원소의 복사 생성자나 할당 연산자에서 예외가 던져지지 않았다면, insert()는 성공하거나 아무런 영향
을 받지 않음
3) pop_back()은 어떤 예외도 던지지 않음
4) 원소의 복사 생성자나 할당 연산자에서 예외가 던져지지 않았다면, erase()와 clear()는 예외를 던지
지 않음.
5) swap()은 예외를 던지지 않음
6) 복사생성자나 할당연산자에서 절대로 예외를 던지지 않는 원소를 사용한다면, 모든 동작은 성공하거
나 아무런 영향을 받지 않음. 이러한 원소를 POD라고 함.
* POD : C++만의 특징을 가지지 않는 원소. 구조체가 이에 해당됨.
- POD의 조건
i) built-in type
* 기본변수 타입을 사용하고, 사용될 용량을 도출할 수 있어야 함.
ii) 가상화 함수가 없고 사용자 정의 할당자와 소멸자를 가지지 않은 class의 object
* 사용자 정의 할당자와 소멸자는 메모리 배치에 영향을 주지 않으나 할당문의 결과와 물리적인 배치가
일치하지 않을 수 있으므로 소유하지 않아야 함.
iii) non POD를 non-static멤버로 가지지 않은 class의 object
* static은 객체의 멤버에 포함되지 않으므로.
6.2.5 vector를 사용한 예제
6.2.6 vector<bool>클래스
- 벡터 원소 타입이 boolean일 경우, C++표준 라이브러리에서 제공하는 특별한 라이브러리.
- bool에 대한 벡터 구현은 각 원소에 대해 최소 1바이트를 예약하지만, vector<bool>은 1비트만을 사용
하는 특수화된 버전임. 따라서, 레퍼런스와 반복자를 다루는 특별한 방법이 필요함.
- vector<bool>은 다른 벡터가 요구되는 상황과는 충돌하지 않는다. vector의 템플릿 코드는 bool을 제외
하고는 동작한다. 그러나 vector<bool>은 비트연산을 수행하므로 일반적인 벡터보다는 느리다. 동적인
사이즈를 가지는 비트 필드.
|
함수명 |
동작 |
|
c.flip() |
모든 boolean원소들을 반전 |
|
m[idx].flip() |
인덱스가 idx인 원소를 반전 |
|
m[idx] = val |
val을 인덱스가 idx인 원소에 할당 |
6.3 Deque
- deque은 vector와 유사하나 양방향에 대하여 개방되어 있다.
6.3.1 deque의 능력
- 벡터와의 차이점
1) 원소들을 컨테이너의 앞과 끝에 삽입/삭제하는 과정이 빠름. amortized 복잡도를 가짐.
*amortized복잡도 : 전체적으로 일정한 성능을 가지나 최악의 경우도 가짐.
2) deque의 내부 자료구조는 원소를 액세스 하기 위해 하나이상의 간접성을 이용하기에 원소의 액세스
시간과 반복자 이동시간이 조금 더 느리다. (분리된 메모리 블록을 이용하므로)
3) 반복자는 기존의 포인터 타입이 아니라 반드시 스마트포인터 타입이어야 한다.
4) 만약 시스템에서 메모리블록에 대한 사이즈의 제한값이 존재할 경우 deque는 벡터에 비해 더 많은 원
소를 가질 수 있다. (분리된 메모리 블록을 사용하므로)
5) deque는 용량과 재할당 같은 제어 조건을 사용자에게 주지 않음. 원소의 삽입/삭제가 이루어질 때, 모
든 포인터와 레퍼런스, 반복자를 무효화 함(제일 앞,뒤 제외). 그러나 분리된 블록을 사용하므로 재할당
은 벡터보다 효율적이다 (모든 메모리 블록을 복사하지 않음).
6) 메모리 블록은 더 이상 사용되지 않을 때, 해제됨
- 벡터와 동일하게 적용되는 점
1) 컨테이너의 중간에 삽입/삭제하는 동작은 시간이 필요함.
2) 반복자는 랜덤 액세스를 지원
- deque를 사용하는 것이 좋을 경우
1) 컨테이너의 앞/끝으로 삽입 삭제가 이루어지는 경우
2) 컨테이너의 원소를 참조하지 않는 경우
3) 컨테이너가 사용되지 않을 때, 메모리가 해제되길 원하는 경우
6.3.2 deque의 동작
- 벡터와 유사하다. 그러나 다음과 같은 경우에만 벡터와 다름
1) 용량에 대한 함수 (capacity, reserve)를 지원하지 않음
2) 앞에 직접적으로 원소를 추가(push_front()), 삭제(pop_front())를 하는 함수를 지원
- deque사용시 주의할 점
1) at()을 제외한 모든 멤버함수는 반복자나 인덱스가 유효한지 검사하지 않음
2) 원소의 삽입,제거는 재할당을 유발함. 모든 삽입, 제거동작은 모든 포인터와 레퍼런스, 반복자를 무효
화 함. 그러나 맨 앞/뒷부분의 경우 레퍼런스와 포인터는 유효함 (반복자는 무효화).
6.3.4. deque예제
6.4 List
- list는 이중연결리스트처럼 원소를 관리함.
6.4.1 List의 능력
- vector, deque와의 차이점
1) 랜덤 액세스 지원하지 않음. 액세스 속도가 상대적으로 느림
-> []연산자와 at()을 제공하지 않음
2) 다른 원소들이 이동할 필요가 없기 때문에 어느 위치에서도 삽입/삭제가 빠름. 포인터 값만 조작하면
되기 때문.
3) 삽입과 삭제 동작이 모든 포인터와 레퍼런스, 반복자를 무효화 하지 않음
4) 거의 대부분의 동작이 성공하거나 아무런 영향을 받지 않음
- 멤버 함수들의 차이
1) []과 at()이 없음
2) 용량과 재할당과 관련된 함수 제공 안함. (각 원소는 별도의 메모리 소유)
3) 원소를 이동시키기 위한 멤버함수를 제공함. STL알고리즘보다 빠름. 멤버함수는 데이터 복사를 안하
고 포인터 값만 재지정 하므로
6.4.2 list의 동작
1) 생성, 복사, 소멸과 관련된 동작
2) 수정하지 않는 동작
3) 할당관련
4) 원소 액세스
5) 반복자 함수들
6) 원소의 삽입 및 제거
7) splice함수
- 링크드리스트의 최대 장점은 어떤 위치에 원소를 삽입하거나 제거하여도 상수복잡도를 보장해 주는
것. 이러한 점을 살리기 위해 list에서는 다음과 같은 함수들을 제공한다.
6.4.3 예외 핸들링
- list는 가장 강력한 예외 안정성을 제공함. 할당연산자와 sort만 기본적인 안정성을 제공함. 모든 동작들
이 영향을 받지 않음.
- push_back, push_front, insert, resize : 성공하거나 아무런 영향을 받지 않음
- pop_back, pop-_front, erase, clear, splice, reverse, swap : 예외를 던지지 않음
- remove, remove_if, unique, merge : 원소를 비교하는 동작에서 예외를 던지지 않으면 예외를 던지지
않는다.
6.4.4 list를 사용한 예제
6.5 set과 multiset
- set, multiset은 주어진 기준에 따라 원소를 자동적으로 정렬하는 컨테이너임.
-> 연관컨테이너의 특징. map/multimap도 동일하다
- “strict weak ordering”을 만족할 것. 해당 상황은 아래의 조건을 만족해야 함
1) 반드시 반대칭적일 것
x >y가 true이면, y<x는 반드시 false
2) 반드시 추이적일 것
x <y가 true, y<z 가 true이면 x<z가 true
3) 반드시 비반사적이어야 함
연산자 <의 경우, x < x가 반드시 false를 보장하여야 함. 즉, op(x,x)에서는 항상 false
6.5.1 set과 multiset의 능력
- set과 multiset은 균형 2진트리처럼 구현되어 있다. 원소의 값을 직접적으로 수정할 수 없는 단점.
-> 직접 수정시, 정렬 상태가 보장되지 않음
1) 직접적인 원소 액세스를 허락하지 않음
2) 반복자를 통한 간접적인 액세스에 제한을 받음
6.5.2 set과 multiset의 동작
1) 생성, 복사, 소멸과 관련된 동작.
- 정렬 기준에 대하여 2가지 방식으로 정의 가능
i) 템플릿의 파라미터로 넣는 방식
정렬기준은 컨테이너 타입의 한 부분이 됨. 타입 시스템은 같은 정렬 기준을 가진 컨테이너에 한해서
만 결합할 수 있음을 보장함.
ex) std::set<int,std::greater<int>> coll;
ii) 생성자의 파라미터로 넣는 방식
같은 타입에 대해 다른 정렬 기준이 필요하거나 정렬 기준을 런타임시 처리하고 싶은 경우 유용함.
2) 수정하지 않는 동작
3) 특별한 검색 함수들
4) 할당
5) 반복자 함수
6) 컨테이너 원소의 삽입과 제거
* insert함수의 리턴 값이 set의 경우 pair<iterator, bool>임. (multiset은 iterator). set은 중복
을 지원하지 않기에, pair로 리턴받고, second : 성공여부, first : 삽입된 위치 를 의미함.
* 시퀀스 컨테이너와 연관 컨테이너의 erase()의 반환값
- 시퀀스 : iterator
- 연관 : void
연관 컨테이너의 경우 2진트리여서 성공여부 반환에 시간이 필요하다.
6.5.4 set과 map을 이용한 예제
6.5.5 런타임시에 정렬기준을 정하는 예제
-기본 정렬타입은 less<type>임. 다른 정렬타입도 추가 가능하다. 하지만 런타임시에 결정하도록 변경
* 함수명 뒤에 const를 붙이는 이유
|
void func() const {...} |
위에 const는 클래스의 멤버함수에만 사용가능하다. 저 키워드는 해당 멤버함수에서 멤버 변수를 변경하지 않음을 의미한다.
6.6 Map과 Multimap
- map과 multimap은 key/value를 한 쌍으로 취급하는 원소를 관리하는 컨테이너임.
- 필수 조건
1) key/value쌍은 반드시 할당가능하고, 복사 가능해야 함
2) key는 반드시 정렬기준에 따라 비교될 수 있어야 함
6.6.1 map과 multimap의 능력
- set/multiset과 비슷하다. 하지만 key의 경우 직접적인 수정이 불가하나, value의 경우 직접 수정 가능
6.6.2 map과 multimap의 동작
1) 생성, 복사, 소멸관련동작
2) 수정하지 않는 동작
3) 특별한 검색함수
4) 할당
5) 반복자 함수와 원소 액세스
6) 컨테이너 원소의 삽입과 제거
* set/multiset의 주의사항과 동일하다. 그러나 map,multimap은 key/value의 쌍이다. 원소 전달 방법은 다
음과 같이 3종류가 있다.
i) value_type을 사용하기
- 암시적형 변환을 피하기 위해 value_type을 사용하여 정확한 타입을 전달.
ex)
|
std::map<std::string,float> coll; … coll.insert(std::map<std::string,float>::value_type(“otto”,22.3)); |
ii) pair<>를 사용
- pair<>를 직접 사용함.
ex)
|
std::map<std::string, float> coll; … //암시적 형 변환 사용 coll.insert(std::pair<std::string, float>(“otto”,22.3)); //암시적 형 변환 사용 안함 coll.insert(std::pair<const std::string, float>(“otto”, 22.3)); |
iii) make_pair()를 사용
- pair객체를 생성하여주는 함수를 사용.
* multiset이나 multimap은 중복된 키가 허용되므로, 특정 키를 삭제 시, find를 사용함. 그러나 이 경우
알고리즘의 find가 아닌 find멤버함수를 사용하여 성능을 향상시키는 편이 좋음
6.6.3 연관배열처럼 map을 사용하기
- 연관 컨테이너의 경우 반드시 반복자를 사용하여 액세스 하여야 하나, map은 []연산자가 허용된다. []
연산자의 인덱스는 원소의 정수 위치가 아니라 map의 key임. 만약 invalid한 키일 경우 해당 키를 사용하
는 새로운 원소를 삽입한다.
- 연관배열 동작의 장점과 단점
1) map에 보다 편리하게 새로운 원소를 삽입할 수 있다는 장점이 있다.
2) 그러나 실수로 새로운 원소가 삽입될 수 있음.
ex)
|
std::map<std::string, float> coll; ... coll["abc"] = 7.7; coll["abcd"] = 7.5; //Key가 abcd가 아닌 abc를 의도한 경우라면? |
6.6.4 예외처리
- set/ multiset과 동일한 안정성을 보장한다.
6.6.5 map/multimap 예제
특정 value를 가지고 있는 첫 번째 원소 찾기
6.6.6 map과 스트링, 런타임 정렬기준 예제
- map의 사용법, 함수객체의 사용법, 정렬기준의 실시간 정의, 스트링의 사전식 비교
6.7 다른 STL 컨테이너
- 사용자가 직접 작성한 컨테이너나, 기존의 배열, 스트링도 STL의 컨테이너처럼 사용할 수 있게 해줌.
1) invasive접근방법
- 사용자는 STL이 필요로 하는 인터페이스를 제공하여 주면 됨. begin, end등의 함수
ex) string을 STL컨테이너처럼 사용하고자 할 경우.
2) noninvasive접근방법
- 알고리즘과 특별한 컨테이너의 상호 인터페이스로 사용되는 특별한 인터페이스를 작성하거나 제공
배열처럼 begin, end가 없으면 포인터 같은 대체반복자나 클래스 제공해야함
배열 예제
3) wrapper 접근방법
- 두 방법을 결합하여 STL컨테이너와 유사한 인터페이스를 제공하며, 내부자료구조를 은닉하는 래퍼 클
래스를 작성하는 방법.
배열래퍼클래스
래퍼클래스 사용하기
6.8 ‘레퍼런스 의미론’구현
- 일반적으로 STL의 컨테이너들은 ‘값 의미론’을 제공함. ‘레퍼런스 의미론’을 사용하고 싶을 경우, 스마
트 포인터를 사용하여야 한다. auto_ptr과 유사하지만, 하나의포인터 값에 대해 둘 이상의 소유자를 허용
하고, 포인터를 참조하던 마지막 객체가 파괴되는 순간에 해당 포인터를 해제.
실 사용 예제
6.9 언제 어느 컨테이너를 사용할 것인가?
1) 기본적으로 벡터를 사용한다. 벡터는 간단한 내부 자료구조를 사용하며 랜덤 액세스를 지원한다.
2) 만약 원소를 컨테이너의 앞/끝에 자주 삽입/제거를 한다면 반드시 deque를 사용할 것. 또한 원소 제거
시 컨테이너의 메모리 사용량이 줄어들어야 할 때에도 deque를 사용할 것
3) 원소의 제거/삽입/이동이 컨테이너 중간에서 빈번할 경우 list를 고려해볼 것. list의 경우 삽입 삭제가
빠르지만, 원소 액세스시 성능상에 제약을 받음
4) 예외에 대해서 각각의 동작이 성공하거나 아무런 영향도 가지지 않는 컨테이너가 필요하다면 list나 연
관컨테이너를 고려할 것
5) 특정기준에 따라 원소를 자주 검색해야 하면 set/multiset을 사용할 것.
6) key/value쌍을 위해서는 map/multimap을 사용할 것
7) 연관배열이 필요하다면 map을 사용할 것
8) 사전이 필요하다면 multimap을 사용할 것
* 해시 테이블도 고려해볼만 함. 그러나 해시 컨테이너는 순서가 없으므로, 순서에 의존이 필요하다면 사
용하지 않는편이 좋음
6.10 컨테이너의 타입과 멤버에 대한 자세한 설명
6.10.1 타입 정의
1) container::value_type
- 원소의 타입.
- set과 multiset의 경우 원소는 상수, map과 multimap의 경우 원소는 pair임
- vector, deque, list, set, multiset, map, multimap, string에서 제공됨
2) container::reference
- 원소의 레퍼런스타입 ,container::value_type과 동일
- vector<bool>의 경우 reference는 보조클래스
- vector, deque, list, set, multiset, map, multimap, string에서 제공됨
3) container::const_reference
- 상수 원소의 레퍼런스 타입, const container::value_type&
- vector<bool>의 경우 bool
- vector, deque, list, set, multiset, map, multimap, string에서 제공됨
4) container::iterator
- 반복자의 타입
- vector, deque, list, set, multiset, map, multimap, string에서 제공됨
5) container::const_iterator
- 상수 반복자의 타입
- vector, deque, list, set, multiset, map, multimap, string에서 제공됨
6) container::reverse_iterator
- 역방향 반복자의 타입
- vector, deque, list, set, multiset, map, multimap, string에서 제공됨
7) container::const_reverse_iterator
- 역방향 상수반복자의 타입
- vector, deque, list, set, multiset, map, multimap, string에서 제공됨
8) container::size_type
- 사이즈를 위한 unsigned 정수 타입
- vector, deque, list, set, multiset, map, multimap, string에서 제공됨
9) container::difference_type
- 차이(간격)를 위한 값으로 signed 정수 타입
- vector, deque, list, set, multiset, map, multimap, string에서 제공됨
10) container::key_type
- 연관컨테이너 원소의 key타입. set과 multiset의 경우 value_type과 동일
- set, multiset, map, multimap에서 제공됨
11) container::mapped_type
- 연관컨테이너 원소의 value타입
- map, multimap에서 제공됨
12) container::key_compare
- 연관 컨테이너의 비교 기준의 타입
- set, multiset, map, multimap에서 제공
13) container::value_compare
- 전체 원소 타입을 위한 비교 기준의 타입
- set/multiset : key_compare와 동일, map/multimap : 비교기준을 위한 보조클래스
- set, multiset, map, multimap에서 제공
14) container::allocator_type
- 할당자의 타입
- vector, deque, list, set, multiset, map, multimap, string에서 제공됨
6.10.2 생성, 복사, 소멸과 관련된 동작
1) container::container()
- 기본 생성자. 새로이 빈 컨테이너 생성.
- vector, deque, list, set, multiset, map, multimap, string에서 제공됨
2) explicit container::container(const CompFunc& op)
- 정렬 기준인 op와 함께 빈 컨테이너 생성. 기준은 “strict weak ordering”에 부합할 것
- set, multiset, map, multimap
3) explicit container::container(const container& c)
- 복사생성자. 기존의 c컨테이너를 복사하여 새로운 컨테이너 생성(모든 원소에 대해 복사생성자 호출
함)
- vector, deque, list, set, multiset, map, multimap, string에서 제공됨
4) explicit container::container( size_type num)
- num개의 원소와 함께 컨테이너 생성. 각 원소는 기본생성자에 의해 생성됨
- vector, deque, list에서 제공
5) container::container(size_type num, const T& value)
- num개의 원소와 함께 컨테이너를 생성. 각 원소는 value를 복사. T는 원소의 타입. 스트링의 경우
value는 레퍼런스로 전달되지 않음
- vector, deque, list, string에서 제공
6) container::container(InputIterator beg, InputIterator end)
- [beg, end) 범위의 원소들로 초기화된 컨테이너 생성. 이 함수는 멤버 템플릿임
- vector, deque, list, set, multiset, map, multimap, string에서 제공됨
7) container::container(InputIterator beg, InputIterator end, const CompFunc& op)
- [beg,end)범위의 원소들로 초기화된 컨테이너 생성, 정렬조건은 op. 멤버템플릿임. “strict weak
ordering”에 부합할 것
- set, multiset, map, multimap에서 제공
8) container::~container()
- 소멸자. 모든 원소를 제거하고 메모리에서 해제. (모든 원소에 대해 소멸자 호출)
- vector, deque, list, set, multiset, map, multimap, string에서 제공됨
6.10.3 수정하지 않는 동작
* 사이즈 관련 동작
1) size_type container::size() const
- 현재 원소의 개수 반환. 비어있는지 여부는 empty로 확인
- vector, deque, list, set, multiset, map, multimap, string에서 제공됨
2) bool container::empty() const
- 컨테이너가 비어있는지 여부 판단.
- vector, deque, list, set, multiset, map, multimap, string에서 제공됨
3) size_type container::max_size() const
- 컨테이너가 소유 가능한 최대 원소의 개수 반환
- vector, deque, list, set, multiset, map, multimap, string에서 제공됨
* 용량관련 동작
1) size_type container::capacity() const
- 컨테이너가 재할당 없이 가질 수 있는 원소의 개수 반환
- vector, string등에서 제공
2) void container::reserve(size_type num)
- 최소 num개 원소만큼의 메모리를 예약함. num이 실제 용량보다 작다면 스트링은 용량을 줄일 수 있
음(vector는 아님). 재할당을 하지 않아 속도의 증가 및 레퍼런스와 포인터, 반복자를 유효하게 보관할
수 있음
- vector, string에서 제공
* 비교 연산
1) bool comparison( const container& c1, const container& c2)
- 같은 타입의 두 컨테이너를 비교하여 결과 반환
- '==', '!=', '<', '<=', '>', '>=' 중 하나임
- 두 컨테이너가 동일한 개수의 원소를 가지고, 같은 순서로 가지고 있으면 동일한 것
- vector, deque, list, set, multiset, map, multimap, string에서 제공됨
* 연관된 컨테이너에 대해 수정하지 않는 동작
- 아래 동작들은 모두 map, set, multimap, multiset에서 제공된다.
- T는 value의 타입이고, 해당 타입은 set/multiset : 원소, map/multimap : key임
1) size_type container::count(const T& value) const
- value와 동일한 원소의 개수를 반환, T는 정렬된 value의 타입, 선형복잡도
2) iterator container::find( const T& value)
const_iterator container::find(const T& value) const
- value와 동일한 값을 가지는 첫번째 원소의 위치를 반환. (없으면 end()). 로그복잡도
3) iterator container::lower_bound(const T& value)
const_iterator container::lower_bound(const T& value) const
- value와 같거나 큰 값을 가지는 첫 번째 원소의 위치를 반환. 없으면 end(). 로그복잡도
- 정렬을 깨트리지 않고, 제일 처음으로 삽입할 수 있는 위치 (upper_bound는 마지막위치)
4) iterator container::upper_bound(const T& value)
const_iterator container::upper_bound(const T& value) const
- value보다 큰 값을 가지는 첫 번째 원소의 위치를 반환. 없으면 end(). 로그복잡도
5) pair<iterator, iterator> container::equal_range(const T& value)
pair<const_iterator, const_iterator> container::equal_range(const T& value) const
- value가 정렬을 깨트리지 않고 삽입될 수 있는 첫, 마지막 위치 리턴. 로그복잡도.
6) key_compare container::key_comp()
- 비교 기준을 반환
7) value_compare container::value_comp()
- 비교 기준처럼 사용된 객체를 반환. set/multiset에서는 key_comp와 동일
6.10.4 할당
1) container& container::operator = (const container& c)
- c의 모든 원소를 할당. 기존에 존재하는 원소에는 할당연산자, 새롭게 추가되는 원소에는 복사생성자,
제거되는 원소에는 소멸자가 호출됨
- vector, deque, list, set, multiset, map, multimap, string에서 제공됨
2) void container::assign(size_type num, const T& value)
- value를 가진 num개의 원소를 할당. T는 원소의 타입일 것
- vector, deque, list, string에서 제공
3) void container::assign(InputIterator beg, InputIterator end)
- [beg,end)의 원소들을 할당. 멤버템플릿.
- vector, deque, list, string에서 제공
4) void container::swap( container& c)
- c와 모든 내용을 교체. 컨테이너는 원소와 정렬기준을 교체. 상수복잡도
- vector, deque, list, set, multiset, map, multimap, string에서 제공됨
5) void swap(container& c1, container& c2)
- c1.swap과 동일. 연관컨테이너에서 비교 기준의 복사or 할당에서 예외발생시 이 함수에서 예외를 던
짐. 다른 컨테이너일 경우 던지지 않음
- vector, deque, list, set, multiset, map, multimap, string에서 제공됨
6.10.5 원소의 직접적인 액세스
1) reference container::at(size_type idx)
const_reference container::at(size_type idx) const
- idx위치의 원소를 반환. 유효하지 않은 인덱스인 경우 out_of_range예외 발생.
- vector, deque, string에서 제공
2) reference container::operator[](size_type id)
const_reference container::operator[](size_type idx) const
- at과 동일하나, 더 빠름. 그러나 인덱스의 유효성을 보장해주어야 함
3) T& map::operator[](const key_type& key)
- 연관 배열을 위한 []연산자. map에서 대응되는 value를 반환.
4) reference container::front()
const_reference container::front() const
- 첫번째 원소를 반환. 최소한 하나의 원소가 있다는 것을 보장해 주어야 함
- vector, deque, list에서 제공
5) reference container::back()
const_reference container::back() const
- 마지막 원소를 반환. 최소 하나의 원소가 있음을 보장해 주어야 함
- vector, deque, list에서 제공
6.10.6 반복자와 관련된 연산자
* vector, deque, list, set, multiset, map, multimap, string에서 제공됨
* 컨테이너 타입에 따른 반복자 카테고리
i) 랜덤액세스 : vector, deque, string
ii) 양방향 : list, set,multiset, map, multimap
* set/multiset(원소는 상수), map/multimap(key는 상수)
1) iterator container::begin()
const iterator container::begin() const
- 컨테이너의 첫번째 위치. 비어있으면 end
2) iterator container::end()
const iterator container::end() const
- 컨테이너의 마지막 위치. 비어있으면 begin
3) iterator container::rbegin()
const iterator container::rbegin() const
- 컨테이너의 역방향 첫 번째 위치. 비어있으면 rend
4) iterator container::rend()
const iterator container::rend() const
- 컨테이너의 역방향 마지막 위치. 비어있으면 rbegin
6.10.7 원소의 삽입과 제거
* T는 원소의 타입
1) iterator container::insert( const T& value)
pair<iterator, bool> container::insert(const T& value)
- 연관 컨테이너에 value를 복사하여 삽입. 중복을 허용할 경우 첫 번째 시그너처를 가짐. 이 경우 새로
운 원소의 위치를 반환
- 중복을 허용하지 않을 경우 두번째 시그너처를 가짐. 중복일 경우 기존원소의 위치와 false를 반환하
고, 중복이 아니면 새로운 원소의 위치와 true반환
- set, multiset, map, multimap에서 제공
2) iterator container::insert(iterator pos, const T& value)
- pos의 위치에 value의 복사본을 삽입, 새로운 위치를 반환. 연관컨테이너에서는 삽입을 위한 어느 위
치에서부터 검색을 실시하는가에 대한 힌트로만 동작
- vector, deque의 경우, 반복자와 레퍼런스를 무효화 할 수 있음.
- vector, deque, list, set, multiset, map, multimap, string에서 제공됨
3) void container::insert(iterator pos, size_type num, const T& value)
- pos의 위치에 value를 num개만큼 복사하여 삽입.
- vector, deque의 경우, 반복자와 레퍼런스를 무효화 할 수 있음
- vector, deque, list, string에서 제공
4) void container::insert((iterator pos), InputIterator beg, InputIterator end)
- [beg,end)범위의 원소들을 복사하여 삽입
연관 컨테이너는 pos가 없음. 그 외의 컨테이너에서는 pos의 위치 이후에 삽입(pos필수)
5) void container::push_front(const T& value)
- 첫 번째 원소로 value의 복사본을 삽입
- insert(begin(), value)와 동일
- deque에 대해 다른 원소에 대한 반복자를 무효화 함
- deque, list에서 제공
6) void container::push_back(const T& value)
- insert(end(), value)와 동일
- vector의 경우 재할당이 이루어지면, 다른 원소에 대한 반복자와 레퍼런스가 무효화 되고, deque의
경우 다른 원소에 대한 반복자들을 무효화 하나 레퍼런스는 유효
- list, vector, deque, string에서 제공
7) void list:remove(const T& value)
void list::remove_if(unarypredicate op)
- remove는 value와 같은 값을 제거, remove_if는 op가 true를 반환하는 모든 원소를 제거. op는 함수
가 호출되는 동안 상태를 변경하면 안된다.
- 남은 원소의 순서는 유지된다.
8) size_type container::erase(const T& value)
- 연관 컨테이너에서 value와 동일한 값을 가진 모든 원소를 제거. 제거된 수를 반환. 제거된 원소의 소
멸자를 호출.
- map, multimap, set, multiset에서 제공
9) void container::erase(iterator pos)
iterator container::erase(iterator pos)
- pos의 위치에서 원소를 제거. 시퀀스 컨테이너는 두번째 시그니처(다음 위치를 반환), 연관 컨테이너
는 첫번째 시그니처를 반환.
- 제거되는 원소의 소멸자를 호출. pos가 유효함을 보장해 주어야 함.
- vector나 deque는 다른 원소에 대한 반복자와 레퍼런스를 무효화함. 또한 이 두 경우에는 원소의 복
사생성자와 할당연산자에서 예외가 던져질 경우에만 예외를 던져줌, 나머지는 안던져줌.
- vector, deque, list, set, multiset, map, multimap, string에서 제공됨
10) void container::erase(iterator beg, iterator end)
iterator container::erase(iterator beg, iterator end)
- [beg,end)범위의 원소를 제거. 제거시 각 원소의 소멸자를 호출한다. 연관 컨테이너는 첫번째 시그
니처를 가지고, 시퀀스 컨테이너는 두번째 시그니처를 가진다(이 경우 반환값은 제거된 원소 다음 위
치 or end()).
- 모든 범위는 beg는 포함하지만 end는 포함하지 않음. beg과 end는 유효함을 보장해야 함
- vector와 deque는 다른 원소에 대한 반복자와 레퍼런스를 무효화 함. 또한 이 두 경우에는 원소의 복
사생성자와 할당연산자에서 예외가 던져질 경우에만 예외를 던져줌, 나머지는 안던져줌.
- vector, deque, list, set, multiset, map, multimap, string에서 제공됨
11) void container::pop_front()
- 컨테이너의 첫 번째 원소를 제거. container.erase(container.begin())과 동일
- 컨테이너가 비어있지 않음을 보장해야 함.
- deque, list에서 제공
12) void container::pop_back()
- 컨테이너의 마지막 원소를 제거. container.erase(--container.end())와 동일하나 vector에 대해서는
이 표현이 다를 수 있다.
- 컨테이너가 비어있지 않음을 보장해야 함.
- vector, deque, list에서 제공
13) void container::resize( size_type num)
void container::resize( size_type num, T value)
- 원소의 개수를 num개로 변경.
- size()와 num을 비교한 결과에 따라 다음과 같이 동작
i) size() == num : 아무런 영향을 받지 않음
ii) size() < num : 원소가 생성되어 컨테이너에 추가됨. 기본 생성자를 이용해 생성되나 두번째 시그
니처로 호출된 경우 값은 value로 생성된다.
iii) size() > num : 원소들의 끝에서부터 제거되며 제거되는 원소들의 소멸자 호출. size변경됨
- vector, deque는 다른 원소에 대한 반복자와 레퍼런스를 무효화 함. 이 경우에는 원소의 복사 생성자
와 할당연산자에서 예외가 발생하지 않으면 성공하거나 아무 영향을 받지 않음. list는 성공하거나 아
무런 영향을 받지 않음.
- vector, deque, list, string에서 제공됨
14) void container::clear()
- 모든 원소들을 제거하고, 제거된 원소들에 대해서는 소멸자를 호출함.
- 컨테이너에 대한 모든 반복자와 레퍼런스를 무효화 시킴.
- vector, deque의 경우 원소의 복사 생성자와 할당연산자에서 예외가 던져질 경우에만 예외를 던짐.
다른 컨테이너에서는 예외를 던지지 않음
- vector, deque, list, set, multiset, map, multimap, string에서 제공됨
6.10.8 list의 특별한 멤버 함수들
1) void list::unique()
void list::unique(BinaryPredicate op)
- list원소의 연속된 중복 값을 제거함. 단, 두번째 시그니처의 경우 op의 조건이 true가 되는 원소 모두를
제거함. 두 형ㅌ태 모두 제거된 원소에 대한 소멸자를 호출함.
- op는 함수가 호출되는 동안 자신의 상태를 변경해서는 안됨.
- unique()알고리즘의 특별한 형태임
- 원소의 비교 동작에서 예외를 던지지 않으면, 이 함수는 예외를 던지지 않음
2) void list::splice(iterator pos, list& source)
- source의 모든 원소를 *this의 pos위치 앞으로 이동. 호출 후 source는 빈 컨테이너가 됨
- source와 *this가 다른 컨테이너임과 pos가 유효한 위치임을 보장하여야 함.
3) void list::splice(iterator pos, list& source, iterator sourcePos)
- source의 sourcePos위치의 원소를 *this의 pos위치에 삽입. source와 *this가 같은 컨테이너면 원소
는 한 컨테이너 안에서 이동되고, 둘이 다르면 호출 후 *this는 최소 1개의 원소를 가짐
- pos는 *this에서 유효한 위치, sourcePos는 source에서 유효한 위치임을 보장해야 함.
4) void list::splice(iterator pos, list& source, iterator sourceBeg, iterator sourceEnd)
- source의 [sourceBeg, sourceEnd)의 모든 원소를 *this의 pos위치에 삽입. source와 *this가 같은 컨
테이너면 한 컨테이너 안에서 이동되고, 다르면 *this는 호출 후 최소 1개의 원소를 가짐
- pos는 *this에서, sourceBeg,sourceEnd는 source에서 유효한 위치임을 보장해야함.
5) void list::sort()
void list::sort(CompFunc op)
- list의 원소를 정렬함. 두번째 형태는 op의 조건에 따라 정렬이고, 첫 번째는 <로 비교
- 동일한 값을 가지는 원소의 순서는 유지됨
- sort()와 stable_sort()알고리즘의 특별한 버전임
6) void list::merge(list& source)
void list::merge(list& source, CompFunc op)
- source의 모든 원소를 *this로 병합. 호출 후, source는 빈 컨테이너가 된다.
- *this와 source가 정렬된 상태라면, 함수 호출 후에도 결과는 정렬된 상태임.
- 첫번째 형태는 <가 정렬기준이나, 두번째는 op를 정렬 기준으로 함
- merge()알고리즘의 특별한 형태.
- 원소의 비교 동작에서 예외를 던지지 않으면 이 함수는 예외를 던지지 않음.
6.10.9 할당자 지원
- 모든 STL컨테이너는 할당자라고 정의된 특별한 메모리 모델과 함께 사용된다. 모든 표준 컨테이너들은
할당자 타입의 인스턴스를 요구함.
1) 기본적인 할당자 멤버
i) container::allocator_type
- 할당자의 타입
- vector, deque, list, set, multiset, map, multimap, string에서 제공됨
ii) allocator_type container::get_allocator() const
- 컨테이너의 메모리 모델을 반환함
- vector, deque, list, set, multiset, map, multimap, string에서 제공됨
2) 생성자에서 사용되는 할당자 인자
i) explicit container::container(const Allocator& alloc)
- 메모리 모델로 alloc을 사용하는 새로운 빈 컨테이너를 생성
- vector, deque, list, set, multiset, map, multimap, string에서 제공됨
ii) container::container( const CompFunc& op, const Allocator& alloc)
- 메모리 모델로 alloc을 사용하는 빈 컨테이너 생성, 정렬조건은 op
- set, multiset, map, multimap에서 제공됨
iii) container::container( size_type num, const T& value, const Allocator& alloc)
- 메모리 모델로 alloc을 사용하고 value값을 가진 num개의 원소를 가진 컨테이너 생성
- T는 원소의 타입. string의 경우 value는 레퍼런스로 전달되지 않음
- vector, deque, list, string에서 제공됨
iv) container::container(InputIterator beg, InputIterator end, const Allocator& alloc)
- [beg, end) 범위의 모든 원소들로 초기화 된 컨테이너를 생성. 메모리 모델은 alloc임
- 멤버 템플릿. 범위내 존재하는 원소들은 컨테이너 타입과 호환되면 어떤 타입도 가능
- vector, deque, list, set, multiset, map, multimap, string에서 제공됨
v) container::container(InputIterator beg, InputIterator end, const CompFunc op, const Allocator&
alloc)
- [beg, end) 범위의 원소들로 초기화된 컨테이너 생성. 메모리모델은 alloc, 정렬조건은 op
- 멤버 템플릿. 범위내 존재하는 원소들은 컨테이너 타입과 호환되면 어떤 타입도 가능
- set, multiset, map, multimap에서 제공됨
참조 : C++ Standard Library - A tutorial and Reference
댓글