std::array, std::vector등과 같은 연속된 자료구조에서는

중간 데이터 추가/삭제 하는 작업이 비효율적이다.

그래서 연결리스트와같은 형태의 자료구조가 등장.

• ostream

  https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=kks227&logNo=220221664888

forward_list

단일 연결 리스트를 구현해놓은 wrapper이다.

• 성능 유지를 위하여 전체리스트 크기 반환 X

• 첫번째 원소를 제외한 나머지 원소에 직접 접근 X

• 반대방향으로 이동하는 것 허용 X

forward_list는 마지막 원소에직접 접근 불가능 -> push_back 제공하지 않는다.

특정 위치에 원소를 삽입할려면 insert가 아니라 insert_after()함수 사용해야한다.

이는 연결형 리스트에서 새로운 원소를 삽입후 해당 위치 앞에 있는 원소의 next 포인터를 수정해야하기 때문이다.

O(1)의 시간복잡도를 가진다.

삭제

• erase_after() : 시간 복잡도는 삭제할 원소 개수의 선형함수 형태로 나타낸다.

  연결 리스트에서 각각의 노드는 전체 메모리의 임의 위치에 산재되어 있으며, 각각의 노드에 사용된 메모리를 개별적으로 해제해야하기 때문이다.

std::forward_list<int> fwd_list = {1, 2, 3, 4 ,5};

fwd_list.pop_front(); // 맨앞 원소 삭제

auto it = fwd_list.begin();

fwd_list.erase_after(it, fwd_list.end()); // 맨앞 원소 다음부터 맨 마지막 원소까지 삭제

기타 멤버 함수

erase말고 조건 검사를 하여 삭제할 수 있는 기능인 remove(), remove_if() 함수를 제공한다.

remove()

삭제할 원소 하나를 매개변수로 받는다.

이 함수는 저장된 데이터 타입에 정의된 등호 연산자를 사용하여 전달된 값과 일치하는 모든 원소를 찾아 삭제한다.

저장된 데이터에 등호 연산이 지원되지 않으면 remove()함수 사용불가능.

(즉, 직접 정의한 자료형 같은 경우 등호 연산자를 지원해주어야한다)

그래서, 보다 유연한 조건분 삭제를 진행을 하기 위해서는

remove_if() 사용이 가능하다.

remove_if()

데이터 원소 값 하나를 인자로 받아 bool값을 반환하는 조건자 함수를 인자로 받는다.

그리고 조건자가 true를 반환하는 모든 데이터 원소를 리스트에서 삭제를 진행한다.

이 조건자 자리에 람다 표현식을 사용할 수 있다.

이후 remove_if의 조건자 자리에 람다 표현식을 사용을 해보면은

이렇게 리스트에서 삭제가 된다.

remove_if는 주어진 조건에 대해 참을 만족하는 모든 원소를 제거한다.

remove, remove_if 함수는 리스트 전체를 순회를 하면서 조건에 맞는 모든 원소를 삭제를 진행하기 때문에

O(n)의 시간 복잡도를 가진다.

정렬

forward_list는 특정 원소에 임의 접근이 불가능 하므로 std::sort() 함수를 사용할 수 없다.

(메모리가 연속적이지 않아서)

std::forward_list에서 제공하는 sort() 함수는 두 가지 형태를 지원한다.

하나는 < 연산자를 기반으로 정렬하고,

하나는 매개변수로 전달된 '비교자(compartor)' 사용한다.

---

기본 sort()함수는 std::less<value_type>을 비교자로 사용한다.

이 비교자는 첫번째 인자가 두번째 인자보다 작으면 true를 반환하고, 사용자 정의 타입 원소를 사용할 경우에는 < 연산자가 재정의 되어 있어야한다.

아무튼 이 std::forward_list의 두가지 형태의 sort() 함수는 모두 선형 로그 시간 복잡도 O(n logn)을 가진다.

std::forward_list<int> list = {23, 0, 1, -3, 34, 32};

list.sort(); // -3, 0, 1, 23, 32, 34 순으로 정렬

list.sort(std::greater<int>()); // 34, 32, 23, 1, 0, -3 순으로 정렬

std::grearter< int >

표준으로 제공되는 비교 함수 객체

현재는 리스트에서 확인할 수 있듯, 원소를 내림차순으로 정렬하기 위한 > 연산자에 대한 wrapper이다.

https://itguava.tistory.com/67 참고

다양한 멤버 함수

• reverse() : 지정된 원소의 순서를 역순으로 변경, 시간복잡도 -> 원소의 개수에 비례 O(n)

• unique() : 리스트에서 홀로 나타내는 원소는 놔두고 인접하여 중복되는 원소에 대해서는 첫번째만 남겨두고 나머지는 제거.

  인자가 없는 형태, bool값을 반환하는 이항 조건자를 인자로 받는 두가지 버젼 제공

  이 함수는 서로 인접한 원소끼리 같은지를 판단하고, 만약 같다면은 앞에 있는 원소는 남기고 뒤에 있는 원소를 제거를 하기 때문에, 리스트 전체에서 유일한 원소들만 남게하고 싶다면은 먼저 리스트를 정렬후 unique()함수를 호출해야한다.

반복자 iterator

STL 컨테이너 (자료구조) 대해 공통의 인터페이스를 제공을 한다.

vector, array는 연속된 자료구조를 사용하기 때문에 특정 위치의 원소에 바로 접근이 가능하다.

이러한 반복자를 임의 접근 반복자(random access iterator) 라고한다.

하지만 forward_list의 경우 역방향으로 이동하는 기능 지원 X.

이전 노드로 되돌아 갈려면은 맨 처음 노드부터 다시 시작해야한다.

따라서 std::forward_list의 경우 증가 연산만 가능하며, 이러한 반복자를 순방향 반복자(forward iterator)라고함.

iterator function

• advance() : 반복자와 거리 값을 인자로 받고, 반복자를 거리 값만큼 증가시킨다.

• next(), prev() : 반복자와 거리 값을 인자로 받고, 해당 반복자에서 지정한 거리만큼 떨어진 위치의 반복자를 반환한다.

주의할 점은 해당 iterator가 지원할 경우에만 동작한다.

forward_list에서는 prev() 사용을 못한다. -> 컴파일 에러.

ex)

random access iterator에서는 +, - 연산지 "상수 시간"으로 동작하므로

next(), prev() 함수도 상수 시간 O(1)으로 동작을 한다.

vector와의 연산 속도 비교

vector는 특정원소에 즉각 접근이 가능하다.

그래서 vector::iterator의 덧셈과 뺄셈 연산은 O(1)이다.

반면 std::forward_list의 경우 연속적인 순회를 통해서만 특정원소에 접근이 가능하다.

메모리가 연속적이지 않다.

힙에 여기저기 흩어져있다.

따라서 시간 복잡도는 O(n)이고 n은 순회할 횟수이다.

문제 구현 ❗❗

• 함수 이름 뒤 const

  
  https://ladun.tistory.com/19#:~:text=%ED%95%A8%EC%88%98%EB%AA%85%20%EB%92%A4%EC%97%90%20const,-class%20CMyClass%20%7B%20public&text=%ED%95%A8%EC%88%98%EC%9D%98%20%EB%92%A4%EC%97%90%20const%EA%B0%80,%EC%9D%84%20%EB%B3%80%EA%B2%BD%ED%95%A0%20%EC%88%98%20%EC%97%86%EA%B2%8C%20%EB%90%9C%EB%8B%A4.

• 생성자() = default

  https://woo-dev.tistory.com/100

• initializer_list

  https://ansohxxn.github.io/cpp/chapter9-13/

  

위의 세가지 개념이 내가 문제를 forward_list를 구현하면서 몰랐던 개념들이다. 숙지를 하도록 하자.

struct singly_ll_node
{
	int data;
	singly_ll_node* next;
};

class singly_11
{
public:
	using node = singly_ll_node;
	using node_ptr = node*;

public:
	singly_11() = default;
	singly_11(const singly_11& other) : head(NULL)
	{
		std::cout << "복사 생성자 호출" << std::endl;
		if (other.head)
		{
			head = new node{ 0, NULL };
			auto cur = head;
			auto it = other.begin();
			while (true)
			{
				cur->data = *it;
				auto tmp = it;

				++tmp;
				if (tmp == other.end())
					break;
				
				cur->next = new node{ 0, NULL };
				cur = cur->next;
				it = tmp;
			}
		}
	}

	singly_11(const std::initializer_list<int>& ilist) : head(NULL)
	{
		std::cout << "initializer_list 생성자 호출" << std::endl;

		for (auto it = std::rbegin(ilist); it != std::rend(ilist); ++it)
		{
			push_front(*it);
		}
	}
	
private:
	node_ptr head;

public:
	void push_front(int val)
	{
		auto new_node = new node { val, NULL };

		if (head != NULL)
			new_node->next = head;
		head = new_node;
	}
	
	void pop_front()
	{
		auto first = head;
		if (head)
		{
			head = head->next;
			delete first;
		}
	}

	class singly_ll_iterator;
	singly_ll_iterator begin() { return singly_ll_iterator(head); }
	singly_ll_iterator end() { return singly_ll_iterator(NULL); }
	singly_ll_iterator begin() const { return singly_ll_iterator(head); }
	singly_ll_iterator end() const { return singly_ll_iterator(NULL); }


	class singly_ll_iterator
	{
	private:
		node_ptr ptr;
		
	public:
		singly_ll_iterator(node_ptr p) : ptr(p) {}

	public:
		int& operator * () { return ptr->data; }
		
		singly_ll_iterator& operator ++()
		{
			ptr = ptr->next;
			return *this;
		}
		singly_ll_iterator operator ++ (int)
		{
			singly_ll_iterator result = *this;
			++(*this);
			return result;
		}
		
		bool operator == (const singly_ll_iterator& right) { return this->ptr == right.ptr; }
		bool operator != (const singly_ll_iterator& right) { return !(this->ptr == right.ptr); }

		node_ptr get() { return ptr; }

		friend class singly_ll_iterator;
	};
};

	singly_11 sll = { 1, 2, 3 };
	sll.push_front(0);

	std::cout << "첫 번째 리스트 : ";
	for (auto it : sll)
		std::cout << it << " ";
	std::cout << std::endl;

	auto sll2 = sll; // 복사 생성자 호출
	sll2.push_front(-1);

	std::cout << "첫 번째 리스트를 복사한 후, 맨 앞에 -1 추가 : ";
	for (auto it : sll2)
		std::cout << it << " ";
	std::cout << std::endl;

	std::cout << "깊은 복사후 첫 번째 리스트 : ";

	for (auto it : sll)
		std::cout << it << " ";
	std::cout << std::endl;
  

이제 실행을 해주게 되면은

알아야 할 점

std::initializer_list를 통해 연결 리스트를 초기화 하는 방법을 사용하였다.

도한 sll2가 깊은 복사에 의해 생성되었기 때문에 sll2에 원소를 추가를 하여도 sll의 리스트에는 여전히 4개의 원소가 남아있게 된다.