[STL] STL 기본 구성 요소 & 반복자

STL이란?

Standard Template Library의 약자로, 프로그램에 필요한 자료구조와 알고리즘을 템플릿으로 제공하는 라이브러리다
자료구조와 알고리즘은 서로 반복자라는 구성 요소를 통해 연결한다

STL의 특징

효율성 / 일반화 프로그램(재사용성) / 확장성

---

간단한 정의

(컨테이너) Container

• 객체를 저장하는 데 사용되는 자료구조이다

(반복자) Iterator

• 포인터와 비슷한 개념. 컨테이너의 원소를 가리키고,가리키는 원소에 접근하여 다음 원소를 가리키게 해준다

(알고리즘) Algorithm

• 정렬, 삭제, 검색, 연산 등을 해결하는 방법을 제공하는 함수 템플릿

(어댑터) Adaptor

• 구성 요소의 인터페이스를 변경해 새로운 인터페이스를 갖는 구성요소

(함수객체) Function Object

• 함수처럼 동작하는 객체. operator()연산자를 오버로딩한 객체이다

---

Container (컨테이너)

같은 타입을 저장, 관리할 목적으로 만들어진 클래스. 2가지로 나눌 수 있다

저장 방법에 따른 2가지 분류

• 표준 시퀀스 컨테이너 (Standard Sequence Container)
  -> 컨테이너 원소가 자신만의 삽입 순서를 가지는 컨테이너 (선형적)
  -> ex) vector, deque, list

• 표준 연관 컨테이너 (Standard associative container)
  -> 삽입 순서와 다르게 특정 정렬 기준에 의해 원소가 자동 정렬되는 컨테이너 (비선형적)
  -> ex) set, multiset, map, multimap

---

저장 메모리 단위에 따른 2가지 분류

• 배열 기반 컨테이너 (array - based container)
  -> 데이터 여러개가 하나의 연속된 메모리 공간(단위)에 저장
  -> ex) vector, deque

• 노드 기반 컨테이너 (node - based container)
  -> 각 데이터가 독립된 메모리 단위(노드)에 저장
  -> 각 노드는 포인터를 통해 다음 노드를 가리키는 방식
  -> ex) list, set, map, multimap, multiset

---

🔷 iterator (반복자)

컨테이너(자료구조) 내의 요소에 접근할 수 있게 해주는 객체
-> 컨테이너 요소를 순차적으로 탐색할 수 있도록 도와준다 (포인터 처럼 사용)

vector<int> :: iterator iter = v.begin();

📌 왜 포인터와 유사하다는 걸까?

iterator타입의 iter 변수는 v.begin()의 위치만 가리키는 상태
-> 그래서 포인터 느낌이다
-> iter 변수가 가리키는 값을 알고싶을때도 일반적인 cout << iter 로 출력하면 에러가 발생한다
-> 위치만 가리키고 있기 때문에 역참조를 통해 출력할 수 있다 cout << *iter

---

🔷 begin(), end()

반복자를 반환하는 메소드

반복자는 (iterator) 반환된 반복자를 사용하여 실제 요소를 순회한다

• 맨 처음 요소를 가리키는 begin();
  출력해보면 맨 처음 요소 10이 출력된다

• 📌 end() 맨 마지막 요소의 다음을 가리킨다 !!

  맨 마지막 요소가 아닌 맨 마지막 요소의 다음 위치를 가리키기 때문에, 실제 값을 출력하려고 하면 에러 발생
  아래의 코드는 에러가 발생한다 %%%%%

---

'순차열'을 대상으로 하는 알고리즘 (find & sort)

STL의 순차열 즉, 시퀀스(컨테이너 원소의 집합)를 대상으로 하는 알고리즘이 있다

이 알고리즘은 한쌍의 반복자를 필요로 한다
ex) find(), sort()

find()

find()는 순방향 반복자를 요구하는데, 모든 컨테이너들은 양방향 반복자 이상을 제공하기 때문에 가능하다

반복자가 vector<int>를 순회하면서 요소 35를 찾는다

sort()

sort()는 임의 접근 반복자를 요구한다
-> 임의 접근 반복자로는 vector & deque 등의 시퀀스(선형) 컨테이너

📌 이 둘을 제외한 컨테이너들은 sort() 알고리즘 적용 자체가 말이 안된다
-> 연관 컨테이너 (map & set)
-> 연관 컨테이너는 요소들이 컨테이너만의 정렬 기준으로 자동 정렬되기 때문이다 (키, 쌍)

연결리스트에서도 사용 불가능

-> 연결리스트는 양방향 반복자로, 임의 접근 반복자가 아니기 때문이다 (인덱스 접근 불가)

-> 리스트는 인덱스 접근이 불가하기 때문에, 요소 순차탐색 후 출력하려면 반복자를 사용해야한다

• 반복자를 사용한 리스트 순차 탐색 후 출력

---

함수 객체 (greater(), less())를 sort와 함께 사용

내림차순 정렬

sort(v.begin(), v.end(), greater<int>());

오름차순 정렬

sort(v.begin(), v.end(), less<int>());
-> 함수 객체를 사용하지 않으면 기본 오름차순 기준으로 정렬한다

---

Adaptor (어댑터)

구성요소의 인터페이스를 변경한다

• 컨테이너 어댑터 : stack, queue, priority_queue
• 반복자 어댑터 : reverse_iterator 등등...
• 함수 어댑터 : 부정자(Not2), 바인더, 함수 포인터 어댑터

---

컨테이너 어댑터 (ex : stack)

대표적인 컨테이너 어댑터로 stack이 있다

stack은 일반 컨테이너를 LIFO 방식으로 변환한다

push, pop, empty, size 등의 인터페이스(멤버함수)를 지원하는 컨테이너는 모두 stack 어댑터를 사용하여 변환할 수 있다
-> 시퀀스(순차) 컨테이너들 가능

stack <타입, 내부 컨테이너 타입> 변수 이름;

stack의 내부 컨테이너는 디폴트가 deque<T>으로 지정되어있다
-> 덱은 앞뒤로 모두 삽입 삭제가 가능하다 (스택 + 큐 느낌)

기본 내부 컨테이너

ex) stack <int> st; 생성
-> stack의 내부 컨테이너 타입을 지정하지 않으면 기본 컨테이너는 덱으로 잡힌다
-> 아래의 코드에서 st의 내부컨테이너는 deque

내부 컨테이너 지정

ex) stack <int, vector<int>> st;
-> int 형 데이터를 저장할 stack 자료구조이고, 내부 컨테이너는 vector이다
-> 내부적으로 vector<int>를 사용하여 데이터를 저장

결론은 stack 컨테이너 어댑터를 사용하면 사용자들이 보기에는 LIFO 방식으로 데이터가 삽입 삭제 되는 걸로 보이고, 실제 내부 데이터들은 내부 컨테이너 방식에 따라 데이터가 삽입 삭제 되고 있는 것

---

🔷 반복자 어댑터 (ex : reverse_iterator)

반복자 어댑터 중 reverse_iterator는 역방향 반복자로, 정방향 반복자(iterator)를 역방향 반복자로 변환한다

• 정방향 반복자 : iterator
• 역방향 반복자 : reverse_iterator

reverse_iterator <vector <int> :: iterator> riter (v.end());
정방향 반복자를 역방향 반복자로 변환하는 riter 변수는 v.end()를 가리킨다

이렇게 직접 코드를 짤 필요없이, 모든 컨테이너들은 자신의 역방향 반복자를 반환하는 멤버 함수를 사용할 수 있다

• rbegin() : 순차열의 끝을 가리킨다
• rend() : 순차열의 제일 앞 요소의 이전을 가리킨다
  

📌 end() & rend() 주의점 !!!!

앞에서 end() 접근 주의할 점은 얘기했지만 그래도 다시 보자

• end() 는 가장 뒷 요소의 다음을 가리킨다
• rend() 는 가장 앞 요소의 이전을 가리킨다

두 함수는 실제 값을 가리키는 게 아닌 끝났다는 것을 알려주는 '끝 위치'를 가리키는 것

둘 다 처음과 끝이 [begin, end)를 만족한다 -> begin 이상 end 미만

---

함수 어댑터 (ex : not2)

not2는 조건자 함수 객체를 반대 의미의 조건자 함수 객체로 변경하는 어댑터이다
not1은 단항 조건자, not2는 이항 조건자에 사용된다

ex) less 함수객체를 반대 시키기
std :: less<T> : 비교 함수 객체로, T타입의 두 객체를 비교하여 true / false를 반환한다

less<int>(매개변수1, 매개변수2);
매개변수1 < 매개변수2 = true

임시 함수객체

임시 함수 객체는 객체를 정의하지 않은 상태로 사용하는 것

함수 객체 정의

---

함수 어댑터 not2 사용하기

not2사용 시 #include <functional> 사용
not2는 결과를 반전시킨다
-> 결과값이 true라면 false를 반환한다

---

할당기 (allocator)

할당기란 메모리 할당 및 관리를 담당하는 시스템을 말한다

ex) vector<typename T, typename Alloc);
일반적으로 메모리 관리에 사용할 할당기 까지는 적지 않았기 때문에 vector<int> 이런식으로 적었을 것이다
-> 이 경우엔 기본값 allocator<T>로 적용된다

---

🔷 삽입 반복자 inserter()

순차열에 원소를 삽입할 수 있게 반복자를 변환하는 반복자 어댑터이다.

덮어쓰기 모드와 다르게 삽입 모드로 동작하여 ➡ 원소의 갯수가 늘어난다.

삽입 반복자	사용 함수	사용 가능한 컨테이너	특징 및 동작 방식	필요 조건
back_inserter()	push_back()	vector, deque, list	컨테이너 뒤에 원소를 추가	push_back() 필요
front_inserter()	push_front()	deque, list	컨테이너 앞에 원소를 추가 (deque, list 가능)	push_front() 필요
inserter()	insert(pos, v)	대부분의 컨테이너	지정된 위치에 원소 삽입	insert(pos, val) 필요

🔹 inserter()

int main()
{
	vector <int> v1;

	v1.push_back(10);
	v1.push_back(20);
	v1.push_back(30);

	vector <int> v2;

	copy(v1.begin(), v1.end(), inserter<vector<int>>(v2, v2.begin()));

	for (vector<int>::iterator iter = v2.begin(); iter != v2.end(); iter++)
	{
		cout << *iter << " "; // 10 20 30
	}
}

🔹 back_inserter()

vector, deque, list 가능

int main()
{
	vector <int> v1;

	v1.push_back(10);
	v1.push_back(20);
	v1.push_back(30);

	vector <int> v2;

	v2.push_back(1);
	v2.push_back(2);
	v2.push_back(3);

	copy(v1.begin(), v1.end(), back_inserter<vector<int>>(v2));

	for (vector<int>::iterator iter = v2.begin(); iter != v2.end(); iter++)
	{
		cout << *iter << " "; // 1 2 3 10 20 30
	}
}

🔹 front_inserter()

list, deque만 가능하다. ➡ push_front()로 원소를 삽입할 수 있다.

int main()
{
	vector <int> v1;

	v1.push_back(10);
	v1.push_back(20);
	v1.push_back(30);

	list <int> l1;

	l1.push_back(1);
	l1.push_back(2);
	l1.push_back(3);

	copy(v1.begin(), v1.end(), front_inserter<list<int>>(l1));

	for (list<int>::iterator iter = l1.begin(); iter != l1.end(); iter++)
	{
		cout << *iter << " "; // 30 20 10 1 2 3
	}
}

---

🔷 보조 함수 advance()

advance(p, n) ➡ p반복자를 p += n의 위치로 이동시킨다.

list의 경우 임의 접근 반복자가 아닌 양방향 반복자이다.
➡ 즉, +=, -= 연산으로 반복자를 이동시킬 수 없다. 이런 경우에 advance()를 사용한다.

int main()
{
	list <int> l1;

	l1.push_back(1);
	l1.push_back(2);
	l1.push_back(3);

	list<int>::iterator iter = l1.begin();

	cout << *iter << endl; // 1

	// iter += 2; 불가능한 방법

	advance(iter, 2); // iter += 2와 같은 의미

	cout << *iter << endl; // 3
}

---

🔷 일반 반복자 & 상수 반복자

이 두 반복자들은 요소 접근과 요소 이동 가능이 서로 다르다.

• 일반 iterator
  ➡ 읽기, 쓰기(원소 변경), 원소 이동 가능

• const_iterator
  ➡ 읽기, 원소 이동 가능 / 반복자가 가리키는 원소의 값 변경 불가능

• const <T> iterator
  ➡ 쓰기 가능 / 반복자 자체가 const 객체

• const <T> const_iterator
  ➡ 불가능 / 반복자가 가리키는 원소의 값 변경 불가능 & 원소 이동 불가능

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


int main()
{
	vector<int> v;

	v.push_back(10); // [0]
	v.push_back(20); // [1]
	v.push_back(30); // [2]
	
	// 일반 반복자 (값 변경 o, 원소 이동 o)
	vector<int>::iterator iter = v.begin();
	*iter = 50;
	cout << *iter++ << endl;
	cout << *iter << endl;  

	// 상수 반복자 (값 변경 x, 원소 이동 o)
	vector<int>::const_iterator citer = v.begin();

	// *citer = 50;
	cout << *citer++ << endl;
	cout << *citer << endl;
	
	// const 일반 반복자 (값 변경 o, 원소 이동 x)
	const vector<int>::iterator constiter = v.begin();

	*constiter = 50;
	cout << *constiter << endl;
	// constiter++;

	// const 상수 반복자 (값 변경 x, 원소 이동 x)
	const vector<int>::const_iterator constciter = v.begin();

	//*constciter = 50;
	cout << *constiter << endl;
	// constiter++;

}

---