[C++] STL Container I

 본 포스트는 코드누리 C++ Basic 강의 내용을 보고 정리한 포스트입니다.

 

- Basic에서는 STL에서 가장 기본이 되는 얘기만 다뤄진다.

- 이후 별도 STL 카테고리에서 STL에 대해서 조금 더 다양한 얘기를 할 것이다.

- 여기서는 C++ 개발자가 알아야하는 핵심 내용이나 사용법 위주로 다룬다.

 

1. STL의 역사

- 1983년 처음 발표되고, C++ 1차 표준 (C++98) 발표 및 자료 구조와 알고리즘 위주의 라이브러리가 추가되었다.

- 이후 C++11 / 14 / 17에 thread, smart pointer, chrono, file 등이 추가된다.

- C++ 20에는 Range, Concept 등의 라이브러리가 추가된다.

- C++ 23 / 26에서 generator, excepted, Network(C++26) 다양한 라이브러리 추가 예정이다.

 

※ 이처럼 버전업이 되면서 새로운 라이브러리가 추가되고 있다.

 

C++ Reference와 관련해서는 해당 링크를 통해서도 확인이 가능하다.

C++ 레퍼런스의 예시와 사용 방법등이 설명되어 있으니 필요한 것을 꺼내어 사용할 수 있다.

C++ Reference 홈페이지

---

2. STL 핵심 요소

① 컨테이너(Container)

-  C++ 표준 라이브러리에서 제공하는 다양한 자료구조이다.

- STL 컨테이너는 데이터를 저장하고 관리하는 데 사용된다.

- Vecotr, (Linked) list, stack, queue와 같은 자료구조를 제공한다.

② 알고리즘(Algorithm)

- 데이터를 처리하고 조작하는 다양한 기능을 제공하는 함수들을 의미

- 정렬, 검색, 힙 연산 등이 존재하며, C++에서는 이런 함수를 알고리즘이라고 한다.

③ 반복자(Iterator)

- 자료구조와 알고리즘을 연결하는 포인터와 유사한 객체를 의미한다.

---

3. Container

- Vector, list, stack 등 여러 개의 값(객체)를 보관하는 클래스(템플릿)

- 자료구조를 클래스(템플릿)으로 설계한 것을 컨테이너라고 한다.

 

3-1. Container의 종류

컨테이너 종류	컨테이너 이름
선형 컨테이너	array
	vector
	list
	forward_list
	deque
컨테이너 어댑터	stack, queue, priority_queue
연관 컨테이너	set map
	unordered_set unordered_map

- 각각은 독립된 헤더파일을 사용한다.

 

3-2. Container의 타입 인자 생략 지원 // C++17

#include <vector>

int main()
{
    // 1. C++17 부터는 초기값이 있는 경우 타입 인자 생략 가능
    std::vector<int> v1 = { 1,2,3,4,5 };
    std::vector v1      = { 1,2,3,4,5 };
    
    // 2. 초기값이 없는 경우는 반드시 타입인자를 전달해야 한다.
    std::vector      v3; // error
    std::vector<int> v4; // ok
    
    std::vector      v5(10, 3); // 10개를 3으로 초기화, 타입인자 생략 가능
    std::vector<int> v6(10);    // 타입 인자 필요
    
    // 3. () 와 { } 를 주의할 것.
    std::vector v7(10, 3); // 10개를 3으로 초기화
    std::vector v8{10, 3}; // 2개를 10, 3으로 초기화, 아래 코드와 동일
    std::vector v9 = {10, 3}; 
}

- C++ 17 부터는 초기값이 없는 경우 타입 인자의 생략이 가능하다.

- Container 사용시, ( )와 { }를 혼동하지 않도록 유의해야 한다.

 

3-3. STL Container의 공통적인 특징

 

① 대부분의 컨테이너의 멤버 함수 이름이 동일하다.

#include <vector>
#include <list>

int main()
{
    // 1. 대부분 컨테이너의 멤버 함수 이름이 동일
    std::vector c = {1,2,3};
    
    c.push_back(4);
    c.resize(10);
    auto sz = c.size();
    
    // 2. 제거와 반환을 동시에 하는 멤버 함수는 없다.
    auto n = c.back();
    c.pop_back();
}

- 대부분의 코드를 수정하지 않고도 컨테이너를 교체할 수 있다.

- 차이점이 있는 경우도 있는데 이는 의도적인 설계이다.

 

// 1. 대부분 컨테이너의 멤버 함수 이름이 동일
// std::vector c = {1,2,3};
   std::ist c = {1, 2, 3};

- Vector를 사용하다가 list로 변경했다고 하더라도 이 코드는 기존 아래 있는 코드를 수정할 필요가 없다.

 

② 제거와 반환을 동시에 하는 멤버 함수가 없다.

// 2. 제거와 반환을 동시에 하는 멤버 함수는 없다.
    auto n = c.back();
    c.pop_back();

- pop_front(), pop_back()은 요소를 제거만 한다.

- front(), back() 함수는 반환만 하는 것이다.

- '예외 안정성의 강력 보장'을 지원하기 위한 의도적인 설계이다.

※ 예외 안정성의 강력 보장이라는 개념이 다소 어려운 개념으로, 별도로 다뤄볼 예정이다.

---

4. 선형 컨테이너(Sequence Container)

- 모든 요소들이 삽입된 순서로 한줄로 놓여 있는 것을 선형라고 한다.

- 5개의 선형 컨테이너가 제공된다.

- 선형 컨테이너의 메모리 구조 파악이 중요하다.

- Deque는 덱(deck)으로 칭한다. 

- 여기서 list는 double linked list이고, forward_list는 single linked list이다.

- array는 별도로 다룬다. (vector와 조금 다르다)

 

#include <vector>		
#include <list>			
#include <deque>		
#include <forward_list> 
#include <array>

int main()
{
	// 1. 선형 컨테이너(sequence container)의 메모리 구조
	std::vector v = {1, 2, 3, 4, 5};
	std::list   s = {1, 2, 3, 4, 5};
	std::deque  d = {1, 2, 3, 4, 5};

	// 2. 대부분의 멤버 함수는 이름(사용법)이 동일 합니다.
	v.push_back(2);
	s.push_back(2);
	d.push_back(2);

	// 3. 사용법이 다른 경우가 있다면 의도적인 설계 입니다.
//	v.push_front(3);	// error. vector는 전방 삽입 안됨
	s.push_front(3);
	d.push_front(3);

	v[4] = 5;
//	s[4] = 5;	// error. list 는 배열 연산 안됨.
	d[4] = 5;

	// 4. 사용법이 유사하므로 컨테이너를 변경해도 대부분의 코드는 수정 없이 사용가능
//	std::vector c = {1,2,3,4};
	std::list c = {1,2,3,4};

	c.push_back(10);
	c.pop_back();
}

- 앞서 다룬 것과 같이 대부분의 멤버 함수는 함수 이름이 동일하다.

- 하지만, 사용법이 다른 것도 존재한다.

 

4-1. 의도적으로 사용법이 다른 것의 설계 예시

① vector의 전방 삽입/삭제 미지원

- vector는 push_front(), pop_front()가 없다.

- vector의 앞에 삽입/삭제 하는 것은 성능이 좋지 않다.

 

- Vector는 연속된 메모리이다.

- vector의 앞쪽에 삽입함으로써, 기존 메모리를 모두 뒤로 밀어내면서, 메모리 복제가 발생한다.

- 이 과정에 대한 성능 저하가 상당히 크다.

※ vector의 앞에 삽입/삭제 하는 것은 성능이 좋지 않다.

 

② list는 [] 연산을 할 수 없다.

- 연속되지 않은 메모리에 [] 연산은 성능이 좋지 않다.

- 연속된 메모리의 경우 []을 이용해서 굉장히 빠르게 접근이 가능하다.

- 이에 반면, list는 처음부터 거쳐서 가야한다. 

 

4-2. 어떤 컨테이너를 사용해야 하는가?

vector	연속된 메모리, [] 연산 가능 요소 접근이 빠르지만, 삽입/삭제가 느림
list	떨어진 메모리, [] 연산 안됨 요소 접근이 느리지만, 삽입 삭제가 빠름
deque	부분적으로 연속된 메모리, [] 연산 가능

- 사용법이 유사하므로, 컨테이너만 변경하면서 성능 측정이 가능하다.

- 대부분의 경우는 vector를 권장한다. (연속된 메모리라서 캐시 적중률이 높다.)