#C++ #알고리즘

STL 컨테이너

STL은 Standard Template Library의 약자로 C++ 에서 자료구조와 알고리즘의 Generic Programming (일반화 프로그래밍) 개념을 구현하기 위해 개발 된 C++ 라이브러리입니다. 이러한 STL 라이브러리의 종류와 컨데이너의 특성 및 사용법등을 정리해두려 합니다.

​

구성요소

  • 반복자 : STL 컨테이너의 원소들을 가리키는 포인터
  • 컨테이너: 데이터를 저장 및 관리를하는 클래스
  • 알고리즘 : STL에서 제공하는 함수

​

STL 컨테이너 종류

  1. 시퀀스 컨테이너
    1. 데이터를 선형적으로 저장합니다.
    2. vector, list, dequeue …
  2. 연관 컨테이너
    1. 일정 규칙에 따라 조직화된 컨테이너입니다.
    2. set, multiset, map …
  3. 어뎁터 컨테이너
    1. 시퀀스나 연관 컨테이너를 변형하여 정해진 방식으로 관리합니다.
    2. stack, queue …

​

시퀀스 컨테이너

시퀀스 컨테이너는 데이터를 선형적으로 저장하고 삽입된 요소의 순서가 그대로 유지됩니다.

​

벡터 (vector)

일반적인 배열은 배열의 길이가 정적인 특징의 단점을 극복하기 위한 컨테이너로 요소가 추가되거나 삭제될때 자동으로 메모리를 재할당 하고 크기를 동적으로 바꿉니다.

문법
1
2
#include <vector>
vector<Type> name(초기크기);

vector의 초기 크기를 지정하지 않으면 빈 백터를 생성합니다.

함수
  1. size() : 컨테이너에 저장된 요소의 개수를 반환
  2. push_front() : 맨 처음에 원소를 추가
  3. push_back() : 맨 끝에 원소를 추가
  4. pop_front() : 첫번째 원소를 제거
  5. pop_back() : 마지막 원소를 제거
  6. begin() : 컨테이너의 첫 요소를 가리키는 반복자를 반환
  7. end() : 컨테이너의 마지막 요소 바로 다음을 가리키는 반복자를 반환
  8. empty() : 컨테이너가 비었는지 확인

​

데크(deque)

dequeue는 양방향 큐를 의미하며, 양쪽에 끝이 있는 큐입니다. 이 컨테이너를 이용하면 양끝에서 삽입과 삭제를 빠르게 할 수 있습니다. vector와 마찬가지로 동적길이를 갖습니다.

문법
1
2
#include <deque>
deque<Type> name(초기크기);
함수
  1. size() : 컨테이너에 저장된 요소의 개수를 반환
  2. front() : 첫번째 원소에 접근
  3. back() : 마지막 원소에 접근
  4. push_front() : 맨 처음에 원소를 추가
  5. push_back() : 맨 끝에 원소를 추가
  6. pop_front() : 첫번째 원소를 제거
  7. pop_back() : 마지막 원소를 제거
  8. begin() : 컨테이너의 첫 요소를 가리키는 반복자를 반환
  9. end() : 컨테이너의 마지막 요소 바로 다음을 가리키는 반복자를 반환
  10. empty() : 컨테이너가 비었는지 확인

​

리스트(list)

리스트 컨테이너는 이중연결 리스트를 구현한 클래스 입니다.

문법
1
2
#include<list>
list<Type> name;
함수
  1. size() : 컨테이너에 저장된 요소의 개수를 반환
  2. front() : 첫번째 원소에 접근
  3. back() : 마지막 원소에 접근
  4. push_front() : 맨 처음에 원소를 추가
  5. push_back() : 맨 끝에 원소를 추가
  6. pop_front() : 첫번째 원소를 제거
  7. pop_back() : 마지막 원소를 제거
  8. begin() : 컨테이너의 첫 요소를 가리키는 반복자를 반환
  9. end() : 컨테이너의 마지막 요소 바로 다음을 가리키는 반복자를 반환
  10. empty() : 컨테이너가 비었는지 확인

​

연관 컨테이너

연관 컨테이너는 Key, Value 와 같이 관련있는 데이터를 하나의 쌍으로 저장하는 컨테이너 입니다. 연관 컨테이너는 보통 균형 이진 트리나 해시 테이블을 사용하여 구현됩니다. 아래의 컨테이너들은 균형 이진 트리중 하나인 레드블랙 트리를 이용합니다.

​

집합(set) / 멀티 집합(multiset)

집합 컨테이너는 저장하는 데이터 그 자체를 키로 사용하는 연관 컨테이너 입니다. 내부적으로 정렬되어 있어 빠른 검색속도를 가집니다.

set은 중복을 허용하지 않지만, multiset은 중복을 허용합니다.

문법
1
2
#include<set>
set<Type> name;
함수
  1. find() : 해당 요소를 가리키는 반복자를 반환
  2. size() : 컨테이너에 저장된 요소의 개수를 반환
  3. insert() : 요소를 컨테이너에 추가
  4. erase() : 요소를 컨테이너에서 제거
  5. begin() : 컨테이너의 첫 요소를 가리키는 반복자를 반환
  6. end() : 컨테이너의 마지막 요소 바로 다음을 가리키는 반복자를 반환
  7. empty() : 컨테이너가 비었는지 확인

​

맵(map) / 멀티맵(multimap)

맵 컨테이너는 Key와 Value의 쌍으로 데이터를 관리하는 연관 컨테이너 입니다. 맵 컨테이너도 빠른 검색 속도를 가집니다. map은 중복을 허용하지 않지만, multimap은 중복을 허용합니다.

문법
1
2
#include<map>
map<KType, VType> name;
함수
  1. find() : 해당 요소를 가리키는 반복자를 반환
  2. size() : 컨테이너에 저장된 요소의 개수를 반환
  3. insert() : 요소를 컨테이너에 추가
  4. erase() : 요소를 컨테이너에서 제거
  5. begin() : 컨테이너의 첫 요소를 가리키는 반복자를 반환
  6. end() : 컨테이너의 마지막 요소 바로 다음을 가리키는 반복자를 반환
  7. empty() : 컨테이너가 비었는지 확인

​

어댑터 컨테이너

어댑터 컨테이너는 기존 컨테이너의 인터페이스를 제한하거나 변형하여 만든 컨테이너 입니다. 하지만 반복자를 지원하지 않아 STL 알고리즘을 이용할 수 없습니다.

​

스택(stack)

vector클래스의 인터페이스를 제한해 구현한 스택 구조를 가지는 클래스 입니다.

문법
1
2
#include <stack>
stack<Type> name;
함수
  1. size() : 컨테이너에 저장된 요소의 개수를 반환
  2. top() : 스택의 최 상단의 요소의 참조를 반환
  3. push() : 스택 최상단에 요소 추가
  4. pop() : 스택 최상단에서 요소를 제거
  5. empty() : 컨테이너가 비었는지 확인

​

큐(queue)

큐는 deque클래스를 이용하여 큐를 구현한 클래스 입니다.

문법
1
2
#include <queue>
queue<Type> name;
함수
  1. size() : 컨테이너에 저장된 요소의 개수를 반환
  2. front() : 첫번째 원소에 접근
  3. back() : 마지막 원소에 접근
  4. push() : 큐에 맨 마지막에 요소를 추가
  5. pop() : 큐의 맨 앞의 요소를 제거
  6. empty() : 컨테이너가 비었는지 확인

​

우선순위 큐(priority_queue)

우선순위 큐는 vector클래스를 이용하여 힙을 구현해 우선순위큐를 구현한 클래스 입니다.

문법
1
2
#include <queue>
priority_queue<Type> name;
함수
  1. size() : 컨테이너에 저장된 요소의 개수를 반환
  2. push() : 우선순위 큐에 요소를 추가
  3. top() : 우선순위 큐에서 맨위의 요소에 접근
  4. pop() : 우선순위 큐에서 맨위의 요소 제거
  5. empty() : 컨테이너가 비었는지 확인
#C++ #알고리즘


Follow @techbless