6. Iterators - 접근 인터페이스

// iter는 어떤 이터레이터이다.
// 이터레이터가 가리키는 요소의 값을 읽는다.
cout << *iter << endl;

// 이터레이터가 가리키는 요소의의 값을 수정한다.
*iter = 10;

// 다음 위치의 이터레이터가 된다.
iter++;

// 어떤 컨테이너의 시작 이터레이터와 끝의 다음 이터레이터를 반환하는 메서드
// 알고리즘은 내부적으로 이터레이터의 연산을 이용해 자신의 역할 수행한다.
sort(con.begin(), con.end());

// vector container의 이터레이터
std::vector<int> v{1,2,3};
auto b1 = v.begin();		// 1을 가리키는 이터레이터
auto e1 = v.end();			// 끝인 3의 다음을 가리키는 이터레이터

auto b2 = std::begin(v);	// 메서드가 아닌 함수로도 존재한다.
auto e2 = std::end(v);

// e1++;		// error!!  past-the-end의 다음은 없다.
// *e2;			// error!! past-the-end는 아무것도 가리키지 않는다.

#include<iostream>
#include<vector>
#include<set>

using namespace std;

int main() {
	vector<int> v{ 1,2,3,4,5 };
	
	auto iter = v.begin();
	while (iter != v.end()) {
		cout << *iter++ << ' ';
	}
	cout << endl;

	set<int> s{ 1,2,3,4,5 };
	if (s.find(10) == s.end()) {
		cout << "10은 s안에 존재하지 않음" << endl;
	} else {
		cout << "10이 s안에 존재함" << endl;
	}
}

vector<int> v{1,2,3,4,5};
for(auto i=v.begin(); i!=v.end(); i++) {
	*i -= 1;				// 0,1,2,3,4
}

// cbegin을 사용했으면 cend를 사용해야함에 주의할 것
for(auto i=v.cbegin(); i!=v.cend(); i++) {
	*i += 1; 				// ERROR!!!!! const는 수정할 수 없음.
}

for(auto i=v.rbegin(); i!=v.rend(); i++) {
	cout << *i << ' '; 		// 4 3 2 1 0
}

vector<int> v{1,2,3,4,5};
for(auto& i : v) {
	cout << i << ' ';  // 1 2 3 4 5
}

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

int main() {
	vector<int> v1{ 1,2,3,4 };
	vector<int>::iterator iter;

	// 1. 대입 연산
	iter = v1.begin(); // v1.begin()값을 읽어 iter에 쓴다.

	// 2. 역참조 읽기, 쓰기
	// 이터레이터가 가리키는 요소의 값에 접근한다.
	// 일부 이터레이터는 쓰기가 허용되지 않는다.
	*iter;			// vector의 첫 번째 요소인 1을 가리킨다.
	*iter = 10;		// vector의 첫 번째 요소인 1을 10으로 덮어 쓴다.
					

	// 3. 증감&감소
	// 일부 이터레이터는 감소를 지원하지 않는다.
	++iter;			// vector의 두 번쨰 요소를 가리킨다.
	iter++;			// vector의 세 번쨰 요소를 가리킨다.
	--iter;			// *iter == 2
	iter--;			// *iter == 10


	// random access 및 정수와의 연산
	iter = v1.begin();
	*(iter + 2);	// 3
	iter[2];		// 3

	iter = v1.end();
	*(iter - 1);	// 4 

	
	auto iter2 = v1.begin() + 2;
	// 동등성 비교
	iter == iter2;	// false
	iter != iter2;	// true

	// 대소 비교
	iter >= iter2;	// true
	iter <= iter2;	// false
	iter < iter2;	// true
	iter > iter2;	// false

	// 이터리이터간 덧셈 뺄셈
	iter - iter2;	// 2
	iter + iter;	// error!!!! 덧셈은 불가능.
}

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
	// sort는 오름차순으로 정렬한다.
	// 일반적인 사용법
	vector<int> v1{ 3,1,4,5,2 };
	sort(v1.begin(), v1.end());			// 1 2 3 4 5

	// vector의 부분적인 범위만 사용
	vector<int> v2{ 5,4,3,1,2 };
	sort(v2.begin(), v2.begin() + 2);	// 4 5 3 1 2

	// 정렬은 이터레이터간의 순서에 따라서 수행됨.
	// 역순인 이터레이터를 사용해 역순으로 오름차순 정렬이 된다. (내림차순)
	vector<int> v3{ 1,2,3,4,5 };
	sort(v3.rbegin(), v3.rend());	// 5 4 3 2 1

	// 포인터를 이터레이터로 사용.
	int arr[] = { 8,1,5,4,2 };
	sort(arr, arr + 5);					// 1 2 4 5 8
}

#pragma once

// 단일 연결 리스트의 노드
template<class T>
struct Node {
	T data;
	Node* next = nullptr;
	Node(T data) : data(data) {};
};

template<class T>
class LinkedList {
private:
	Node<T>* head = nullptr;
	int size = 0;

public:
	// LinkedList 내부에 정의된 이터레이터
	class iterator {
	private:
		Node<T>* ptr;
	public:
		iterator(Node<T>* ptr) : ptr(ptr) {};

		// 역참조 연산 정의
		T& operator*() { return this->ptr->data; }

		// 전위 증감 연산자 정의
		iterator& operator++() {
			if (ptr) ptr = ptr->next;
			return *this;
		}

		// 비교 연산 정의
		bool operator!= (const iterator & other) const {
			return ptr != other.ptr;
		}
		bool operator== (const iterator& other) const {
			return ptr == other.ptr;
		}
	};

public:
	~LinkedList() {
		while (head) {
			Node<T>* temp = head;
			head = head->next;
			delete temp;
		}
	}
	T& get(int index) {
		if (index >= size) throw "out of range";
		auto iter = this->begin();
		for (int i = 0; i < index; i++) { ++iter; };
		return *iter;
	}
	Node<T>* append_front(T val) {
		auto node = new Node(val);

		if (this->head) {
			node->next = head;
		}

		this->head = node;
		this->size++;
		return node;
	}
	
	// 이터레이터를 반환하는 메서드
	iterator begin() { return iterator(this->head); }
	iterator end() { return iterator(nullptr); }
};

#include<iostream>
#include<algorithm>

#include"LinkedList.h"

using namespace std;

int main() {
	LinkedList<int> list;
	list.append_front(1);
	list.append_front(2);
	list.append_front(3);
	list.append_front(4);
	list.append_front(5);

	for (auto iter = list.begin(); iter != list.end(); ++iter) {
		cout << *iter << ' ';			// 5 4 3 2 1
	}
	cout << endl;

	cout << list.get(2) << endl;		// 2

	// error : 비교 및 대입 관련된 연산 요구사항이 충족되지 않음.
	// sort(list.begin(), list.end());	

	// 데이터를 채우는 함수
	fill(list.begin(), list.end(), 1);

	for (auto i : list) {
		cout << i << ' ';				// 1 1 1 1 1
	}
}