알고리즘 라이브러리 정리
Vector 벡터 라이브러리
vector 컨테이너는 대표적인 시퀀스 컨테이너로 배열과 비슷하여 사용이 쉬우며 자주 사용된다. vector는 임의 접근 반복자(Random Access Iterator)를 지원하는 배열 기반 컨테이너이다. vector의 가장 큰 특징 중 하나는 원소가 하나의 메모리 블록에 연속하게 저장된다는 것이다. 그렇다 보니 원소가 추가되거나 삽입될 때 메모리 재할당이 발생할 수 있고 상당한 비용을 지불하게 된다. 그래서 메모리 할당 크기를 알 수 있게 capacity() 함수를 제공하며 한번에 메모리를 할당할 수 있는 reserve() 함수도 제공된다. 원소가 연속하게 저장되므로 [] 연산자 또는 at 으로 읽기에는 빠르지만 insert(), erase(), push_back() 등은 비효율적으로 동작한다.
템플릿 형식 | |
template<typename T, typename Allocator = allocator<T>> class vector |
T는 vector 컨테이너 원소의 형식 |
생성자 |
|
vector v |
v는 빈 컨테이너이다. |
vector v(n) |
v는 기본값으로 초기화된 n개의 원소를 갖는다. |
vector v(n,x) |
v는 x 값으로 초기화된 n개의 원소를 갖는다. |
vector v(v2) |
v는 v2 컨테이너의 복사본이다.(복사 생성자 호출) |
vector v(b,e) |
v는 반복자 구간 [b,e)로 초기화된 원소를 갖는다. |
멤버함수 |
|
v.assign(n,x) |
v에 x 값으로 n개의 원소를 할당한다. |
v.assign(b,e) |
v를 반복자 구간 [b,e)로 할당한다. |
v.at(i) |
v의 i번째 원소를 참조한다. |
v.back() |
v의 마지막 원소를 참조한다. |
p=v.begin() |
p는 v의 첫 원소를 가리키는 반복자 |
x=v.capacity() |
x는 v에 할당된 공간의 크기 |
v.clear() |
v의 모든 원소를 제거한다. |
v.empty() |
v가 비었는지 조사한다. |
p=v.end() |
p는 v의 끝을 표식하는 반복자 |
p=v.erase(pp) | p가 가리키는 원소를 제거한다. q는 다음 원소를 가리킨다. |
q=v.erase(b,e) | 반복자 구간 [b,e)의 모든 원소를 제거한다. q는 다음 원소 |
v.front() | v의 첫 번째 원소를 참조한다. |
q=v.insert(p,x) | p가 가리키는 위치에 x 값을 삽입한다. q는 삽입한 원소를 가리키는 반복자다. |
v.insert(p,n,x) | p가 가리키는 위치에 n개의 x 값을 삽입한다. |
v.insert(p,b,e) | p가 가리키는 위치에 반복자 구간 [b,e)의 원소를 삽입한다. |
x=v.max_size() | x는 v가 담을 수 있는 최대 원소의 개수(메모리의 크기) |
v.pop_back() | v의 마지막 원소를 제거한다. |
v.push_back() | v의 끝에 x를 추가한다. |
p=v.rbegin() | p는 v의 역 순차열의 첫 원소를 가리키는 반복자다. |
p=v.rend() | p는 v의 역 순차열의 끝을 표식하는 반복자 |
v.reserve(n) | n개의 원소를 저장할 공간을 예약한다. |
v.resize(n) | v의 크기를 n으로 변경하고 확장되는 공간의 값을 기본값으로 초기화 한다. |
v.resize(n,x) | v의 크기를 n으로 변경하고 확장되는 공간의 값을 x 값으로 초기화한다. |
v.size() | v의 원소 갯수 |
v.swap(v2) | v와 v2를 swap한다. |
연산자 |
|
v1==v2 |
v1과 v2의 모든 원소가 같은가? (bool) |
v1!=v2 |
v1과 v2의 모든 원소 중 하나라도 다른 원소가 있는가? |
v1<v2 |
문자열 비교처럼 v2가 v1보다 큰가? |
v1>v2 |
문자열 비교처럼 v1이 v2보다 큰가? |
v[i] |
v의 i번째 원소를 참조한다. |
멤버 형식 |
|
allocator_type |
메모리 관리자 형식 |
const_iterator |
const 반복자 형식 |
const_pointer |
const value_type* 형식 |
const_reference |
const value_type& 형식 |
const_reverse_iterator |
const 역 반복자 형식 |
difference_type |
두 반복자 차이의 형식 |
iterator |
반복자 형식 |
pointer |
value_type* 형식 |
reference |
value_type& 형식 |
reverse_iterator | 역 반복자 형식 |
size_type | 첨자(index)나 원소의 개수 등의 형식 |
value_type | 원소의 형식 |
Vector
벡터는 앞쪽이 막혀있는 구조로, FILO스택구조와 비슷하다고 생각하면 된다. 즉, 원소 제거는 맨 마지막에 넣은 것과 빼는 것만 가능하다.
(ex: vec.push_back(); vec.pop_back();)
추가
push_back(element)
: end에 요소를 추가insert(v.begin()+3, element)
: 3번째 인덱스에 요소를 추가, 그 뒤의 요소는 뒤로 밀림
삭제
pop_back()
: end에 있는 요소를 삭제 q = erase(v.begin()+3) : 3번째 인덱스의 요소 삭제, q는 다음번 요소를 가리킴 clear() : 벡터의 모든 요소 삭제
조회
at(index)
: index에 있는 요소를 반환begin(), end()
: 각각 첫 번째와 마지막 포인터 반환
기타
empty()
: 벡터가 비어있으면 true 아니면 false를 반환size()
: 벡터 사이즈를 반환
stack
추가 및 삭제
push(element)
: top에 요소를 추가pop()
: top에 있는 요소를 삭제
조회
top()
: top(스택의 처음이 아닌 가장 끝)에 있는 요소를 반환
기타
empty()
: 스택이 비어있으면 true 아니면 false를 반환size()
: 스택 사이즈를 반환
vector와 stack 멤머 함수 차이
- Vector와 Stack 함수 차이