정부기 DevBlog

STL

8 min read

STL STL (Standard Template Library) Generic Programming 의 대표 문법.

STL의 구성 요소로 표현되어지는 4가지 용어

1. 컨테이너 : 데이터를 저장하는 객체, 즉 자료 구조를 구현한 객체 (클래스 템플릿 집단)

  • [*] 컨테이너의 분류 기준

  • [>] 원소 배치 방식에 따른 분류법 시퀀스컨테이너 연관컨테이너

  • 표준 시퀀스 컨테이너 : vector, deque1, list, array, forward_list2,
    연달아 정렬한 형태로 정리한 컨테이너

  • 표준 연관 컨테이너(정렬) : set, multi-set, map, multi-map 비선형적 구조의 특징을 가진 컨테이너

  • 표준 연관 컨테이너(비정렬) : unordered_set, unordered_map

  • [>] 메모리 저장 방식에 따른 분류법

    • 배열 기반 컨테이너 : vector, deque
    • 노드 기반 컨테이너 : set, multi-set, map, multi-map, list

  • [>] 컨테이너 어댑터(연결 장치)

    • Stack , queue, priority_queue
    • 컨테이너의 기능 중 일부의 기능만 사용 가능, 기능 제한이나 변형되어 있는 형태로 사용함.
    • 컨테이너의 기능을 보완하거나, 추가적인 사용성을 지원하는 용도로 사용함

  • [>] 근사 컨테이너(almost)

    • 템플릿으로서의 속성을 모두 갖추지 못한 상황의 컨테이너
    • string / wstring

2. 알고리즘 (STL 알고리즘) #include <algorithm> 파일을 포함해야 제공하는 STL 함수들을 사용할 수 있음

  • [*] 대량의 데이터를 관리할 떄 무엇이 더 효울적인지에 대한 것을 다루는 학문
  • [?] 알고리즘의 사용처 탐색 / 정렬 / 삭제와 같은 방법 일반화된 방법으로 제공, 함수 템플릿 집단 특정 컨테이너 멤버가 아닌 전역 함수의 형태로 제공 다수 컨테이너에 대해 동일하게 적용 가능하도록 캡슐화를 진행하지 않음.

보통 알고리즘을 사용하는 형태 = 알고리즘 (begin, end, 조건자) 범위를 지정해주어, 순회를 하며 조건에 맞는 것을 찾아주는 형태

3. 함수 객체

  • [*] 객체를 함수처럼 사용하는 문법. 함수 포인터보다는 함수 객체를 이용해서 만드는 것이 권장됨. 보편적으로는 bool 타입을 반환하는 형태로 제작하며, STL 알고리즘 동작의 조건을 제공하기 위해 제작됨.
  • [!] 그러나 람다식의 등장으로 사용 입지가 줄어들게 되었음.

4. 반복자 ⭐⭐⭐

  • [*] 컨테이너 안의 원소를 접근하기 위한 용도의 객체(절대 포인터 아님3) 컨테이너 마다 개별적인 반복자를 소유하고 있으나, 멤버 변수or 함수는 아님4
  • 관리하는 방식이 컨테이너 마다 다르기 때문에 컨테이너를 순회하는 방법과 원소를 참조하는 방법을 획일화하여 사용할 수 있도록 제공

STL 컨테이너의 특성

  • [I] 벡터의 특성 vector

    1. 반개 구간 (반만 열렸다) [ begin, end ) - 시작은 언제나 같지만, 끝은 정해지지 않았다.
    2. 동적 배열을 기반으로 하는 컨테이너.
    3. 인덱스 접근이 가능하다 = 탐색이 빠르다.⭐
    4. 삽입 시에 앞에서부터 삽입할 수 없다. (맨 끝부터 추가)
    5. 중간 삽입 및 삭제 시, 원소 개수 만큼의 선형적 시간 복잡도가 발생함.(꺼내서 지우고 다른 곳에 재할당)❗
    6. 벡터의 원소를 삭제해도 존재했던 공간(메모리)은 남아있다.
    7. 맨 끝에 삽입 삭제 시에는 상수 시간 복잡도가 발생한다. (빠르다)
    8. 배열의 크기를 넘어갓을 때, 동적 배열의 재할당과 원소 복사가 있기에 느리다.

  • [I] 리스트의 특성 List

    1. 노드를 기반으로 하는 컨테이너
    2. 앞/뒤 노드의 삽입 삭제가 가능하다.(상수 시간 복잡도)⭐
    3. 비연속적인 공간에 나열된 노드들을 연속된 것처럼 나열. 그래서 인덱스 접근이 불가함. ❗
    4. 탐색과 순회가 반드시 순서대로 진행되기 때문에 선형 시간 복잡도가 걸린다.
    5. ++/-- 연산자만 오버로딩 되어 있음.
    6. 한정된 메모리 공간을 사용하는 것이 아니기 때문에 데이터 저장이 유연하다.⭐

  • [I] 덱(deque)의 특성 deque

    1. vector의 한 종류의 컨테이너이며 동적 배열 기반이다.
    2. 인덱스 접근이 가능하다.
    3. chunck5 형태의 데이터 저장이 진행됨.
    4. 벡터와 리스트가 혼합된 형태.
    5. 벡터랑 비교했을 때 8배 가까이 되는 메모리 용량을 요구함.

  • [I] 표준 연관 컨테이너의 특성(정렬)

    1. 기본적으로 트리 기반으로 구성된 컨테이너.

[#추천도서] 제프리 리처의 WINDOWS VIA C/C++(복간판) - 국내도서 (준형이형 추천)

Footnotes

  1. 메모리에 일정한 크기를 지닌 블록 형태로 흩어져서 저장되는 자료구조 ↩

  2. 양방향 이동이 불가하고, 단방향 이동만 가능한 리스트 ↩

  3. 포인터의 연산자를 오버로딩하여 포인터처럼 사용할 뿐, 포인터로 착각하면 안됨. ↩

  4. 컨테이너 마다 이터레이터라는 객체를 이너 클래스로 지니고 있는 형태 ↩

  5. 메모리 구성 단위, 즉 데이터 블럭이라고 보는 것이 맞음 ↩

그래프 뷰