C++ STL

공팡팡·2024년 9월 29일

C++

목록 보기
2/4

C++이 강력하고 인기가 많은 이유중 하나는 어떤 특별한 라이브러리의 존재 때문이라고 해도 과언이 아니다.

C++의 표준 라이브러리. 그 중 템플릿 라이브러리에는 크게 3가지가 존재한다.

  • Container
  • Iterator
  • Algorithm

오늘은 이 3개의 키워드를 중심으로 STL라이브러리를 살펴보려고 한다.

Container

컨테이너에는 크게 시퀀스 컨테이너와 연관 컨테이너가 존재한다.

Sequence Container

  • Vector(Iterator)
  • List
  • Deque

시퀀스 컨테이너의 특징으로는 array처럼 객체들을 순차적으로 보관한다.

각각의 예시코드들을 살펴보며 알아보자.

Vector

int main()
{
    std::vector<int> vec;
    vec.push_back(10);
    vec.push_back(20);
    vec.push_back(30);
    vec.push_back(40);
    vec.push_back(50);

    for(vector<int>::size_type i=0;i<vec.size();i++)
    {//int i와 비슷하지만 type안정성때문에 size_type을 쓰는것이 권장된다.
        std::cout<<vec[i]<<std::endl;
    }
}

해당 코드만으로 vector의 사용처에 대해 알 것이라고 생각한다.

Iterator

int main()
{
    std::vector<int> vec;
    vec.push_back(10);
    vec.push_back(20);
    vec.push_back(30);
    vec.push_back(40);
    vec.push_back(50);

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

iterator는 어떻게 보면 컨테이너를 가리키는 포인터라고 할 수 있다. 다만 그게 객체형으로 되어있어 곧바로 뽑아낼 수 있는 것이 특징이다. vec.begin()과 vec.end()등의 함수를 통해 iterator의 위치를 옮길 수 있다.

iterator는 포인터 연산자를 이용해 자신이 가리키는 컨테이너 요소에 접근하게 해야 해당 요소를 참조할 수 있다.

cout<<*itr이 동작하지 않는 이유도 이것이다.

포인터를 사용하면 객체에 담겨있는 어느 요소를 가리키게 되지만, cout<<itr을 하게 되면 객체 자체를 출력하라는 오류를 만나게 된다.

사용방법은 위의 코드처럼 vector<int>::iterator 변수명으로 선언하면 된다. 특이한 특징으로는 vec.end(), 즉 벡터의 끝자락은 빈 벡터라는 것이다. string에서 마지막 글자가 null이라는 것과 유사하다. 때문에 끝에 있는 벡터의 인덱스를 뽑아오려면 vec.end-1을 해야 해당 위치를 알 수 있을 것이다.

  • 곧바로 vec().end를 접근하게 되면 iterator부분에서 오류가 나는 것을 확인할 수 있음.

vec.insert, vec.erase도 자주 사용하는 함수이니 익숙하지 않다면 한번 써보는 것을 추천한다.

List

리스트는 양방향 구조를 가지고 있다. 자료구조에서 봤던 연결리스트가 바로 이 리스트를 가리킨다.

연결리스트의 특징상 각각의 원소가 다음 원소를 가리키고 있기 때문에 곧바로 어떠한 원소에 접근하는 것은 불가능하다.

곧바로 접근 가능한 원소는 begin()과 end()에 있는 원소 뿐이다.

#include <iostream>
#include <list>

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

  lst.push_back(10);
  lst.push_back(20);
  lst.push_back(30);
  lst.push_back(40);

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

vector처럼 iterator를 통해 컨테이너 안의 요소를 접근할 수 있다. 단, 앞서 언급했던 것 처럼 임의의 요소를 직접적으로 접근하는 것은 불가능하기에, itr+3과 같은 접근은 허용하지 않는다. 단 increment,decrement(++,--)는 허용한다.

만약 특정원소, 예를 들어 30을 찾고 삭제하려면 vector처럼 erase(vec.begin()+3)이 허용되지 않는다. 원소의 위치를 찾고 삭제하는 과정이 필요하다.

for (std::list<int>::iterator itr = lst.begin(); itr != lst.end(); ++itr) {
  if (*itr == 30) {
    lst.erase(itr);
    break;
  }
}

Deque

덱은 벡터처럼 임의의원소 접근, 추가, 삭제의 소요시간에 O(n)이 소요된다. 그러나 속도는 벡터보다 빠르다.

단, 해당 원소들을 보관하고 있는 메모리들이 연속적으로 배치되어 있지 않기에, 추가적인 메모리를 필요로 하는 단점을 지니고 있다.

즉 실행속도는 빠르나 메모리 소모는 크다.

좀 더 깊게 들어가보면, 할당된 메모리가 가득찬 벡터가 있다고 해보자. 이 vector는 6개의 공간이 가득 차 있는데, vector.push_back(7);을 하게 될 경우 해당 벡터에서 공간을 추가해버리는게 아닌, 아예 새로운 벡터를 만들어 버리고 그 공간에 할당을 해버린다.

즉 많은 시간이 소요된다는 것이다.

이와 다르게, 덱은 별도의 메모리에 새로운 블록을 만들어 원소를 넣어버리고 같은 덱인 척을 한다.

즉 1번 메모리에 1~5의 숫자가 들어있고, 6의 숫자가 새로 들어오면 2번 메모리에 6을 넣고 같은 공간인 척을 해버린다. 때문에 메모리는 많이 잡아먹으나, 속도면에서 우위를 보이는 것이다.

이론은 여기까지하고, 사용방법은 아래와 같다.

void print_deque(std::deque<int> &dq){
    std::cout << "[ ";
    for (std::deque<int>::size_type i=0;i<dq.size();i++) {
        std::cout << dq[i] << " ";
    }
    std::cout << " ] " << std::endl;
}

덱또한 iterator를 사용해 출력하기 어렵지 않음을 알 수 있다.

추가적으로 auto를 사용하여 출력하는 문장도 살펴보고가자.

for (const auto& elem : dq) {
    std::cout << elem << " ";
  }

auto는 해당 타입을 컴파일러가 유추하여 표현한다. 예를들어 숫자가 1,2,3,4타입의 경우 자동적으로 int로 바뀌고 a,b,c,d의 경우 char타입으로 바뀐다.

또한 :dq를 통해 python의 in처럼 객체의 인덱스를 차례차례 뒤지는 방법도 존재한다. 이 경우 :dq의 왼쪽에는 객체가 와야만 하기에 참조레퍼런스와 auto가 왔음을 알 수 있다.

Associate Container

  • set
  • map
  • unorder_map, set

연관 컨테이너의 특징으로는 key와 value값을 묶어서 저장하는 컨테이너이다. 주로 균형 이진트리나 해쉬 함수를 사용해 구현된다.

profile
공팡팡
공부 정리 노트

0개의 댓글