STL

standard template library

• STL est compose en gros par container, iterator et algo(global function).
• algo accede a container avec iterator.
• container est compose par sequence container, associative container et adapter container.

---

Iterator

Iterator indique un element dans container comme pointer.

• InIt, OutIt, FwdIt, BiIt et RanIt.
  ( la raison pour laquelle les iterators sont divisee en 5, c'est pour limiter la function.)

---

Input Iterator

• 가장 기본적인 기능만 제공하는 반복자.
• 컨테이너의 한 위치를 가리키는것.
• 반복자가 가리키는 위치의 요소를 * 연산자로 읽을수있다.
• ++연산자, != 연산자.
• 예) find 함수

---

Output Iterator

• copy 알고리즘에서의 입력부분.
• ++연산자.
• copy 함수에서의 * it = a 부분.

---

Foward Iterator

• 읽고 쓰기 모두가능.
• ++연산자.
• 한 위치를 여러 번 읽고 쓸수있기 때문에, 다중 패스 알고리즘을 지원.
• 전진기능만 지원하고, 후진은 불가능.
• replace 함수 : old값을 순회하며 찾아, new 값으로 교체. :++, 읽기, 쓰기.

---

Bidirectional Iterator

• 역방향으로도 이동 가능한 반복자.
• ++연산자, --연산자.
• reverse 함수. : 구간내의 요소들을 반대로 뒤집어 재배치, 양쪽끝에서 동시에 순회하여 재배치 : 양방향, 읽기, 쓰기.

void main()

{

     int ari[]={1,2,3,4,5,6,7};

     list<int> li(&ari[0],&ari[7]);



     list<int>::iterator it=li.begin();

     printf("%d\n",*it);                      // 읽을 수 있다.

     printf("%d\n",*(++it));                 // 한칸 전진 가능

//  printf("%d\n",it[3]);               // 에러:임의 위치를 읽지는 못함

//  it+=3;                                    // 에러:임의 위치로 이동하지 못함

     advance(it,3);                            // advance로 이동 가능

     printf("%d\n",*it);

//  printf("거리=%d\n",li.end()-li.begin());                 // 에러:반복자끼리 뺄셈은 안됨

     printf("거리=%d\n",distance(li.begin(),li.end()));   // distance로 거리를 구하는 것은 가능

}

리스트 컨테이너가 제공하는 양방향 반복자는 +n을 지원하지 않으므로 [ ] 연산자로
임의 위치를 읽거나 +=n으로 임의 위치로 이동할 수 없으며 반복자끼리 뺄셈을 할 수도
없다.
그러나 advance와 distance 함수를 사용하면 가능하기는 하다. 실행 결과는 다음과 같다.

1

2

5

거리=7

void advance(InIt &first, int off)

{

     for (;off > 0;--off) { ++first; }

     for (;off < 0;++off) { --first; }

}

임의 접근 반복자는 it[30000]을 한 번에 바로 찾아 가지만
양방향 반복자는 다음 링크 찾아 3만리를 가야 하므로 진정한 의미의 +n 연산을 지원한다고 볼 수 없다.
advance와 distance는 꼭 필요할 경우에 사용할 수는 있지만 n이 커지면 효율이 떨어진다는 점을 알아야 한다.

---

Random Iterator

• • 연산자로 읽기.
• 읽기, 쓰기.
• ++연산자, --연산자.
• 같은위치를 여러번 엑세스 하기.
• 임의 위치로 이동. ( iterator + n 연산 가능 -> * (it + n) 가능 );
  : 컨테이너의 요소들의 크가가 같고 연결해있기때문이다.
• 임의 접근 반복자는 단순히 임의 접근이 가능하다는 정도로 정의하는것 보다는,
  상수 시간내에 원하는 곳으로 즉시 이동할수있는 반복자이다. (위의 양방향과는 다름)

---

반복자와 알고리즘

상위의 반복자는 하위 반복자의 기능을 포함하므로 하위 반복자를 요구하는 알고리즘에는
더 상위의 반복자를 항상 사용할 수 있다.
양방향 반복자는 입력이나 순방향을 요구하는 알고리즘에 별 제약없이 사용할 수 있으며 임의 접근 반복자는 모든 알고리즘에 사용 가능하다.

• 입력, 출력반복자는 배타적이며 서로 포함관계가 아니다.
• 순방향 반복자는 입력, 출력 반복자의 기능을 포함하며 여기에 같은 위치를 여러 번
  액세스 하는 기능을 추가로 가진다.
  순방향 반복자는 입력, 출력을 겸하므로 InIt, OutIt를 요구하는 알고리즘에도 사용할 수 있다.
• 양방향 반복자는 순방향 반복자의 기능에 역방향으로 이동하는 -- 연산자를 추가로 가진다.
• 임의 접근 반복자는 양방향 반복자에 +n 연산을 추가로 정의하며 이 연산이 추가됨에 따라 [ ], += 등도 가능해진다.

반복자의 속성 (Iterator_traits)

알고리즘 함수들은 임의의 컨테이너에대해 동작하므로, 반복자만 인수로 전달받을뿐,
컨테어너에 대해서는 알지못한다.
알고리즘이 인수로 반복자만을 받았을때, 이 반복자만 가지고 특성을 파악하는방법?
InIt, BiIt, RanIt등은 문서화를 위한 분류방법일뿐, 컴파일러가 인식하는 타입은 아니다.
알고리즘의 함수로 전달되는 반복자는 통상 템플릿의 인수이며 임의의 모든 타입이 전달될수 있으므로, 이 타입만 가지고는 반복자의 종류를 알아낼수없다.
심지어는 반복자인지 정수인지 조차도 분간할수없다.
하지만 반복자의 특징이 필요한경우, 특징을 표현하기위해 iterator_traits 클래스와이 클래스를 보조하는 여러가지 타입정보를 정의한다.

template<class Iter>

struct iterator_traits {

     typedef typename Iter::iterator_category iterator_category;

     typedef typename Iter::value_type value_type;

     typedef typename Iter::difference_type difference_type;

     typedef typename Iter::pointer pointer;

     typedef typename Iter::reference reference;

};

Iterator_traits 클래스는 멤버를 가지지않고 타입만 정의하는 빈 클래스이다.

• iterator_category는 반복자의 종류를 지정한다.
• value_type은 반복자가 가리키는 대상체의 타입이다.
• difference_type은 반복자끼리의 거리를 표현하는 타입이다.

반복자 타입 Iter를 템플릿인수로 전달하면 Iter 반복자가 정의하는 타입을 약속된이름으로 재정의 하는 역활을 할뿐이다.

반복자의 종류는 다음과 같이 태그 이름이 정의되어있다.

struct input_iterator_tag {};

struct output_iterator_tag {};

struct forward_iterator_tag : public input_iterator_tag {};

struct bidirectional_iterator_tag : public forward_iterator_tag {};

struct random_access_iterator_tag : public bidirectional_iterator_tag {};

모두 멤버를 가지지않은 빈 구조체이다. 또한 일종의 개념적인 상속계층을 구성하고있다.

각 컨테이너별로 정의되어 있는 반복자 타입들은 iterator_traits 클래스가 요구하는
타입들을 개별적으로 정의한다.

컨테이너 별로 반복자의 특징이 달라지므로 이 타입들은 매 컨테이너마다 달라질것이다.

예) 벡터와 리스트의 반복자클래스가 iterator_traits의 타입을 정의.

class vector_iterator {
	typedef random_access_iterator_tag	iterator_category;
	typedef T value_type;
};

class list_iterator	{
	typedef bidirectional_iterator_tag	iterator_category;
	typedef T value_type;
};

• 벡터는 iterator_category 타입을 random_access_iterator_tag 타입으로 정의하여 자신이 임의접근 반복자라는것을 표시하고있다.
• value_type T는 벡터의 템플릿 인수로 전달된 타입이된다.
  ( vector 타입에서 Int가 곧 T로 전달되므로, 반복자의 대상체도 int가 된다.)
• 리스트의 반복자는 양방향 반복자이며 대상체의 타입은 역시 템플릿 인수로 전달된 T이다.

각 반복자가 클래스가 이렇게 자신의 정체와 자신과 관련되 타입을 약속된 이름으로 밝혀놓으면,
iterator_traits 클래스는 이 이름들을 "외부에서 일관되게 사용할수있도록 제공"한다.
예를 들어, 벡터에 대한 반복자와 리스트에 대한 반복자가 있을 때, 반복자를 iterator_traits의 인수로 전달하면 반복자에 대한 여러가지 특징을 얻을수있다.

vector<int>::iterator vit;
list<int>::iterator lit;

iterator_traits<vit>::iterator_category;	//	임의접근이다.
iterator_traits<lit>::iterator_category;	//	양방향이다.
iterator_traits<vit>::value_type;			//	정수를 가리킨다.

이런정보들을 사용하면, "알고리즘을 반복자 종류에 맞게 최적화"시킬수 있다.
대표적으로 반복자 사이의 거리를 구하는 distance알고리즘의 구현코드이다.
두 반복자의 거리를 구하는 방법은 반복자가 어떤 연산을 제공하는가에따라 달라지는데,
입력, 순방향, 양방향 반복자인경우에는 다음과같이 구한다.

template<typename InIt>
void	distance_impl(Init first, Init last, input_iterator_tag)
{
	int	d = 0;
	while (;first != last; ++first)
		++d;
	return d;
}

반복자끼리 연산 할수 없기때문에, first가 last가 될때까지 루프를 돌면서 카운트해야한다.

그러나 임의 접근반복자의 경우는 다음과 같다.

template<typename RanIt>
void	distace_impl(Ranlt first, RanIt last, random_access_iterator_tag)
{
	return last - first;
}

반복자의 종류에 따라, distance_impl이라는 두 함수를 "오버로딩"해놓았다.
세번째 인수인 태크타입이 다르기 때문에 오버로딩 조건을 만족한다.

결국 반복자 태크라는것은 어떤 중요한 정보를 담는 구조체가 아니라,
" 단순히 타입만을 정의함으로써, 오버로딩된 함수중 적절한 함수를 선택하는 역활"
을 한다.
이 선택에 관하여서는

• 클래스는 모두 빈 클래스이므로 단 1바이트도 불필요하게 사용되지 않았다.
• 타입이란 컴파일 중에만 사용되는 정보이며, 모든 선택은 "컴파일" 중에 일어나므로 실행시의 "효율감소도 전혀없다".

distance 함수의 구현코드

int distance(Iter first, Iter last) {

     if (반복자가 입력용이면) {

          하나, 둘, 셋, 넷 열심히 세서 리턴

     } else {

          뺄셈만 하면 됨.

     }

}

if문 안에 있는 조건 판단을 위해 반복자의 타입만으로 특징을 조사할수있는 방법이 필요하다.
itertor_traits 클래스와 반복자에 "컴파일러가 인식할수있는 타입을 정의함으로써 특징을 판별할수 있도록" 한다.

상수반복자

안전한 참조를 위해, 포인터나 레퍼런스에 상수성을 줄수있듯이 반복자도 상수성을 가질수있다.
비상수 반복자는 레퍼런스를 리턴하므로, * 연산자와함께 대입식의 좌변에 사용될수있따.
하지만 상수 반복자는 "상수 레퍼런스"를 리턴하므로 대입식의 좌변에 놓아 값을 변경할수없고 오로지 읽을수만있다.

• const_iterator 타입으로 정의되어있다.
• 상수반복자가 가리키는 대상이 상수이다. 반복자는 변경가능. (const char * 와 같음)
• 컨테이너의 begin, end 멤버함수는 상수, 비상수 버전으로 오버로딩되어있다.
• 비상수는 항상 상수에 대입할수있으므로, 비상수 반복자도 상수반복자에 대입가능.
  예)

vector vi; // 읽기, 쓰기
vector::const_iterator cit = vi.begin(); // 읽기만 가능

---

# Tempalte
> 무엇인가를 만들기 위한 형틀. 오버로딩을 일반화한다.



---

# Vertor
> Vector est un container dans "Standard Template Library".

## les avantages de Vector
> array variable.
1. on peut ajouter les éléments en dynamique et la taille est automatiquement augmentée.
2. meme si la vitesse est lente par rapport a "array", Vector est utilisé beaucoup avec l'avantage de pouvoir bien gérer la mémoire.


## la Structure de Vector
> Vector est crée dans Heap et alloué dynamiquement.

<img width="641" alt="스크린샷 2022-04-27 오후 2 17 42" src="https://user-images.githubusercontent.com/71254925/165516272-bdc456b0-b1b2-4288-b8fe-6de2b8183568.png">

front() : premier élément.
back() : dernier élément.
begin() : premier emplacement.
end() : dernier emplacement suivant.
size() : le numbre des éléments.
capacity() : la taille d'espace alloué

## La différence entre "Capacity" et "Size"
> il est inefficace d'allouer une nouvelle mémoire a chaque fois qu'un élément arrive.
par conséquent, le vector est configuré que l'espace de mémoire supplémentaire est alloué lorsque de nouveux éléments sont ajoutés au vector.
- si la capacité est insuffisante, la capacité est augmentée de "la moitié de la capaticé".
- si le nombre de capacité est déja fixé, le vector est alloué plus efficacement en résevant l'espace.

## utilisation de "Vector"

```cpp

vector<int> v;	// création de vector
vercot<int> v = {1, 2, 3}; // création de vector et intialisation avec 1, 2 et 3
vector<int> v[10];	// création de vector en 10 de capacité
vector<int> v[] = { {1, 2}, {3, 4}};	//	création d'array de vector avec ligne variable et avec colone fixé
vector<vector<int>> v;	// création de double array de vector avec ligne et colone variable
vector<int> v(5);	// création de vector et 5 taille de 0
vector<int> v(5, 3);	// création de vector 5 taille de 3
vector<int> v2(v);	// création de vector v2 en copyant de v

ajouter l'élément de vector

pour ajouter l'élément.

• au début : insert sans "index" : insert(index, value)
• au milieu : insert avec "index" : insert(value), insert( iterator de premiere position, value)
• a la fin : push_bach(value)

v.push_back(10);	// ajouter 10 a la derniere position

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

it = v.insert(it, 2);	// ajouter 2 au début
it = v.insert(it, 2, 3);	// ajouter 3 en deux fois au début
it = v.insert(it + 2, 2, 4);	// ajouter 4 en deux fois au deuxeme position

effacer l'élément de vector

pour effacer l'élément

• effacer un élément : eraser(index)
• effacer les élément : eraser(index, index)
• effacer le dernier élément : pop_back()
• effacer tous les éléments : clear()

v.pop_back();	// effacer l'élément a la fin

v.eraser(vec.begin() + 10);	// effacer 10 eme élément
v.eraser(vec.begin(), vec.begin() + 5);	// effacer les éléments de 0 a 5

v.clear();	// effacer tous les éléments, mais la capacité reste

imprimer les éléments de vector

imprimer avec "index"

for (int i = 0; i < v.size(); i++)
	std::cout << v[i] << std::endl;

std::cout << v[2] << std::endl;	// imprimer la valeur de index 2
std::cout << v.front() << std::endl;	// imprimer le premier élément
std::cout << v.back() << std::endl;	// imprimer le dernier élément

imprimer avec "iterator"

// sortie dans l'ordre
for (auto i = v.begin(); i != v.end(); i++)
	std::cout << *i << std::endl;

// sorite dans l'ordre inverse
for (auto ir = v.rbegin(); ir != v.rend(); i++)
	std::cout << *ir << std::endl;