STL::vector, itr, list, deque

강한친구·2022년 3월 6일

C / CPP

목록 보기

12/19

표준 템플릿 라이브러리

cpp의 표준 라이브러리에는 iostream, chrono, regex등 다양한 라이브러리들이 있고 이들은 매우 유용하지만, 보통 STL이라 한다면,

임의 타입의 객체를 보관할 수 있는 컨테이너 (container)
컨테이너에 보관된 원소에 접근할 수 있는 반복자 (iterator)
반복자들을 가지고 일련의 작업을 수행하는 알고리즘 (algorithm)

들을 의미한다.

STL Container Vector

cpp로 알고리즘문제를 풀이들을 보면 반드시 존재하는 그 것이다. 가변길이를 가진 배열이라고도 생각하면 되는데, 쉽게 이해하자면 python의 list와 같은 기능을 한다고 생각하면 된다.

STL::vector의 시간복잡도

vector의 경우 특정 위치에 접근할 때, O(1)의 시간이 소요된다. 원소를 추가 혹은 제거하는 작업 역시 O(1)이 소요되는데 정확히는 이는 amotized O(1)이다.

Amotized란 분활상환이라는 뜻이다. 이는 대략적으로 1이지만 가끔 O(n)이 발생한다는 의미인데, vecotr의 경우 이전의 코드에서 보았던것처럼 capacity를 2배로 잡고 시작한다. 만약 이 capacity가 가득차면 메모리를 파괴하고 2배 더 늘린 공간에 쓰게 된다. 이 때 O(n)만큼의 시간이 소요되는 것이다.

다만 임의의 위치에 원소를 추가 혹은 제거하는것은 O(n)이 걸린다. 이는 새롱누 원소를 추가하거나 뺼 때, 원소를 복사이동 해야하기 때문이다.

iterator

반복자는 컨테이너 원소에 접근 할 수 있는 포인터와 비슷한것이다. (자바에도 있다) vector에서 우리는 배열처럼 [ ] 을 이용해서 접근하지만, 실제로는 이 iterator를 통해서 접근할 수 있다.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec;
    vec.push_back(1);
    vec.push_back(2);
    vec.push_back(3);
    vec.push_back(4);

    for (std::vector<int>::iterator itr = vec.begin(); itr != vec.end(); itr++) {
        std::cout << *itr << std::endl;
    }
}

보통은

for (int i = 0; i < vec.size(); i++)

처럼 쓰겠지만 itr로도 가능하다 (대신 포인터이기 떄문에 값을 보려면 *을 써줘야한다.)

range based for loop

피이썬에서는 포문을

for i in range(n):
# index 

for i in array:
# element

이런식으로 작성한다.

c에서도 이와 유사하게 꾸밀 수 있는데 다음과 같다.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec;
    vec.push_back(1);
    vec.push_back(2);
    vec.push_back(3);
    vec.push_back(4);

    for (int elem : vec) {
    	std::cout << "element : <, elem << std::endl;
    }
}

혹은 레퍼런스로 받을려면 이런식으로 작성할 수 있다.

#include <iostream>
#include <vector>

template <typename T>
void normal_vector(std::vector<T>& vec) {
    for (typename std::vector<T>::iterator itr = vec.begin(); itr != vec.end();
        ++itr) {
        std::cout << *itr << std::endl;
    }
}

template <typename T>
void range_based(std::vector<T>& vec) {
    for (const auto& elem : vec) {
        std::cout << elem << std::endl;
    }
}

int main() {
    std::vector<int> vec;
    vec.push_back(1);
    vec.push_back(2);
    vec.push_back(3);
    vec.push_back(4);

    std::cout << "print_vector" << std::endl;
    normal_vector(vec);
    std::cout << "print_vector_range_based" << std::endl;
    range_based(vec);

    return 0;
}

const auto는 이 글을 참고하자

list

리스트는 파이썬이나 자바에서 자주 써봐서 많이들 알 것이라 생각하지만 엄연히 자료구조중 하나이긴하다.

자신의 전, 후 노드를 포인터로 가르키고 있는 자료구조이다. 따라서 바로 접근할 수는 없지만 삭제 및 추가시 포인터만 수정하면 그만이라 정말 빠른 자료구조이다.

탐색 O(n)
삭제 삽입 O(1)

#include <iostream>
#include <list>

int main() {
    std::list<int> lst;

    lst.push_back(1);
    lst.push_back(2);
    lst.push_back(3);
    lst.push_back(4);

    for (std::list<int>::iterator itr = lst.begin(); itr != lst.end(); ++itr) {
        std::cout << *itr << std::endl;
    }
}