STL : Standard Template Library

• c++에서 제공하는 표준 템플릿 라이브러리
• STL로 제공하는 자료구조
  • vector, list, map, set 등등
  • 템플릿 형태로 제공해서 다양한 자료형에 대응 가능

#include <iostream>
#include <vector>
#include <list>

using std::vector;
using std::list;

int main() 
{
	vector<int> vla;
	list<int> linkedList;

	return 0;
}

이렇게 제공하는데도 직접 만들어본 이유
1. 기존에 배운 것들을 활용하여 충분히 자료구조를 만들어볼 수 있음.
2. 자료구조에 대한 이해

---

멤버 함수

	vector<int> vla;
	vla.push_back(10);
	vla.push_back(20);
	vla.push_back(30);

	vla[0] = 100;
	int value = vla.at(1); // 함수 버전

	vla.data();
	vla.size();
	vla.capacity();

• vla.push_back(10); : 구현했던 것과 동일하게 작동할 것
• vla[0] = 100; : 연산자 오버로딩으로 바로 접근하는 것을 구현해둔 것.
  • int value = vla.at(1); : 이 기능의 함수 버전
• vla.data(); : 가변 배열이 가진 힙 메모리의 시작 주소.
  가변 배열에 값을 넣는다 => 가변 배열의 힙 메모리에 값을 넣는 것.
  그렇다면 최소 시작 주소도 받을 수 있을 것.
• vla.size(); : 현재 갯수
• vla.capacity(); : 힙 메모리에 할당된 메모리의 크기

---

	list<int> linkedList;
	linkedList.push_back(1000);
	linkedList.push_back(2000);
	linkedList.push_front(10);

	linkedList.size(); //

• linkedList.push_back(1000);, linkedList.push_front(1000);
  • 구현했던 것과 동일하게 작동할 것
• 연결형 리스트는 capacity 개념이 없음. 그때그때 추가하는 것이므로.
• 여기서 배우지 않은 것이 있음. iterator 반복자

---

iterator

• 리스트가 자신의 데이터를 한 바퀴 순회하는 방법은?
  • 리스트의 경우 바로 접근하는 것이 불가능하기 때문에 [] 연산자가 없음.
    • 메모리가 연속된 구조가 아니기 때문.
    • 리스트가 내부적으로 특정 자료에 접근하는 방법은 노드를 순차적으로 따라가야함.
    • 억지로 [] 연산자를 만든다면 위의 방법으로 작성하게 될 것.
  • 벡터는 반복문으로 순회하면 됨.
  • 근데 리스트는 헤드 노드를 통해 차례차례 접근해야함.
  • 자료구조는 편하게 쓰기위해 만드는 것인데, 이렇게하면 사용자가 내부 설계를 깊게 알아야함.
• 가변 배열과 리스트를 동일한 방법으로 쓸려면 리스트는 다른 방법을 써야하는데 그것이 iterator

	list<int>::iterator iter;
	iter = linkedList.begin();	// 리스트의 첫번째 데이터를 가리키도록 함.
	int val = *iter;			// 포인터처럼 동작하는데 본래는 클래스임. 즉, 연산자 오버로딩임.

• list<int>::iterator iter; 리스트 안에 구현되어 있는 반복자 클래스. (inner class. 포함 클래스)
• int val = *iter; : 포인터처럼 동작하는데 본래는 클래스임.
  • 즉, 이 형태는 연산자 오버로딩임.

---

STL 추가 정리

구성요소

• STL은 효율성, 유연성, 재사용성을 위해 만들어짐.
• STL이 제공하는 기능들은 크게 4가지로 분류할 수 있음.
  1. 컨테이너 Containers
  2. 알고리즘 Algorithms
  3. 반복자 Iterator
  4. 함수 객체 Functors

---

1. 컨테이너 Container

• 데이터나 객체를 보관하기 위해 사용하는 자료구조들
  • 모든 자료구조는 템플릿 클래스로 구현돼 있고 자료구조의 기본 기능 구현을 포함하고 있음.
  • 모든 컨테이너들은 각자의 헤더 파일에 선언돼있음.
  • 컨테이너들은 또 다시 다음 4가지로 분류할 수 있음.
    1. 순차 컨테이너 Sequence Container
    2. 컨테이너 어댑터 Container Adaptors
    3. 연관 컨테이너 Associative Containers
    4. 비정렬 연관 컨테이너 Unordered Associated Containers

---

1-1. 순차 컨테이너 Sequence Container

• 순차 컨테이너는 자료들을 선형(Linear)으로 보관함.
  • 컨테이너 어댑터를 구현하기 위해 사용되기도 함.

배열 array

• 컴파일 타임에 고정된 크기를 가진 배열. (고정 배열)

벡터 vector

• STL이 제공하는 가변 배열.

데큐 deque

• 데큐, 양 끝단의 확장과 수축 기능을 가진 쌍방향 큐.

리스트 list

• 데이터의 값을 노드 형태로 저장하고, 각각의 노드는 앞뒤에 있는 노드 주소를 갖고 연결함.
• 벡터와 달리 데이터를 비연속적으로 메모리에 값을 배치하여 저장.
  • 그리고 데이터에 대한 접근을 순차적으로 제공.
• 기본적으로 양방향 연결형 리스트.

포워드 리스트 forward list

• 리스트처럼 선형적으로 데이터를 저장하지만, 리스트와 차이점은 다음 데이터의 주소만 저장.
  • 단방향 연결형 리스트

---

1-2. 컨테이너 어댑터 Container Adaptors

• 기본 컨테이너들을 이용해서 구성되어 특정한 요청에 적합한 자료구조.
  • 반복자를 지원하지 않고 STL 알고리즘을 적용할 수 없음.

스택 stack

• 후입선출(Last In First Out : LIFO)의 원리에 따라 요소를 삽입하고 제거하는 자료구조.

큐 queue

• 선입선출(First In First Out : FIFO)의 원리에 따라 첫번째 요소가 먼저 출력되는 자료구조.
• 기본적으로 데큐 컨테이너를 사용.

우선순위 큐 priority queue

• 후입선출(LIFO), 선입선출(FIFO) 원리를 따르지 않음.
• 데이터의 출력 시, 우선순위 기준에 따라 이루어짐.
  • 데이터를 넣으면 데이터들이 우선순위 기준에 따라 정렬됨.
  • 그러므로 기본 값일 경우 제일 큰 값이 먼저 출력됨.
• 기본적으로 벡터를 기반 컨테이너로 사용.
• 큐 헤더에 같이 구현돼 있음.

---

1-3. 연관 컨테이너 Associative Container

• 데이터를 일정 규칙에 따라 조직화하여 저장하고 관리하는 컨테이너들.
• 기존의 컨테이너들과 달리, 삽입 순서가 아니라 키(key)값으로 요소들을 정렬하여 저장한다.

세트 set

• 요소들을 중복없이 유일한 상태로 관리하는 컨테이너.
  • 요소의 값을 통해서 구분하기 때문에 들어오는 요소들은 중복없이 단 하나씩만 존재.
• 기본적으로 오름차순 정렬.
• 내부는 이진 탐색 트리로 구현되어 있음.

맵 map

• 요소들을 키-값 쌍의 형태로 저장하는 컨테이너.
• 키는 중복이 불가하며, 키를 기준으로 정렬됨.
• 내부는 이진 탐색 트리로 구현되어 있음.

멀티 세트 multiset

• 세트와 유사하지만 값을 중복으로 저장할 수 있음.
• 얼핏 쓰임새가 vector와 유사해보이나 내부 구조와 사용 목적이 다름.
• vector와 차이 및 사용 상황
  
  
  • multiset
    • 자동 정렬된 중복 허용.
    • 시간 복잡도
      • 삽입, 삭제, 탐색 : $O(log N)$
  • vector
    • 순차 배열.
    • 시간 복잡도
      • 인덱스를 통한 접근, 탐색 : $O(1)$
      • 삽입, 삭제 : $O(N)$

빠른 탐색과 정렬 필요 시 : multiset.
빠른 인덱스 접근 필요 시 : vector.

멀티 맵 multimap

• 맵와 유사하나 하나의 키에 대해서 여러 값을 맵핑할 수 있음.
• 정렬은 키를 기준으로 우선 정렬하고 키에 맵핑된 값은 들어온 순서로 저장됨.

#include <bits/stdc++.h>
using namespace std;

int main() {
    multimap<int, string> mm = {{1, "Geeks"},
                     {2, "For"}, {1, "C++"}};
    
    // Traverse multimap
    for(auto it = mm.begin(); it != mm.end(); it++)
        cout << it->first << " " << it->second
        << "\n";
    return 0;
}

• iterator를 통한 순회 결과

1 Geeks
1 C++
2 For

---

1-4. 비정렬 연관 컨테이너 Unordered Associative Container

• 연관 데이터와 다르게 자료들을 특정 기준으로 정렬하지 않음.
• 정렬 작업이 없는 만큼 데이터 삽입, 삭제, 탐색 작업이 빠름.
  • 아티클에선 STL의 모든 컨테이너들 중에서 제일 빠르다고 함.

비정렬 세트 unordered_set

• 해시 테이블 형태로 키를 중복없이 저장.
  • 세트와 달리 값을 해시를 사용해서 저장함.
• 이러한 특성으로 자료들이 정렬되진 않으나,
  삽입, 삭제, 탐색이 평균적으로 $O(1)$의 시간복잡도를 제공하는 자료형.

비정렬 멀티 세트 unordered_multiset

• 비정렬 세트와 유사하게 작동하지만 하나의 키에 여러 값을 담아 저장할 수 있음.

비정렬 맵 unordered_map

• 맵과 같이 데이터를 키-값 쌍의 형태로 저장.
• 맵과 다르게 해시를 이용해서 데이터를 저장.
• 자료들이 정렬되진 않으나 삽입, 삭제, 탐색이 평균적으로 $O(1)$의 시간복잡도를 제공.

비정렬 멀티 맵 unordered_multimap

• 비정렬 맵과 유사하나, 하나의 케에 대해 여러 값을 맵핑할 수 있음.

---

2. 알고리즘 Algorithms

• STL의 알고리즘 라이브러리는 주로 컨테이너 데이터들에 대해 공통적인 연산을 수행하는 광범위의 함수들을 제공한다.
  • 정렬, 탐색, 데이터 수정, 조작과 같은 작업들에 대해 가장 효율적인 버전의 함수들을 구현.
• 모든 알고리즘은 <algorithm>, <numeric> 헤더에 선언돼 있음.
• 동작에 따라 크게 두 가지로 분류 가능
  • 수정 알고리즘 Manipulative Algorithms
  • 비수정 알고리즘 Non-Manipulative Algorithms

---

2-1. 수정 알고리즘 Manipulative Algorithms

• 주어진 컨테이너의 데이터 요소를 수정하거나 순서를 재정렬하는 연산을 수행.
• 여러 함수들이 있으며 다음은 자주 쓰이는 수정 알고리즘들은 다음과 같음.

---

• copy : 컨테이너의 특정 순서부터 n개에 해당하는 데이터들을 다른 컨테이너로 복사.
• fill : 지정 범위의 모든 요소들을 특정 값으로 채움.
• transform : 지정 범위의 각 요소들에 함수 연산을 적용하고 그 결과를 다른 범위에 저장한다.
• replace : 지정 범위의 값들을 모두 새로운 값으로 교체함.
• swap : 두 변수를 서로 교환함.
• reverse : 범위의 요소들의 순서를 반전시킴.
• rotate : 지정한 범위에서 특정 값이 가장 앞으로 오도록 순서를 바꿈.
• remove : 지정한 범위에서 특정 값을 제거함.
  • 컨테이너 사이즈를 줄이진 않음.
• unique : 범위에서 연속해서 중복되는 값을 제거함.

2-2. 비수정 알고리즘 Non-Manipulative Algorithms

• 컨테이너의 데이터들에 대해서 그 값이나 순서를 대체하지 않고 작동하는 연산들.
• 몇몇 예시들

---

• max_element : 주어진 범위에서 가장 큰 요소를 찾음.
• min_element : 주어진 범위에서 가장 작은 요소를 찾음.
• accumulate : 주어진 범위에서 요소들의 합을 구함.
• count : 범위 내에서 특정 값의 갯수를 구함.
• find : 범위 내에서 특정 값을 찾고, 가장 먼저 나온 위치의 iterator를 반환.
• is_permutation : 한 범위가 다른 범위의 순열인지 확인함.
• is_sorted : 범위 내 요소들이 감소하지 않는 순서로 정렬되어 있는지 확인함.
• partial_sum : 특정 범위의 요소들의 부분 합을 계산함.

---

3. 반복자 Iterator

• 반복자는 컨테이너의 메모리 주소를 가리키는데 사용되는 포인터 같은 객체들을 의미함.
  • STL 알고리즘을 컨테이너와 연결시키는데 가장 큰 역할을 한 중요한 요소.
• iterator 헤더에 선언되어있음.
• C++ STL에서 반복자들은 iterator들의 기능에 따라 5종류로 분류할 수 있음.
  1. 입력 반복자 Input Iterator
  2. 출력 반복자 Output Iterator
  3. 순방향 반복자 Forward Iterator
  4. 양방향 반복자 Bidirectional Iterator
  5. 임의 접근 반복자 Random Access Iterator

3-1. 입력 반복자 Input Iterator

• 컨테이너로부터 값을 읽을 수만 있고 변경할 수 없음. (읽기 전용)
  • ++ 증가 연산자로 순방향 이동만 가능.
  • * 역참조를 통해 값을 읽어올 수 있음.
• Find()
  • 함수와 같이 순차 검색으로 특정 값을 찾아내는데 사용할 수 있음.

  template<class InputIterator, class T>
  InputIterator Find(InputIterator first, InputIterator last, const T& value);

3-2. 출력 반복자 Output Iterator

• 컨테이너의 값을 변경하는데 사용.
  값을 변경할 순 있으나 읽어올 순 없음. (쓰기 전용)
  • ++ 증가 연산자로 순방향 이동만 가능.
  • * 역참조를 통해 단 한 번만 값을 쓸 수 있음.
• Copy()
  • 다른 컨테이너에 특정 범위의 값을 복사해 넣는데 사용할 수 있음.

  template<class InputIterator, class OutputIterator>
  OutputIterator Copy(InputIterator first, InputIterator last, OutputIterator result);

3-3. 순방향 반복자 Forward Iterator

• 컨테이너의 값을 입력, 출력 모두 할 수 있는 반복자
• 입력 반복자 + 출력 반복자
  • ++ 증가 연산자로 순방향 이동만 가능.
  • * 역참조로 몇번이고 참조하거나 변경할 수 있음.
• Replace()
  • 범위 내에 특정 값을 다른 값으로 교체하는데 사용할 수 있음.

  template<class ForwardIterator, class T>
  void Replace(ForwardIterator first, ForwardIterator last, const T& target, const T& replacement);

3-4. 양방향 반복자 Bidirectional Iterator

• 입력, 출력 모두 가능하며 역방향 이동 기능이 포함된 반복자
• 순방향 반복자 + 역방향 기능 추가
  • ++, -- 증감 연산자로 순방향, 역방향 이동 가능.
  • * 역참조로 몇번이고 참조하거나 변경할 수 있음.
• Reverse()
  • 특정 범위의 요소들을 역으로 정렬하는 새 컨테이너를 반환할 때 사용됨.

  template<class BidirectionalIterator, class OutputIterator>
  OutputIterator Reverse(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result);

3-5. 임의 접근 반복자 Random Access Iterator

• 최상위 레벨 반복자로 가능 많은 기능 제공
• 양방향 반복자 + 임의 요소 접근 기능 추가
  • [] 첨자 연산자로 임의의 요소에 접근할 수 있음.
  • ++, -- 증감 연산자로 양뱡향 이동.
  • * 역참조를 통해 요소 접근 가능
  • >=, >, <, <=, ==, != 비교 연산자 사용 가능
• Sort()
  • 특정 범위를 정렬할 때, 비교, 접근, 양방향 순회를 위해 사용됨.

  template<class RandomAccessIterator>
  void Sort(RandomAccessIterator first, RandomAccessIterator last);

---

4. 함수 객체 Functors

• 함수처럼 취급할 수 있는 객체들.
  • 흔히 STL 알고리즘과 함께 사용.
• 호출 연산자 ()를 오버로드해서 사용자들이 객체를 함수처럼 쓸 수 있도록 함.
• functional 헤더에 STL의 많은 함수 객체들이 선언되어 있음.
• 함수 객체들은 수행하는 연산 종류에 따라 분류할 수 있음.
  1. 산술 연산 Arithmetic Functors
  2. 관계형(비교연산) Relational Functors
  3. 논리형 Logical Functors
  4. 비트 단위 Bitwise Functors

---

4-1. 산술 연산 Arithmetic Functors

• plus : 두 매개변수의 합을 반환
• minus : 두 매개변수의 차를 반환
• multiplies : 두 매개변수의 곱을 반환
• divides : 두 매개변수를 나누어 몫을 반환
• modulus : 두 매개변수를 나누어 나머지를 반환
• negate : 매개변수에 -1을 곱하여 반환

---

4-2. 관계형(비교연산) Relational Functors

• equal_to : 두 매개변수가 같다면 true 반환
• not_equal_to : 두 매개변수가 다르다면 true 반환
• greater : 두 매개변수 중, 첫번째가 크다면 true 반환
• greater_equal : 두 매개변수 중, 첫번째가 크거나 같다면 true 반환
• less : 두 매개변수 중, 첫번째가 작다면 true 반환
• less_equal : 두 매개변수 중, 첫번째가 작거나 같다면 true 반환

---

4-3. 논리형 Logical Functors

• logical_and : 두 매개변수에 대한 && 연산의 결과를 반환
• logical_or : 두 매개변수에 대한 || 연산의 결과를 반환
• logical_not : 매개변수에 대한 ! 연산의 결과를 반환

---

4-4. 비트 단위 Bitwise Functors

• bit_and : 두 매개변수에 대해 비트 연산자 &의 결과를 반환
• bit_or : 두 매개변수에 대해 비트 연산자 |의 결과를 반환
• bit_xor : 두 매개변수에 대해 비트 연산자 ~의 결과를 반환

출처

• STL 정리글 - geeksforgeeks
  • 각 항목에 대한 세부 정리 글과 예시들이 있음.
• STL 참고 - cplusplus
• C++ 교재 - tcpschool