VECTOR

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);
}

---