[Coding Test] Coding Tips 6 : vector, deque, list

삼성B형을 위한 코딩 팁 시리즈

Python 개발자의 PRO 취득을 위한 C++ 공부 여정

• [Coding Test] Coding Tips 1 : ABS(x) macro used in DFS
• [Coding Test] Coding Tips 2 : Priority Queue, Bit Operator
• [Coding Test] Coding Tips 3 : Iterator
• [Coding Test] Coding Tips 4 : algorithm library
• [Coding Test] Coding Tips 5 : 잡-Skill
• [Coding Test] Coding Tips 6 : vector, deque, list
• [Coding Test] Coding Tips 7 : hash

Vector, Deque, List

검정에서 가장 많이 사용하는 컨테이너 타입

vector

• void v.push_back(T x)
• void v.pop_back()
• v.insert() : 처음 입력된 element 의 iterator
  • iterator v.insert(iterator pos, T x) : 삽입 할 위치
  • iterator v.insert(iterator pos, int count, T value) : 삽입 할 위치에 value 값을 count 개 넣기
  • iterator v.insert(iterator post, iterator first, iterator last) : 특정 다른 벡터의 first ~ last 원소 삽입
• v.erase() : 마지막 지워진 element 의 다음 iterator
  • iterator v.erase(iterator pos)
  • iterator v.erase(iterator first, iterator last)

원소 삭제

• erase()
  • O(n)
  • 순서 유지

    v.erase(v.begin() + 2)
    

• 마지막 element 로 덮어쓰기
  • O(1)
  • 순서 유지 X

    v[2] = v.back();
    v.pop_back();
    

deque

• vector 와의 차이점은 front 에 insert/erase 가 O(1)
• 일반적인 연산은 vector 보다 느리므로 front 에 insert/erase 가 필요한 경우에만 사용
• block 주소를 저장하는 공간이 깍 찬 경우에 migration 발생
• 캐시를 사용하는데 지장이 있음 (Compiler option 이 심지어 꺼져 있기 때문에 연속된 데이터를 삭제하는 것이 빠르기 때문에 deque 보다 vector 가 빠르다)

list

• list 는 algorithm 의 sort 를 쓸 수 없음
• li.splice(iterator pos, list<T> li2) : li 의 pos 에 li2 전체 이동
• li.splice(iterator pos, list<T> li2, iterator it) : li 의 pos 에 li2 의 it 이동
• li.splice(iterator pos, list<T> li2, iterator first, iterator last) : li 의 pos 에 li2 의 [first, last) 구간 이동