VECTOR

#define cstl_vector(T) new_vector(T)

VECTOR는 크기가 동적으로 변하는 시퀀스 컨테이너로, C++ STL의 std::vector에 대응됩니다. 요소는 메모리에 연속적으로(contiguously) 저장되며, 일반 포인터로 접근할 수 있습니다. 즉 반복자(iterator)뿐 아니라 포인터 산술로 요소에 접근할 수 있으며, 배열 첨자 연산자 []도 그대로 동작합니다.

저장 공간은 자동으로 관리되며, 필요에 따라 확장·축소됩니다. 벡터는 일반적으로 할당된 저장 공간이 실제 크기보다 더 크며, 이는 요소가 추가될 때마다 재할당이 일어나지 않도록 하기 위함입니다. 용량은 capacity()로 조회할 수 있습니다.

복잡도: 끝(back)에서의 삽입/제거는 분할 상환 상수 시간 O(1), 중간에서의 삽입/제거는 선형 시간 O(n), 요소 접근은 상수 시간 O(1)입니다.

Functions

생성/소멸/대입

Function	설명
new_vector(T)	T 타입의 새로운 벡터 생성
destroy	컨테이너 소멸자
assign	벡터에 새 값을 대입

Element access

Function	설명
v[i]	첨자 연산자 — n번째 요소에 접근 (경계 검사 없음)

Iterator

Function	설명
begin	시작 반복자를 반환
end	끝(past-the-end) 반복자를 반환
rbegin	역방향 시작 반복자를 반환
rend	역방향 끝 반복자를 반환
next	반복자를 한 칸 전진
prev	반복자를 한 칸 후퇴

Capacity

Function	설명
size	요소 개수를 반환
max_size	담을 수 있는 최대 요소 수를 반환
capacity	현재 할당된 저장 용량을 반환
reserve	저장 용량을 최소 n개 이상으로 확보
shrink_to_fit	용량을 크기(size)에 맞게 축소

Modifiers

Function	설명
clear	모든 요소를 제거
insert	지정 위치에 요소를 삽입
erase	지정 범위의 요소를 제거
push_back	끝에 요소를 추가
pop_back	마지막 요소를 제거
resize	요소 개수를 n으로 변경

탐색

Function	설명
find	지정한 요소를 검색

Member function details

Note

VECTOR, new_vector

VECTOR(int) v = new_vector(int);

요소 타입이 TYPE인 빈 벡터를 생성합니다. 반환값은 TYPE*로, 컨테이너 변수에 직접 대입해서 사용합니다.

Parameters

Parameter	설명
T	저장할 요소의 타입 (예: int, double, 구조체 등)

Complexity

O(1)

Example

VECTOR(int) v = new_vector(int);
VECTOR(double) v2 = new_vector(double);

Note

destroy

void destroy(v);

벡터가 소유한 모든 메모리를 해제하고 포인터를 NULL로 설정합니다. 더 이상 사용하지 않는 벡터는 반드시 이 함수로 해제해야 메모리 누수를 방지할 수 있습니다.

Complexity

O(1)

Example

VECTOR(int) v = new_vector(int);
// v 사용
destroy(v); // free가 아닌 destroy를 사용해야 합니다.

Note

assign

void assign(CTL, size_t n);                // 모든 값을 0으로 채움
void assign(CTL, size_t n, <TYPE> value);  // 모든 값을 지정한 값으로 채움

벡터의 기존 내용을 대체하여, 값 value로 채워진 n개의 요소를 가지도록 합니다. 필요하면 용량이 재할당됩니다.

Parameters

Parameter	설명
n	할당할 요소의 개수
value	각 요소에 채울 값. 생략 시 0으로 초기화

Complexity

O(n)

Example

VECTOR(int) v = new_vector(int);
assign(v, 5, 42);
// v = {42, 42, 42, 42, 42}

Note

begin, end

iterator begin(v);
iterator end(v);

begin은 첫 번째 요소를 가리키는 반복자를, end는 마지막 요소의 다음 위치(past-the-end)를 가리키는 반복자를 반환합니다. 벡터가 비어 있으면 begin == end입니다.

Complexity

O(1)

Example

VECTOR(int) v = new_vector(int);
for (int i = 0; i < 10; i++) push_back(v, i);

for (int* it = begin(v); it != end(v); it++) {
    printf("%d ", *it);
}

Note

rbegin, rend

reverse_iterator rbegin(v);
reverse_iterator rend(v);

역방향 순회용 반복자를 반환합니다. rbegin은 마지막 요소를, rend는 첫 번째 요소의 한 칸 앞을 가리킵니다.

Warning

rend는 유효한 메모리 영역을 벗어난 위치(begin - 1)를 가리키므로 역참조하면 안 됩니다. 루프 종료 조건으로만 사용하세요.

Complexity

O(1)

Example

VECTOR(int) v = new_vector(int);
for (int i = 0; i < 10; i++) push_back(v, i);

for (int* it = rbegin(v); it != rend(v); it = prev(it, sizeof(int))) {
    printf("%d ", *it);
}

Note

next, prev

iterator next(it, size_t type_size);
iterator prev(it, size_t type_size);

반복자를 한 칸 전진시키거나 후퇴시킵니다. 벡터의 요소는 연속적이므로 it + 1, it - 1과 동등하게 사용할 수 있습니다.

Complexity

O(1)

Example

VECTOR(int) v = new_vector(int);
push_back(v, 10);
push_back(v, 20);

int* it = begin(v);
it = next(it, sizeof(int)); // 두 번째 요소로 이동
printf("%d\n", *it);        // 20

Note

size

size_type size(v);

벡터가 현재 저장하고 있는 요소의 개수를 반환합니다.

Complexity

O(1)

Example

VECTOR(int) v = new_vector(int);
push_back(v, 1);
push_back(v, 2);
printf("%zu\n", size(v)); // 2

Note

max_size

size_type max_size(v);

벡터가 시스템·라이브러리 제약 하에서 담을 수 있는 요소의 이론적 최댓값(INT_MAX)을 반환합니다.

Complexity

O(1)

Example

VECTOR(int) v = new_vector(int);
printf("%zu\n", max_size(v));

Note

capacity

size_type capacity(v);

재할당 없이 저장할 수 있는 요소의 최대 개수, 즉 현재 할당된 저장 공간의 크기를 반환합니다. 항상 size() <= capacity()입니다.

Complexity

O(1)

Example

VECTOR(int) v = new_vector(int);
reserve(v, 100);
printf("%zu\n", capacity(v)); // 100

Note

reserve

void reserve(v, size_t n);

용량을 최소 n개 이상으로 확보합니다. 현재 용량이 n보다 크거나 같으면 아무 일도 하지 않습니다.

Parameters

Parameter	설명
n	확보할 최소 용량

Complexity

O(n) (재할당이 발생하는 경우)

Example

VECTOR(int) v = new_vector(int);
reserve(v, 1000);
// 이후 1000번의 push_back 에서 재할당이 발생하지 않음

Note

shrink_to_fit

void shrink_to_fit(v);

용량을 현재 크기(size)에 맞게 줄입니다. 이후 capacity() == size()가 됩니다. 벡터가 비어 있을 경우 용량은 1로 설정됩니다.

Complexity

O(size)

Example

VECTOR(int) v = new_vector(int);
reserve(v, 1000);
push_back(v, 1);
shrink_to_fit(v);
printf("%zu\n", capacity(v)); // 1

Note

clear

void clear(v);

벡터에서 모든 요소를 제거합니다. 크기는 0이 되지만 용량은 변경되지 않습니다. 용량까지 해제하려면 이후에 shrink_to_fit을 호출하거나 destroy를 사용하세요.

Complexity

O(1)

Example

VECTOR(int) v = new_vector(int);
push_back(v, 1);
push_back(v, 2);
clear(v);
printf("%zu\n", size(v)); // 0

Note

insert

void insert(v, iterator pos, size_t n, <TYPE> value);

pos 위치에 값 value를 n번 복사하여 삽입합니다. 기존 요소들은 뒤로 밀립니다.

Parameters

Parameter	설명
pos	삽입 위치를 가리키는 반복자
n	삽입할 요소의 개수
value	삽입할 값

Warning

재할당이 발생하거나 pos 이후 요소가 이동하므로, 호출 이후 기존 반복자는 무효화됩니다.

Complexity

O(n + size - pos)

Example

VECTOR(int) v = new_vector(int);
for (int i = 0; i < 5; i++) push_back(v, i); // 0 1 2 3 4
insert(v, begin(v) + 2, 3, 99);
// v = {0, 1, 99, 99, 99, 2, 3, 4}

Note

erase

void erase(v, iterator first, iterator last);

구간 [first, last)에 해당하는 요소들을 제거합니다. 이후 요소들은 앞으로 당겨집니다.

Parameters

Parameter	설명
first	제거 구간의 시작 반복자
last	제거 구간의 끝 반복자 (제외)

Complexity

O(size - first)

Example

VECTOR(int) v = new_vector(int);
for (int i = 0; i < 5; i++) push_back(v, i); // 0 1 2 3 4
erase(v, begin(v) + 1, begin(v) + 3);
// v = {0, 3, 4}

Note

push_back

void push_back(v, <TYPE> value);

벡터의 끝에 값을 추가합니다. 용량이 부족하면 자동으로 두 배로 확장됩니다 (exponential growth).

Complexity

분할 상환 상수 — amortized O(1)

Example

VECTOR(int) v = new_vector(int);
for (int i = 0; i < 10; i++) {
    push_back(v, i);
}

Note

pop_back

void pop_back(v);

벡터의 마지막 요소를 제거합니다.

Warning

빈 벡터에서 호출할 경우 에러가 발생합니다.

Complexity

O(1)

Example

VECTOR(int) v = new_vector(int);
push_back(v, 1);
push_back(v, 2);
pop_back(v);
printf("%zu\n", size(v)); // 1

Note

resize

void resize(v, size_t n);                 // 증가분은 0으로 채움
void resize(v, size_t n, <TYPE> value);   // 증가분은 value로 채움

벡터의 크기를 정확히 n개로 변경합니다.

현재 크기보다 작으면 뒤에서부터 요소가 제거됩니다.
현재 크기보다 크면 value로 채워진 요소가 뒤에 추가됩니다. value가 생략되면 0으로 채워집니다.

Parameters

Parameter	설명
n	변경할 크기
value	증가분을 채울 값 (선택)

Complexity

O(|n - size|)

Example

VECTOR(int) v = new_vector(int);
for (int i = 0; i < 3; i++) push_back(v, i); // 0 1 2
resize(v, 5, 99);
// v = {0, 1, 2, 99, 99}

Note

find

iterator find(v, iterator first, <TYPE> value);

first부터 시작해 value와 memcmp 기준으로 일치하는 첫 번째 요소의 반복자를 반환합니다. 찾지 못하면 NULL을 반환합니다.

Warning

비교는 바이트 단위(memcmp)로 수행됩니다. 구조체에 패딩이 있을 경우 예기치 않은 결과가 나올 수 있으니, memset으로 초기화하여 사용하세요.

Complexity

O(size - first)

Example

VECTOR(int) v = new_vector(int);
for (int i = 0; i < 10; i++) push_back(v, i * i);

int target = 25;
int* pos = find(v, begin(v), target);
if (pos != NULL) {
    printf("found %d at index %td\n", *pos, pos - v);
}

OpenCSTL Wiki

Home
- Container library
  - Sequential Containers
    - VECTOR
    - DEQUE
    - LIST
  - Associative Containers
    - SET
    - MAP
  - Unordered Containers
    - UNORDERED_SET
    - UNORDERED_MAP
- Sorting Algorithm
- Logging library

VECTOR

VECTOR

#define cstl_vector(T) new_vector(T)

Functions

생성/소멸/대입

Element access

Iterator

Capacity

Modifiers

탐색

Member function details

Parameters

Complexity

Example

Complexity

Example

Parameters

Complexity

Example

Complexity

Example

Complexity

Example

Complexity

Example

Complexity

Example

Complexity

Example

Complexity

Example

Parameters

Complexity

Example

Complexity

Example

Complexity

Example

Parameters

Complexity

Example

Parameters

Complexity

Example

Complexity

Example

Complexity

Example

Parameters

Complexity

Example

Complexity

Example

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

OpenCSTL Wiki

Clone this wiki locally