vector

https://www.aladin.co.kr/shop/wproduct.aspx?ItemId=257288899

코딩 테스트를 위한 자료 구조와 알고리즘 with C++

본 책을 사용하여 공부하는 내용이고 해당 글은 상업적으로 배포하고자 하지 않고 개인 공부용입니다

 

array의 단점이라면

• array의 크기가 컴파일 시간에 결정되는 상수로, 프로그램 실행 중에는 변경할 수 없음
• 크기가 고정되어 있어서 원소를 추가하거나 삭제할 수 없음
• 메모리의 할당 방법을 변경할 수 없이 stack 메모리를 사용해야 함

vector는 근본적으로 array의 단점이었던 고정 크기의 문제를 해결하여 초기화 과정에 데이터의 크기를 제공하지 않음

 

#include <iostream>
# include<vector>

int main()
{
    std::vector<int> vec1 = { 1,2,3,4,5 };
// ㄴ 초기화
    std::vector<int> vec;
    std::vector<int> vec2(10);
// ㄴ 선언 
// 위의 것은 크기가 0임, 물론 그렇다고 용량이 0인것은 아니지만
    std::vector<int> vec3(10, 5);
// ㄴ 크기는 10, 모든 원소는 5
}

 

• 벡터에 새로운 원소를 추가하려면 push_back( ) 또는 insert( )를 사용함
• push_back은 맨 마지막에 새로운 원소를 추가, insert는 삽입할 위치를 나타내는 반복자를 첫 인자로 받음으로써 원하는 위치에 원소를 추가할 수 있음

push_back(val):
    if size < capacity         // 새 원소를 추가할 공간이 있는 경우
        - 마지막 원소 다음에 val 저장
        - 벡터 크기를 1만큼 증가
        - return;
    
    if vector is already full  // 할당된 메모리 공간이 가득 차 있는 경우
        - 2*size 크기의 메모리를 새로 할당
        - 새로 할당한 메모리로 기존 원소 전부를 복사/이동
        - 데이터 포인터를 새로 할당한 메모리 주소로 지정
        - 마지막 원소 다음에 val을 저장하고, 벡터 크기를 1만큼 증가

 

• 따라서 맨 뒤에 원소를 삽입하는데, 남은 공간이 있다면 O(1)의 시간이 걸림
• 그런데 충분하지 않으면 모든 원소를 새로운 공간을 할당받아서 복사/이동해야 하며, 이때는 O(n)의 시간이 걸림
• 대부분 용량이 부족한 상황이 오면 기존 용량의 두 배로 늘려서 작동하고 사실 이런 경우는 n개의 원소를 추가하는 경우에 발생함
• 그러니까 꽉 찬 상태에서 겨우 한 두개 삽입하는 일이 없다는 뜻
• 따라서 평균적인 push_back의 시간 복잡조는 O(1)에 가까움, 그래서 매우 빠르게 동작한다고 말할 수 있고 이것이 벡터를 많이 사용하는 이유임

 

• insert는 지정된 위치에 값을 삽입하기 때문에 모든 원소를 이동시키는 연산이 필요함
• 따라서 필요한 경우 종종 메모리를 새롭게 할당하기도 하고 이 경우는 O(n)의 시간이 걸림
• 왜? 앞에꺼는 안건드려도 되지 않나, 들어간 위치 뒤에부터만 새로 할당하는게 아닌가
• 맨 앞에 추가하고 싶다면 push_front() 아니고 insert로 인자를 맨 앞 위치로 해야함

std::vector<int> vec;          // 비어 있는 벡터 생성: {}

vec.push_back(1);              // 맨 뒤에 1 추가: {1}

vec.push_back(2);              // 맨 뒤에 2 추가: {1, 2}

vec.insert(vec.begin(), 0);    // 맨 앞에 0 추가: {0, 1, 2}

vec.insert(find(vec.begin(), vec.end(), 1), 4); // 1 앞에 4 추가: {0, 4, 1, 2}

 

• begin을 사용해서 이 역시 메모리 공간으로 접근하는 멤버함수로 생각함
• 한편, push_back과 insert는 함수가 추가할 원소를 먼저 임시로 생성한 후 해당 위치로 복사 또는 이동을 수행하기 때문에 공간 최적화를 위해서 emplace_back() 또는 emplace()를 사용함
• 아마 그리고 문맥상 push_back -> emplace_back ?

 

• 원소 제거를 위해 pop_back과 erase 함수를 제공할 것이고, 역시 맨 마지막을 제거하고 벡터의 크기를 1만큼 줄이는 것과
• erase에서 (두가지 형태로 오버로딩)
• 반복자 하나를 인자로 받아 해당 위치 원소를 제거하거나
• 범위의 시작과 끝을 나타내는 반복자를 받아 시작부터 끝 바로 앞 원소까지 제거하는 것이 있음 (끝 원소는 제거 안됨)
• 역시나 pop back은 O(1), erase는 O(n)의 시간복잡도를 가짐

std::vector<int> vec = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

// 맨 마지막 원소 하나를 제거합니다: {0, 1, 2, 3, 4, 5, 6, 7, 8}
vec.pop_back();

// 맨 처음 원소를 제거합니다: {1, 2, 3, 4, 5, 6, 7, 8}
vec.erase(vec.begin());

// 1번째 원소부터 4번째 앞 원소까지 제거합니다: {1, 5, 6, 7, 8}
vec.erase(vec.begin() + 1, vec.begin() + 4);

 

• 또, 몇가지 유용한 멤버함수로는
• clear() -> 공벡터로 만듬, 원소제거
• reserve(capacity) 벡터에서 사용할 용량을 지정함 : 크면 재할당, 같거나 작으면 동작 안함, 벡터의 크기는 변경 안함
•  shrink_to_fit() 여분의 메모리 공간을 해제하는 용도로 사용되어 벡터의 용량과 벡터의 크기를 같게 설정함-> 벡터가 더이상 사용되지 않을 때 유용

std::vector<int> myVector;

    // Adding elements to the vector
    for (int i = 0; i < 10; ++i) {
        myVector.push_back(i);
        std::cout << "Size: " << myVector.size() << ", Capacity: " << myVector.capacity() << std::endl;
    }

    return 0;

한편, 벡터의 용량과 크기에 대해서 

용량은 추가적인 메모리 할당 없이 저장 가능한 요소의 총 수를 나타내고 항상 용량>=크기임

요소가 추가되어 용량이 초과되면 벡터는 추가 요소를 수용하기 위해 메모리를 더 할당함

보통 용량은 효율적인 크기 조정을 위해 크기보다 크게 유지되며 메모리 재할당의 빈도를 줄임

 

크기는 벡터에 현재 저장된 요소의 수를 나타내고 삽입된 요소의 실제 수임

 

---

참고 시간복잡도에 대한 설명