[C++] STL(vector, list)

 

우리가 지금까지 만들어보았던 자료구조들은 이미 STL이라는 표준 라이브러리에 의해 제공되고 있다.

 

• STL(Standard Template Library) 이란?
  - C++에서 제공하는 템플릿 기반의 표준 라이브러리로, 템플릿으로 작성된 많은 제네릭 클래스와 함수 라이브러리로 다양한 알고리즘과 자료구조를 쉽게 사용할 수 있도록 클래스 형태로 제공한다.
  
  - STL의 제네릭 함수나 클래스는 이미 검증된 코드로 이를 이용하면 더욱 쉽게 C++ 프로그램을 구축할 수 있다.
  
  - std namespace에 작성되었기 때문에 STL을 사용하려면 using namespace std; 로 namespace 사용을 선언해주어야 한다.
  
  
• STL에 포함된 제네릭 클래스와 함수들은 3가지 종류로 분류된다.
  
  1. 컨테이너(=컬렉션, 자료구조) : 템플릿 클래스
  - 데이터를 저장하고 검색하기 위해 담아두는 자료구조를 구현한 클래스로, 아래에서 자세히 다룰 벡터와 리스트가 여기에 속한다.
  
  - 스스로 크기를 조절하여 원소의 개수로 인한 사용자의 부담을 덜어준다.
  
  - 컨테이너에 저장되는 원소를 다루는 방식에 따라 3가지로 분류된다.
    ▶ 순차 컨테이너 (Sequence Container) : vector, dequeue, list 등 연속적인 메모리 공간에 순서대로 값을 저장하고 읽는 컨테이너이다. 인덱스를 사용하여 컨테이너 내의 특정 위치에 있는 값을 읽거나 변경할 수 있다.
  
    ▶ 컨테이너 어댑터 (Container Adaptor) : 다른 컨테이너를 상속받아 기능 중 일부만 공개하여 기능을 제한하거나 변형한 컨테이너이다. stack, queue 등이 해당한다.
  
    ▶ 연관 컨테이너 (Associative Container) : '키'로 '값'을 저장하고 '키'로 검색하여 '값'을 알아내는 컨테이너이다. set, map 등이 해당한다.
  
  
  <STL 컨테이너 종류>

클래스	특징	헤더 파일
vector	가변 크기 배열을 일반화 한 클래스	<vector>
list	빠른 삽입/삭제가 가능한 연결 리스트 클래스	<list>
stack	스택을 일반화한 클래스	<stack>
queue	큐를 일반화한 클래스	<queue>
dequeue	앞뒤로 모두 입력이 가능한 큐 클래스	<dequeue>
map	(key, value) 쌍을 저장하는 맵 클래스	<map>
set	정렬된 순서로 값을 저장하는 집합 클래스로, 값은 유일하다	<set>

2. iterator (=반복자) : 컨테이너 원소에 대한 포인터
- 컨테이너 원소들을 하나씩 순회 접근하기 위해 만들어진 컨테이너 원소에 대한 포인터이다.
종류로는 원소를 읽는 것, 원소를 기록하는 것, 둘 다 가능한 것 등 다양하다.

- 컨테이너 종류에 무관하게 컨테이너의 원소들을 검색할 수 있도록 템플릿으로 설계되었다.

3. 알고리즘 : 템플릿 함수
- 각 컨테이너 원소에 대한 복사(copy), 검색(find, search), 삭제(remove), 정렬(sort) 등의 기능을 구현한 템플릿 함수이다.
알고리즘 함수를 사용하려면 #include <algorithm>으로 헤더 파일을 include 해야 한다.

- 컨테이너 종류에 상관없이 작동하도록 템플릿으로 설계되었다.

- STL 함수는 std 이름 공간에 작성된 전역 함수로, 이 함수들은 템플릿으로 작성 되었기 때문에 STL 컨테이너 클래스의 멤버 변수가 아니다.

- STL 알고리즘 함수는 iterator와 함께 작동한다.

 

• 벡터와 리스트

앞서 살펴보았듯 vector는 표준 라이브러리에서 제공해 주는 가변 배열이며 list는 표준 라이브러리에서 제공하는 연결형 리스트이다.
 벡터의 경우 스스로 내부 크기를 조절하므로 개발자가 크기에 대해 고민할 필요가 없다. 벡터의 원소에 대한 인덱스는 0에서부터 시작한다.

 

#include <vector>
#include <list>

 

이 두 가지는 어떤 데이터 타입이 들어오더라도 호환이 되어야 하므로 당연히 템플릿이다.

그렇기에 템플릿을 호출 할 때와 같은 방식으로 사용한다.

 

std::vector<int> vecInt; // int 타입의 값만 다루는 벡터 객체 생성

 

이전에 배웠듯이 네임스페이스를 명시하는 것이 번거롭다면 using 키워드를 사용해서 생략할 수 있다.
또한 벡터에 값을 삽입하기 위해서는 push_back() 멤버 함수를 사용한다.
이 함수는 이전에 배열에 대해 배울 때 구현하고 사용해 본 적이 있다.
그때와 동일하게 이 함수를 사용하면 삽입되는 값을 벡터의 맨 마지막에 삽입하게 된다.

 

using std::vector;
using std::list;

vector<int> vecInt;
vecInt.push_back(10);
vecInt.push_back(20);

list<int> listInt;
listInt.push_back(10);
listInt.push_back(100);

 

벡터는 가변 배열이기 때문에 push front 함수를 제공하지 않는다.
이전에 배웠듯이 가변 배열에서 현재 값의 앞쪽에 새로운 값을 넣는 것은 매우 비효율적이기 때문이다.
이런 기능이 필요하다면 애초에 가변 배열이 아닌 리스트로 구현해야 한다.

 

vector<int> vecInt;
vecInt.push_back(10);
vecInt.push_back(20);

vecInt[0] = 100;

vecInt.at(1);
// ▲ 위의 코드는 아래의 코드와 같다. ▼
vecInt[1];

 

vector에서는 특정 인덱스로 접근 해서 그 값을 레퍼런스로 반환해 주는 기능이 있다.

vecInt.at();은 함수 버전이고, vecInt[1] 와 같이 진짜 배열처럼 연산자를 써서 접근하는 방법도 있다.

vector 클래스에는 [] 연산자가 이미 작성되어 있기 때문에 벡터를 배열처럼 쉽게 사용할 수 있다.

 

또한 모든 데이터에는 시작 주소가 있다.

vecInt[0] = 100;

 

이와 같은 코드가 있을 경우 객체 안에 데이터를 저장하는 것이 아니라 이것 역시 힙 메모리를 가리키고 그 주소에 데이터를 집어넣는 것이다. 그때 최초의 첫 번째 주소를 (멤버로 치자면 T* m_pData;와 같다.) 반환해 준다.

 

함수로는 다음과 같이 사용한다.

vecInt.data();

 

이 기능은 다음과 같이 아주 간단한 방식으로 직접 구현해 볼 수도 있다.

T* data() { return m_pData; }

 

그 외에도 현재 이 가변 배열에 몇 칸의 데이터를 집어넣었는지를 반환해 주는 size() 함수와,

vecInt.size();

// 직접 구현하면 다음과 같다
int size() { return m_pData; }

 

가변 배열에 집어넣은 데이터 개수가 아닌 현재를 기준으로 지금 몇 칸까지가 허용범위 인지를 알려주는 함수도 있다.

vecInt.capacity();

// 직접 함수로 구현하면 다음과 같다.
int capacity() { return m_iMaxCount; }

 

반면 리스트에는 capacity() 함수가 존재하지 않는다. 리스트 자체가 가변 배열처럼 어느 정도 메모리를 넉넉히 할당 한 뒤 채워가는 식이 아니라 데이터를 넣을 때마다 생성되어 서로 연결되기 때문이다. 따라서 최대 허용범위 같은 개념은 리스트에 적용하기엔 적절치 않다.

 

대신 데이터의 개수를 반환하는 size() 함수에는 벡터와 동일하게 리스트에서도 존재한다.

listInt.size();

 

• 벡터 값 순회 출력하기
  벡터 안에 들어있는 데이터 값을 확인해 보기 위해서는 다음과 같이 전체 벡터에 대한 순회를 돌면서 안에 담긴 데이터를 출력하는 방법이 있다. 벡터는 가변 배열이기 때문에 인덱스만 있다면 특정 인덱스의 값을 가져올 수 있다는 점을 활용한 것이다.

for (size t i = 0; i < vecInt.size(); ++i)
{
    cout << vecInt[i] << endl;
}

 

• 리스트 안의 값 순회하기?
  그렇다면 리스트 같은 경우엔 어떻게 값을 순회해야 할까? 우리가 이전에 구현했던 리스트를 생각하면 가장 첫 번째 노드인 head부터 차례대로 next 노드를 따라가야만 각 노드 안에 든 데이터 값에 접근할 수 있었다. 하지만 이는 매우 번거로운 일이기 때문에 편리하게 자료구조라는 클래스를 쓰는 의미가 없어져 버린다.
  
  따라서 공통된 인터페이스로 자기가 이 안에 집어넣은 데이터를 순회할 수 있는 반복자 이터레이터(iterator)가 제공된다. 이러한 이터레이터를 대신 사용하면 훨씬 편리하게 값을 얻을 수 있을 것이다.
  
  
• 이터레이터(iterator, 반복자)
  

    // iterator
    // 리스트 클래스 안쪽에 구현되어 있는 클래스로 이러한 함수를 이너 클래스(=포함 클래스)라고 한다.
	list<int>::iterator iter;

	list<int> listInt;
	listInt.push_back(10);
	listInt.push_back(100);

	// iterator
	list<int>::iterator iter = listInt.begin();
	int iData = *iter; // 현재 가리키고 있는 데이터를 알려달라고 요청 
	                   // -> 리스트 안에 있는 첫번째 데이터를 받아와서 
	                   // 거기로 역참조해서 값을 본다는 점에서
	                   // 마치 포인터처럼 동작하지만 
	                   // 클래스의 객체에 *가 붙었으므로 
	                   // 이것은 포인터가 아닌 연산자 오버로딩이라는 것을 알 수 있다.
	                   // 즉, 이터레이터 라는 클래스 내부에 (*) 연산자 오퍼레이터가
	                   // 구현되어 있어서 이것이 역참조 연산을 만나면 
	                   // 자기가 가리키고 있던 노드로 가서 
	                   // 그 노드 안의 데이터 파트에만 접근해 리턴해준다.