c++ stl Container 사용법 정리

문제를 해결할 때 적절한 자료구조를 선택하면 문제를 쉽게 해결할 수 있다.

c++에서 지원하는 아주 유용한 container들이 있다. 

간단하게 각각 접근법,삽입,삭제에 대해서 알아보자.

 

 

<Sequence Container>

-vector

   정리해 놓은 개시물 링크 https://zero-stone.tistory.com/22

 

  >접근법:

       1) v[index]   / 시간복잡도=O(1)

 

       2) v.at(index)  / 시간복잡도=O(1)

 

       3) v.back()  /  시간복잡도=O(1)

  

       4) v.front()  /  시간복잡도=O(1)

 

       5) v.begin과 v.end를 이용해 iterator로 접근  /  시간복잡도=O(N)

 

       6) v.data를 이용해 포인터로 접근  / 시간복잡도=O(N)  

       iterator가 [] 지원 ex) it[1]  

     

 >삽입:

     1) v.insert(iterator , value)  /  시간복잡도=O(N)

    

     2) v.push_back()  /  시간복잡도=O(1)

 

 >삭제: 

     1) v.erase(iterator)  /  시간복잡도=O(N)

 

     2) v.pop_back()  /  시간복잡도=O(1)

 

-deque

   정리해 놓은 개시물 링크 https://zero-stone.tistory.com/25

 

  >접근법:

       1) dq[index]   / 시간복잡도=O(1)

 

       2) dq.at(index)  / 시간복잡도=O(1)

  

       3) dq.back()  / 시간복잡도=O(1)

 

       4) dq.front()   /  시간복잡도=O(1)

       

       5) dq.begin과 dq.end를 이용해 iterator로 접근  /  시간복잡도=O(N)

       iterator가 [] 지원 ex) it[1]

 

 >삽입:

     1) dq.insert(iterator , value)  /  시간복잡도=O(N)

    

     2) dq.push_back()  /  시간복잡도=O(1)

 

     3) dq.push_front()  /  시간복잡도=O(1)

 

 >삭제: 

     1) dq.erase(iterator)  /  시간복잡도=O(N)

 

     2) dq.pop_back()  /  시간복잡도=O(1)

     

     3) dq.pop_front()  /  시간복잡도=O(1)

 

-list 

   정리해 놓은 개시물 링크

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

   

>접근법:

       1) list.back()   / 시간복잡도=O(1)

 

       2) list.front()  / 시간복잡도=O(1)

  

       3) list.begin()과 list.end()를 이용해 iterator로 접근  /  시간복잡도=O(N)

       

 

 >삽입:

     1) list.insert(iterator , value)  /  시간복잡도=O(1) 

 

     2) list.push_back()  /  시간복잡도=O(1)  but vector,deque 보다 비효율적

 

     3) list.push_front()  /  시간복잡도=O(1) but vector,deque 보다 비효율적

 

 >삭제: 

     1) list.erase(iterator)  /  시간복잡도=O(1)

    

     2) list.remove(value)  /  시간복잡도=O(N)

 

     2) list.pop_back()  /  시간복잡도=O(1) but vector,deque 보다 비효율적

     

     3) list.pop_front()  /  시간복잡도=O(1) but vector,deque 보다 비효율적

 

 

 

-forward_list 

   정리해 놓은 개시물 링크

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

      

>접근법:

       1) flist.front()  / 시간복잡도=O(1)

  

       2) flist.begin()과 flist.end()를 이용해 iterator로 접근  /  시간복잡도=O(N)

       

 

 >삽입:

     1) flist.insert_after(before_iterator , value)  /  시간복잡도=O(1) 

 

     2) flist.push_front()  /  시간복잡도=O(1) but vector,deque 보다 비효율적

 

 >삭제: 

     1) flist.erase_after(before_iterator)  /  시간복잡도=O(1)

    

     2) flist.remove(value)  /  시간복잡도=O(N)

 

     3) flist.pop_front()  /  시간복잡도=O(1) but vector,deque 보다 비효율적

 

<Associate Container>

-map & multimap

   정리해 놓은 개시물 링크

   map->https://zero-stone.tistory.com/16

   multimap->https://zero-stone.tistory.com/17   

>접근법:

       1) m.at(key)  / 시간복잡도=O(log N)

        multimap은 x

 

       2) m[index]  /  시간복잡도=O(log N)

        multimap은 x

 

       3) m.find(key)  /  시간복잡도=O(log N) 

           iterator 반환

 

       4) m.begin()과 m.end()를 이용해 iterator로 접근  /  시간복잡도=O(N)

       

 

 >삽입:

     1) m.insert(pair<1,3>)  /  시간복잡도=O(log N) 

 >삭제: 

     1) m.erase(key or iterator)  /  시간복잡도=O(log N)

 

 

-set & multiset

   정리해 놓은 개시물 링크

   set & multiset -> https://zero-stone.tistory.com/20

>접근법:

       1) s.find(key)  /  시간복잡도=O(log N)

       2) s.begin()과 s.end()를 이용해 iterator로 접근  /  시간복잡도=O(N)

       

 >삽입:

     1) s.insert(key)  /  시간복잡도=O(log N) 

 >삭제: 

     1) s.erase(key or iterator)  /  시간복잡도=O(log N)