STL 기초

STL은 Standard Template Library의 약자이며 Problem Solving에 편리하게 쓰이는 템플릿이다.

1. find

    find함수는 algorithm 헤더 파일에 있다.

    find함수의 생김새는 find(iterator first, iterator last, const T& val) 이와 같다.

   

    간략히 설명을 하면 찾고차 하는 값을 Linear하게 검색하여 그 값이 존재하면 위치를 가리키는 iterator를 반환하고 값이 존재하지 않으면      end()를 반환한다.

    시간복잡도 : O(n)

2. sort

    sort함수는 find와 마찬가지로 algorithm 헤더파일에 존재한다.

    sort는 두가지로 정의되어있다. 

     - sort(iterator begin, iterator end)

     - sort(iterator begin, iterator end, Compare compare)

    compare함수를 만들어서 사용하는 경우는 구조체를 sort하거나 원하는 정렬 기준을 갖고 정렬을 할 때 쓰인다.

     시간 복잡도 : O(nlogn)

3. min, max

  

   min, max는 영어 그대로 최솟값과 최댓값을 반환해주는 함수이다.

   algorithm 헤더파일에 존재

4. lower_bound / upper_bound

    둘 다 algorithm 헤더파일에 존재한다.

     - lower_bound(arr, arr+n, value, cmp)

     - upper_bound(arr, arr+n, value, cmp)

     

     value가 들어갈 위치를 탐색하는 함수이다.

     lower_bound : value보다 큰 첫번째 원소 가리키는 iterator 반환

     upper_bound : value보다 작은 마지막 원소를 가리키는 iterator 반환

5. pair

     pair는 utility 헤더파일안에 존재한다.

     두개의 자료형을 하나로 묶을때 사용한다.

6. tuple

    

     tuple은 tuple헤더파일에 존재한다.

     여러가지의 자료형을 묶을때 사용한다.

     

     ex) tuple<int, int, int> t(1,2,3);

         tuple<int, int, int> t2 = make_tuple(1,2,3);

          int t1 = get<0>(t);

          int t2 = get<1>(t);

7. vector

     vector는 가장 많이 사용하는 컨테이너이다.

     vector의 장점은 저장할 데이터의 갯수가 가변적일 때 편리하게 사용할 수 있다. 그 이유는 동적할당으로 크기가 변하기 때문이다.

     이것이 바로 배열과 다른점이기도 하다.

8. deque

   

    deque는 stack이랑 queue가 결합된 자료구조이다. 따라서 앞, 뒤에서 삽입과 삭제가 가능하다.

    하지만 stack, queue와 다르게 vector처럼 랜덤접근이 가능하다.