C++ 에서의 자료구조 forward_list를 쓰는 이유

배열과 벡터같은 얀속된 자료 구조에서는...

임의의 위치에서 삽입 삭제가 비효율적이고 말할 수 있다.

 

즉, 연결된 자료구조를 C++이 제공하느냐??

**list도 있지만 list에서 뺄 것을 빼서 기름기가 쫙빠진 것이 forward_list라고 할 수 있다.

 

그렇다. 제공한다. 그것이 바로 forawrd_list이다.

 

연결리스트의 성능은 유지하면서 추가적인 기능을 제공한다.

 

하지만 성능 유지를 위해 임의의 위치에 대한 직접 접근을 허용하지 않으며

전체 리스트의 크기를 바로 알 수는 없다.

 

즉, 맨 처음 원소에 접근하는 front()는 제공하지만 맨 뒤의 원소에 접근하는 back()같은 것은 지원하지 않는다.

 

그리고 연결된 구조와 연속된 구조의 iterator, 반복자는 종류가 다름을 생각하자

 

 

 

---

 

forward_list에서는 원소 삽입 시

push_front()와 insert_after() 함수를 사용한다.

말 그대로 처음에 원소를 삽입하는 것과 임의의 위치에 원소를 삽입하는 것이다.

 

**아래 코드는 최소한만 남겼다.

  forward_list<int> mylist = {77, 2, 16};
  mylist.push_front (19);
  mylist.push_front (34);

///////////////////////////

mylist contains: 34 19 77 2 16

  std::array<int,3> myarray = { 11, 22, 33 };
  std::forward_list<int> mylist;
  std::forward_list<int>::iterator it;

  it = mylist.insert_after ( mylist.before_begin(), 10 );          // 10
                                                                   //  ^  <- it
  it = mylist.insert_after ( it, 2, 20 );                          // 10 20 20
                                                                   //        ^
  it = mylist.insert_after ( it, myarray.begin(), myarray.end() ); // 10 20 20 11 22 33
                                                                   //                 ^
  it = mylist.begin();                                             //  ^
  it = mylist.insert_after ( it, {1,2,3} );                        // 10 1 2 3 20 20 11 22 33
                                                                   //        ^

 

위 둘의 함수는 시간복잡도가 O(1)이라고 할 수 있다.

 

또한 이 연결리스트도

emplace_front()와 emplace_after() 함수도 제공하므로 성능을 위해서 사용해도 좋다.

 

 

---

삭제는 어떻게 할까?

pop_front()와 erase_after()를 제공한다.

역시나 앞에서 삭제하는 것과 ~이후로 제거하는 것이다.

 

std::forward_list<int> mylist = {10, 20, 30, 40};

  std::cout << "Popping out the elements in mylist:";
  while (!mylist.empty())
  {
    std::cout << ' ' << mylist.front();
    mylist.pop_front();
  }
  
  ////////////////////
  Popping out the elements in mylist: 10 20 30 40

std::forward_list<int> mylist = {10, 20, 30, 40, 50};

                                            // 10 20 30 40 50
  auto it = mylist.begin();                 // ^

  it = mylist.erase_after(it);              // 10 30 40 50
                                            //    ^
  it = mylist.erase_after(it,mylist.end()); // 10 30
                                            //       ^

 

pop_front()는 O(1)의 시간복잡도를 가진 반면에

erase_after()는 함를 사용하여 뒤의 일련의 원소를 삭제하는 과정에서 O(N)의 시간복잡도를 가진다.

전체 메모리에서 퍼져있는 노드를 개별적으로 해제해야하기 때문이다.

 

---

 

나머지 기타 함수들로는

ㅇremove(), remove_if() 함수도 있다.

remove()는 삭제할 원소 값 하나를 매개변수라 받아서 이 원소 값과 일치하는 모든 원소를 삭제한다.

 

  std::forward_list<int> mylist = {10, 20, 30, 40, 30, 20, 10};

  mylist.remove(20);

//////////////////
mylist contains: 10 30 40 30 10

 

remove_if()는 조건부삭제 함수다.

원소 값 하나를 매개변수로 받아 bool 값을 반환하는 조건자를 입력으로 받아서 true인 것들은 삭제하는 함수다.

bool single_digit (const int& value) { return (value<10); }


  std::forward_list<int> mylist = {7, 80, 7, 15, 85, 52, 6};

  mylist.remove_if (single_digit);      // 80 15 85 52

 

이 remove 함수들은

리스트 전체를 순회하기 때문에 O(N)의 시간 복잡도를 갖는다.

 

또한 forward_list는 sort() 멤버함수도 가지는데

우리가 쓰는 일반적인 sort와는 다르다. 왜냐하면 iterator종류가 다르기 때문이다.

std::sort()와 std::forward_list::sort()의 차이다.

 

하지만 sort의 역할은 똑같다.

std::forward_list<int> mylist = {22, 13, 5, 40, 90, 62, 31};

  mylist.sort();

  mylist.sort(std::greater<int>());


  ////////////////////////
  
  default sort (operator<): 5 13 22 31 40 62 90
  sort with std::greater(): 90 62 40 31 22 13 5

 

마지막으로

reverse()와 unique() 함수가 있다.

reverse()는 이름과 같이 현재 연결된 원소 순서를 역순으로 바꾸는 함수이고

unique()는 리스트에서 연속되는 원소가 발견되어 그룹이 있을 때는 리더만 남기고 지워버리는 것이라 생각하면 편하다.

EX) 111233314 -> 12314

 

 

---

 

 

임의의 위치에서 삭제와 삽입이 빈번하게 일어난다면

연결리스트를 사용하는 것이 좋다.

또한 크기의 제약이 배열에 비해 적다는 장점이 있다.

하지만 노드 하나의 크기에 data와 pointer가 같이 있기 때문에

배열보다 메모리를 더 먹는다고 말할 수 있다.