C++ STL Sequence Container

-Sequence Container란?

 *container= 기본자료형과 사용자가 정의한 자료형을 담는 자료구조 

 *Sequence= 배열과 같이 입력한 순서대로 저장하여 정렬이 돼있지 안은 자료구조이다

 

 c++ stl중 지원하는 Sequence Container의 종류는  

   > vector https://zero-stone.tistory.com/22

   > deque https://zero-stone.tistory.com/25

   > list  https://zero-stone.tistory.com/23

   > forward_list https://zero-stone.tistory.com/24

 로 이루어져있다. (궁금하면 링크 참조) 

 

-특징

   1) vector 

      vector는 배열로 구현된 자료구조이다.

      크기가 자유자재로 늘어나는 배열이라 생각하면된다.

     

      그래서 다른 컨테이너들중 유일하게 iterator가아닌 pointer를 통해서 접근과 연산이 가능하다.

      또한 push_back을 이용해 끝쪽에 넣어주는 작업이 매우빠르다.

      (장점)

     

       하지만 vector의 용량을 늘릴  때 기존 배열을 재할당 배열에 복사하는 과정으로 인해 비용이 많이든다.

       또한 끝이 아닌 중간에 insert하면 값을 복사 하여 이동시키는 비용이 발생한다.이러한 경우는 list가 유리

       (단점) 

    

    2) deque

         deque도 vector와 마찬 가지로 배열 기반 자료구조이다.

         하지만 deque은 모든 원소가 연속적인 메모리 공간에 존재 하지 않는다. 

         ( 메모리를 블록 단위로 할당하여 추가 공간 필요시 추가 블록을 할당 받는다. 이때 블록들이 연속적으로 존재

          하지 않는다.)

          vector와 같이 중간 삽입시 복사하여 이동시키는 비용이 발생한다.

          (단점)

 

          반면 용량 초과시 vector와 달리 블록을 추가 할당 받아 복사 과정이 존재x , 

          push_front,push_back을 이용해 양 끝쪽에 넣어주는 작업 매우빠르다. (장점)

   

          *vector vs deque 

 

            두 컨테이너 선택 기준은 push_front ,push_back이 필요하냐 아니냐로 따지면 된다.

            그럼으로 front에 삽입 삭제가 필요하다면 deque! 아니면 vector!

 

3) list & forward_list

   list(forward_list)는 노드로 이루어진 자료구조로 노드들끼리 양방향(단반향)포인터로 연결돼있는 자료구조이다.

   메모리상에 순서대로가 아닌 뒤죽박죽 섞여있다.

 

 * vector&deque vs list(forward_list)

   vector, deque와의 차이는 양방향(순방향) iterator를 사용하여 ++,--,*,->만 지원된다.

   (iterator와 인덱싱 둘다 []지원X )

 

   그럼으로 원하는 노드에 접근하는데O(N) 많은 비용이든다.

   또한 포인터를 보유하여 메모리 공간을 vector와 deque에 비해 많이 차지한다. (단점)

 

    반면 중간지점에서의 insert,erase는 링킹하고있는 pointer를 바꿔주는 작업만 하면돼서 이 경우에는 vector와deque      보다 성능이 좋다.(장점)

  

     *forward_list

 

      forward_list는 단방향(전방)포인터만으로 구현되었다.

      list보다 insert,erase속도 및 저장 공간 측면에서 효율적인 자료구조다.

      하지만 단방향 iterator이기 때문에  --는 지원하지 않는다.

      이러한 이유로 양방향 이동이 필요한 경우에는 list를 사용하고 그렇지 안은 경우는 forward_list를 사용하자