SET

set은 순서를 가지고 중복없이 원소를 저장하는 컨테이너입니다.

(순서가 없으면 unordered_map이고, 중복이 가능하면 multiset입니다.)

 

set에서의 값으로 원소를 식별할 수 있습니다. 값이 키 그 자체입니다.

값은 중복되지 않습니다. 즉, unique합니다.

 

set에 들어간 원소는 수정할 수 없고, 삽입하거나 삭제하여 사용합니다.

 

set의 원소는 특정 기준에 따라서 정렬됩니다.

 

set은 키값으로 접근할 때 unordered_set에 비해 느립니다. 하지만 순서대로 순회할 수 있습니다.

 

set은 이진 탐색트리로 구현됩니다.

 

컨테이너 속성

연관 컨테이너

키를 사용해서 원소를 참조합니다. 절대적인 위치와 상관없이 키를 사용해 원소에 접근합니다.

 

순서

컨테이너의 원소는 특정한 순서를 가집니다.

 

집합

원소의 값은 원소를 식별하는데 사용되는 키입니다.

 

고유 키

원소의 키는 고유한 값을 가져, 중복되지 않습니다.

 

Allocator-aware

컨테이너는 요구에 맞게 원소를 동적으로 할당하고 해제 합니다.

 

멤버함수

생성자 set을 생성합니다.
파괴자 set을 파괴합니다.
=연산자 컨테이너의 content를 복사합니다.

 

Iterators

begin 첫번째 element를 가리키는 이터레이터를 반환한다.
end 마지막 element를 가리키는 이터레이터를 반환한다.
rbegin 마지막 element를 가리키는 역 이터레이터를 반환한다. 이터레이터를 증가시키면 역방향으로 그 다음 element를 가리킨다.
rend 첫번째 element를 가리키는 역 이터레이터를 반환한다.
cbegin 첫번째 element를 가리키는 const 이터레이터를 반환한다. 가리키는 객체의 값을 수정할 수 없다.
cend 마지막 element를 가리키는 const 이터레이터를 반환한다. 가리키는 객체의 값을 수정할 수 없다.
crbegin 마지막 element를 가리키는 const 역 이터레이터를 반환한다. 가리키는 객체의 값을 수정할 수 없다.
crend 첫번째 element를 가리키는 const 역 이터레이터를 반환한다. 가리키는 객체의 값을 수정할 수 없다.

 

Capacity

empty 컨테이너가 비어있는지 확인한다.
size set의 크기를 반환한다.
max_size set이 가질 수 있는 element의 최대 크기를 반환한다.

 

Modifiers

insert element를 삽입한다.
erase element를 제거한다.
swap 다른 set의 내용물과 자신의 내용물을 서로 바꾼다
clear 내부 element를 모두 제거한다.
emplace element를 생성 후 삽입한다.
emplace_hint element를 생성 후 힌트를 사용해 삽입합니다. 위치에 대한 힌트로 원소가 들어갈 위치가 예상되는 경우 사용하면 성능이 향상됩니다.

 

Observers

key_comp 비교 객체를 반환합니다.
value_comp 비교 객체를 반환합니다.

 

Operations

find 찾는 원소의 이터레이터를 반환합니다.
count 특정한 값의 갯수를 반환합니다. set의 경우 값이 유일하기 때문에 1이나 0만 반환합니다.
lower_bound 하한(같거나 큰)이 되는 이터레이터를 반환합니다. 1, 3, 5, 7, 9 에서 2을 하한으로 잡으면 3이 반환됩니다.
upper_bound 상한(큰)이 되는 이터레이터를 반환합니다. 1, 3, 5, 7, 9 에서 6을 상한으로 잡으면 7이 반환됩니다.
equal_range 그 값의 상한과 하한의 이터레이터를 모두 반환합니다. pair로 반환합니다.

 

'언어 > C++' 카테고리의 다른 글

[C++/STL] 컨테이너(Containers)  (0) 2020.02.21
[C++/STL]벡터(vector)  (0) 2020.02.20
[C++/STL] 리스트(List)  (0) 2020.02.20

표준 컨테이너

컨테이너는 객체를 담는 객체이다.

이 컨테이너들은 클래스 템플릿으로 구현되어 다양한 타입의 element를 지원한다.

 

컨테이너는 elements를 위한 저장공간을 관리하고, element에 접근하기위한 멤버 함수를 제공한다. 접근할 때에는 직접 element에 접근할 수도 있고 iterator를 통해서 접근할 수도 있다.

 

컨테이너는 프로그래밍을 하면서 가장 일반적으로 사용되는 자료구조들로 이루어져있다.

동적배열(vector), 큐, 스택, 힙(priority_queue), 링크드 리스트(list), 트리(set), 연관배열(map)

 

컨테이너들은 몇몇 멤버함수를 공통적으로 갖는다. 

프로그래밍을 하면서 사용할 컨테이너를 고르는 경우, 컨테이너가 제공하는 기능만으로 결정하는 것이 아니라 컨테이너의 내부 구현된 방식을 이해하고 결정해야한다. 특히 순차 컨테이너의 경우 삽입, 삭제, 접근의 효율성이 차이가 난다.

 

스택, 큐, 우선순위 큐는 컨테이너 어답터이다.

컨테이너 어답터는 완전한 컨테이너 클래스가 아니라 기존 컨테이너 클래스에 의존해 특정한 인터페이스를 제공하는 방식이다.

 

컨테이너 클래스 템플릿

C++11에서 추가된 함수는 배경색을 칠했다.

 

순차 컨테이너

array 배열 클래스
vector 벡터 클래스
deque Double ended queue. 양방향 큐(덱, 데큐, 데크)
forward_list 단방향 리스트
list 리스트(더블 링크드 리스트)

 

컨테이너 어답터

stack 스택 (Last In First Out, 후입 선출, 마지막에 들어온 것이 처음으로 나간다.) 한곳에서 들어오고 나가는 구조
queue 큐 (First In First Out, 선입 선출, 처음에 들어온 것이 처음으로 나간다.) 한쪽은 들어오고 한쪽은 나가는 구조
priority_queue 우선순위 큐

 

연관 컨테이너

set 집합
multiset 여러 키를 갖는 집합
map 맵 (사전형식 자료구조)
multimap 여러키를 갖는 맵

 

순서 없는 연관 컨테이너

unordered_set 순서없는 집합
unordered_multiset 순서없는 멀티키 집합
unordered_map 순서없는 맵
unordered_multimap 순서없는 멀티키 맵

 

'언어 > C++' 카테고리의 다른 글

[C++/STL] Set  (0) 2020.04.26
[C++/STL]벡터(vector)  (0) 2020.02.20
[C++/STL] 리스트(List)  (0) 2020.02.20

벡터

벡터는 크기가 변할수 있는 배열이다.

순차 컨테이너이다.

 

배열처럼 메모리에 연속하여 데이터를 할당하므로 인덱스로 접근이 가능하다.

배열과 다르게 크기가 커져 할당된 크기를 넘어서면 재할당하여 크기를 키운다.

 

다른 순차 컨테이너인 덱(deque), 리스트(list)와 비교해 벡터는 인덱스로 바로 접근하는게 빠르다.

벡터의 끝에 요소를 삽입, 삭제하는 것은 빠르지만 중간이나 앞 부분에 요소를 삽입, 삭제하는 것은 효율적이지 않다.

 

멤버함수

C++11에서 추가된 함수는 배경색을 칠했다.

 

생성자 벡터를 생성한다.
파괴자 벡터를 파괴한다.
operator= 객체를 할당한다.

Iterators

begin 첫번째 element를 가리키는 이터레이터를 반환한다.
end 마지막 element를 가리키는 이터레이터를 반환한다.
rbegin 마지막 element를 가리키는 역 이터레이터를 반환한다. 이터레이터를 증가시키면 역방향으로 그 다음 element를 가리킨다.
rend 첫번째 element를 가리키는 역 이터레이터를 반환한다.
cbegin 첫번째 element를 가리키는 const 이터레이터를 반환한다. 가리키는 객체의 값을 수정할 수 없다.
cend 마지막 element를 가리키는 const 이터레이터를 반환한다. 가리키는 객체의 값을 수정할 수 없다.
crbegin 마지막 element를 가리키는 const 역 이터레이터를 반환한다. 가리키는 객체의 값을 수정할 수 없다.
crend 첫번째 element를 가리키는 const 역 이터레이터를 반환한다. 가리키는 객체의 값을 수정할 수 없다.

Capacity

size 벡터의 크기를 반환한다.
max_size 벡터가 가질 수 있는 element의 최대 크기를 반환한다. 시스템이나 여러 요인에 달려있다.
resize 벡터의 크기를 변경한다. 기존보다 작은 값으로 변경하면 나머지 값들은 파괴된다.
capacity 메모리에 할당된 크기를 반환한다. 벡터의 요소 갯수와 할당된 값은 다를 수 있다.
empty 벡터가 비어있는지 확인한다.
reserve 벡터에 n개의 element를 수용할 수 있도록 요청한다.
shrink_to_fit 컨테이너에 속한 element의 수에 따라 재할당 하도록한다. 많이 할당된 경우 줄이기위해 사용한다.

Element access

operator[] element에 접근한다.
at element에 접근한다.
front 맨 앞의 element에 접근한다.
back 맨 뒤의 element에 접근한다.
data 벡터 내부에서 사용하는 array포인터를 반환한다.

Modifiers

assign 벡터에 값을 할당한다. 기존에 값이 있어도 완전 새로 할당된다.
push_back element를 끝에 추가한다.
pop_back 마지막 element를 제거한다.
insert element를 삽입한다. 인자로 iterator도 같이 넘긴다.
erase element를 제거한다.
swap 다른 벡터의 내용물과 자신의 내용물을 서로 바꾼다
clear 내부 element를 모두 제거한다.
emplace element를 생성 후 삽입한다. 인자로 iterator도 함께 넘긴다.
emplace_back element를 생성 후 맨 뒤에 삽입한다.

 

'언어 > C++' 카테고리의 다른 글

[C++/STL] Set  (0) 2020.04.26
[C++/STL] 컨테이너(Containers)  (0) 2020.02.21
[C++/STL] 리스트(List)  (0) 2020.02.20

리스트

리스트는 순차 컨테이너다.

삽입과 삭제하는데 걸리는 시간이 상수시간만큼 걸린다.

더블 링크드 리스트로 구현되어 있어서 양방향 순회가 가능하다.

 

벡터와 덱, 배열과 비교하면 삽입, 삭제, 요소 이동에 장점을 가지고 있고

직접 접근할 수 없는 것이 단점이다. 접근하는 데 선형 시간이 걸린다.

 

 

멤버함수

C++11에서 추가된 함수는 배경색을 칠했다.

생성자  리스트 객체를 생성한다.
파괴자  리스트 객체를 파괴한다.
operator= 객체를 할당한다.

Iterators

begin 첫번째 요소를 가리키는 이터레이터를 반환한다. 이터레이터를 증가시키면 다음 요소를 가리키게 된다.
end 마지막 요소를 가리키는 이터레이터를 반환한다. 
rbegin 마지막 요소를 가리키는 역 이터레이터를 반환한다. 이터레이터를 증가시키면 시작위치에 가까운 그 다음 요소를 가리키게 된다.
rend 첫번째 요소를 가리키는 역 이터레이터를 반환한다. 
cbegin 첫번째 요소를 가리키는 const 이터레이터를 반환한다. 가리키는 객체의 값은 수정이 불가하다.
cend 마지막 요소를 가리키는 const 이터레이터를 반환한다. 가리키는 객체의 값은 수정이 불가하다.
crbegin 첫번째 요소를 가리키는 const 역(reverse) 이터레이터를 반환한다.  가리키는 객체의 값은 수정이 불가하다.
crend 마지막 요소를 가리키는 const 역(reverse) 이터레이터를 반환한다.  가리키는 객체의 값은 수정이 불가하다.

Capacity

empty 컨테이너가 비어있는지 확인한다.
size 크기를 반환한다
max_size 최대 크기를 반환한다

Element access

front 첫번째 요소에 접근한다.
back 마지막 요소에 접근한다.

Modifiers

assign 컨테이너에 새로운 내용을 할당한다. 새로 쓰여진다.
emplace_front 요소를 생성하고 맨 앞에 삽입한다.
push_front 맨 앞에 요소를 삽입한다.
pop_front 맨 앞 요소를 제거한다.
emplace_back 요소를 생성하고 맨 뒤에 삽입한다.
push_back 맨 뒤에 요소를 삽입한다.
pop_back 맨 뒤 요소를 제거한다.
insert 요소를 삽입한다.
erase 요소를 제거한다
swap 리스트를 다른 리스트와 바꾼다
resize 크기를 변경한다.
clear 리스트 내부 요소를 전부 제거한다.
emplace 생성 후 요소를 삽입한다.

Operations

splice 리스트에서 리스트로 요소를 옮긴다
remove 값으로 요소를 제거한다. 입력된 값과 같은 요소는 모두 제거된다.
remove_if 조건에 맞는 요소를 제거한다. 조건은 함수나 클래스로 만들어질 수 있다.
unique 중복되는 값을 제거한다.
merge 정렬된 리스트를 병합. 정렬하여 병합된다. 
sort 내부 요소를 정렬한다.
reverse 요소의 순서를 뒤집는다.

 

'언어 > C++' 카테고리의 다른 글

[C++/STL] Set  (0) 2020.04.26
[C++/STL] 컨테이너(Containers)  (0) 2020.02.21
[C++/STL]벡터(vector)  (0) 2020.02.20

+ Recent posts

티스토리툴바