c++ 컨테이너 container - 벡터(vector), 리스트(list), 시퀀스(sequence), 알고리즘 헤더

* 본문은 <C++로 구현하는 자료구조와 알고리즘>(범한서적주식회사, 2013)을 공부하면서 작성한 글입니다

 

1. 먼저 STL 컨테이너(container), 반복자(iterator)에 대해 알고가자

STL 벡터, 리스트에 대해 더 잘 이해하기 위해서는 STL 컨테이너와 반복자에 대한 이해가 필요하다.

컨테이너 = 원소의 모음을 저장하는 자료구조이며, vector, deque, list, stack, queue, priority_queue, set(multiset), map(multimap)에 해당하는 것이 바로 STL에서 제공하는 다양한 종류의 컨테이너 클래스다!

반복자는 컨테이너에 저장된 원소들을 접근하고 열거하기 위해 컨테이너에서 제공하는 일정한 함수를 말한다. 지금까진 인덱스를 통해 접근하는 방법에 익숙했지만, 컨테이너 중에 이 방법이 통하지 않는 클래스가 더 많다. 이제부턴 다 이터레이터 방법을 쓸 것이다!!!

 

[반복자 기반 컨테이너 함수]

V = 기본 타입의 stl 벡터,

e = 이 기본 타입의 객체,

p,q = 이 기본 타입에 대한 반복자

• vector(p,q): p,q 사이를 반복하며 그들 원소를 새 벡터에 복사
• assign(p,q): V의 내용을 삭제하고, p,q 사이를 반복하며 그들 원소를 V의 새 내용으로 넣는다
• insert(p,q): e를 복사하여 p에 의해 주어진 위치의 바로 앞에 삽입하고 이후의 원소들은 한 위치씩 오른쪽으로 이동한다. q는 왜 있지...?
• erase(p): p 위치의 V의 원소를 삭제하고 이후 원소들은 한 위치씩 왼쪽으로 이동한다
• erase(p,q): p,q 사이를 반복하면서 삭제, 이후 원소들은 이동해서 공백 채움
• clear(): V 원소 전체 삭제
  * 여기서 반복자 범위는 [p,q) 이다.

또한 각 STL 컨테이너 클래스는 두 개의 멤버 함수 begin, end를 제공하는데, 이들은 이 컨테이너의 반복자를 반환한다. 각각 컨테이너의 첫 번째 원소를 포인트하는 반복자, 컨테이너의 마지막 원소 바로 뒤에 있는 가상 원소를 포인트하는 반복자를 반환한다.

소수의 stl 컨테이너(벡터, 큐 포함)는 정수를 더하고 뺴는 것을 허용하는 추가 기능을 지원한다. 예를 들어, 반복자 p에 대해 p+3은 컨테이너에서 p보다 세 위치 뒤에 있는 원소를 가리킨다. 이를 임의 접근 반복자라고 한다.

반복자가 컨테이너의 유효한 원소를 가리키고 있는지 유의하며 프로그래밍하면 좋다.

 

2. 알고리즘 헤더 파일 - # include <algorithm>

e = 이 기본 타입의 객체,

p,q = 이 기본 타입에 대한 반복자

반복자 범위는 똑같이 [p,q) 이다. 어떤 기능을 하는 함수인지 추측할 수 있는 것은 굳이 적지 않겠다.

• sort(p,q)
  ex) sort(V.begin(), V.end())는 원소 전체 정렬, sort(V.begin(), V.begin()+10)는 앞 원소 10개만 정렬
  
• random_shuffle(p,q): 범위 내 있는 원소들을 무작위 재배치
• reverse(p,q): 원소 순서를 역순으로 바꿈
• find(p,q,e): e가 없으면 q를 반환하는 것이 특징
• min_element(p,q) / max_element(p,q)
• for_each(p,q,f): 범위 내 모든 원소에 함수 f를 적용

3. 벡터

책에 stl 사용하지 않고 직접 벡터 클래스를 구현하는 부분이 있는데, 나중에 stl을 사용하지 말아야 하는 일이 닥치면 그 때 공부하도록 하자. 그때쯤이면 아마 굳이 공부하지 않아도 스스로 구현할 수 있는 수준이 되어있을 것임

 

[STL vector 메서드]

• vector(n): 사이즈 n의 벡터 생성.
• size(): 벡터 내 원소 개수 반환
• empty(): 벡터 비었는지 검사하여 참/거짓 반환
• resize(n): V의 크기 변경
• operator[i]: V의 i번째 원소에 대한 레퍼런스 반환
• at(i): V[i]와 같으나, i가 범위를 벗어났을 경우 예외 발생시킴
• front(): 맨 앞 원소 레퍼런스 반환
• back(): 맨 뒤 원소 레퍼런스 반환
• push_back(e): 맨끝에 원소 추가하고 크기를 1 증가시킴. 원소 추가시 모든 원소는 그 클래스의 복사 생성자를 호출하여 수행된다.
• pop_back(): ~ 크기 1 감소시킴

4. 리스트

STL list는 이중 링크드 리스트로 구현되어 있다. 앞에서 구현했던 LinkedList처럼 말이다.

list(n), size(), empty(), front(), back(), push_front/back(e), pop_front/back() 메서드를 지원한다.

 

5. 시퀀스

벡터와 리스트 ADT를 일반화하는 시퀀스 ADT 개념이 있다. 인덱스와 위치 개념 둘다 사용하여 원소에 접근하는 것을 허용하며, 리스트와 벡터에서 제공하는 모든 메서드를 제공한다.