CPP Module 08: CPP STL Programming

CPP STL (Standard Template Library)

C++의 표준 템플릿 라이브러리인 STL. CPP의 특징인 일반화 프로그래밍 패러다임의 한 축을 담당한다. STL은 객체지향 방식에서 조금 더 나아가, 알고리즘을 일반화한 표현 방식을 제공하여, 데이터를 추상화하고 코드를 재활용할 수 있게 한다.

STL의 구성 요소

1. Container : 자료구조 (stack, queue, vector, …)

• 같은 타입의 여러 객체를 저장하는 일종의 집합 개념.

• 컨테이너의 각 요소에 '반복자'(iterator)을 통해 접근할 수 있음.

• 컨테이너 내 요소 추가 및 제거를 포함한 다양한 작업을 도와주는 여러 멤버 함수를 포함하고 있음.

• STL에서 컨테이너는 자료를 저장하는 방식과 관리하는 방식에 따라 여러 가지 형태로 나뉠 수 있습니다.

• STL 컨테이너는 크게 다음과 같이 세 가지 유형으로 구분됩니다.

  	1. 시퀀스 컨테이너(sequence container)
  	 - 데이터를 선형으로 저장하며, 특별한 제약이나 규칙이 없는 가장 일반적인 컨테이너

  • 삽입된 요소의 순서가 그대로 유지된다

  • 명확한 순서가 유지되는 요소들이므로, 특정 위치를 참조하는 연산이 가능해야 한다

  • vector, deque, list, forward_list

    	2. 연관 컨테이너(associative container)
    	 - key와 value처럼 관련 있는 데이터를 하나의 쌍으로 저장하는 컨테이너

  • set, multiset, map, multimap

    	3. 컨테이너 어댑터(adapter container)
    	- 간결함과 명료성을 위해 인터페이스를 제한한 시퀀스 컨테이너나 연관 컨테이너의 변형. 
    	- 반복자를 지원하지 않으므로 STL 알고리즘에서는 사용할 수 없다.

  • stack, queue, priority_queue

2. Iterator

• STL 컨테이너에 저장된 요소를 반복적으로 순회하여, 각각 요소에 대한 접근을 제공하는 객체.
• 모든 자료구조의 원소에 대한 동일한 접근 방법 제공 (포인터와 유사).
• iterator 타입의 iter 객체를 선언하여 컨테이너의 특정 위치에 접근.
• 벡터의 경우에는 이터레이터, 포인터가 동일한 개념임.

왜 필요한가?

지금까지 우리는 배열의 요소에 접근할 때 i 같은 인덱스를 선언해 사용해 왔다. 반복자는 그런 연산의 과정을 어떤 객체에서나 동일하게 사용할 수 있도록 통일해서 cpp에서 제공하는 generic 포인터 객체라고 생각하면 된다. iterator 클래스 내부에는 배열의 요소를 쉽게 가리킬 수 있도록 몇가지 멤버함수들이 정의되어 있다. iterator 메서드와 컨테이너 메서드를 적절히 사용하면 좋은 알고리즘을 가진 클래스와 함수를 작성할 수 있을 것이다.

3. Algorithm : 함수 (sort, swap, find, …)

• 알고리즘 헤더파일 포함! \

벡터와 리스트

Vector

• 시퀀스 컨테이너
• 벡터(vector) 객체는 요소가 추가되거나 삭제될 때마다 자동으로 메모리를 재할당하여 크기를 동적으로 변경하는 배열이다.
• 메모리 할당을 연속적으로 한다. 미리 할당해 놓고 값을 지정한다. 할당된 메모리 이상으로 값이 추가되면 그때 더 큰 메모리 할당한다. (배열처럼 사용 가능). push_back이 List보다 빠르다. Insert의 경우는 배열을 계속 재구성해야해서 List보다 느리다.

벡터 생성하기

#include <vector> //헤더파일 추가
vector<[data type]> [변수이름] //선언

벡터와 자주 사용되는 STL 함수들

vector<int> vc = {10, 20, 30}; // vector 객체의 선언 및 초기화
cout << "현재 벡터의 크기는 " << vc.size() << "입니다." << endl;
// 현재 벡터의 크기는 3입니다.


vc.push_back(40);              // vector 요소의 추가
cout << "현재 벡터의 크기는 " << vc.size() << "입니다." << endl;
// 현재 벡터의 크기는 4입니다.

cout << "현재 벡터의 네 번째 요소는 " << vc[3] << "입니다." << endl
// 현재 벡터의 네 번째 요소는 40입니다.


cout << "현재 벡터의 모든 요소는 다음과 같습니다 :" << endl;
copy(vc.begin(), vc.end(), ostream_iterator<int>(cout, " "));
// 현재 벡터의 모든 요소는 다음과 같습니다 :
// 10 20 30 40 

1. size() 함수 : 컨테이너에 저장된 요소의 개수를 반환함.
2. push_back() 함수 : 컨테이너의 마지막 요소로 해당 데이터를 추가함.
3. begin() 함수 : 컨테이너의 첫 번째 요소를 가리키는 반복자를 반환함.
4. end() 함수 : 컨테이너의 마지막 요소 바로 다음(past-the-end)을 가리키는 반복자를 반환함.
5. push_front() 함수 : 컨테이너의 첫 번째 요소로 해당 데이터를 추가함.
6. front() 함수 : 컨테이너의 첫 번째 요소를 반환함.
7. pop_front() 함수 : 컨테이너의 첫 번째 요소를 삭제함.

List

• 시퀀스 컨테이너

• 이중 연결 리스트(doubly linked list)의 클래스 템플릿 표현

• 컨테이너의 모든 요소에서 양방향 접근, 빠른 삽입과 삭제가 가능

• 임의 접근 불가

• 따로따로. 값을 넣을 때마다 메모리를 할당. (배열처럼 사용 불가, Linked List처럼 동작).

• 임의 접근을 통한 빠른 접근이 장점

• 요소들의 빠른 삽입과 삭제가 장점입니다.

• 리스트를 구성하는 링크(link)는 포인터이므로, 다음과 같은 특정 작업을 링크만 재배치하는 것으로 아주 빠르게 수행할 수 있음

swap() 두 요소의 위치를 서로 바꿈.
reverse() 리스트 전체의 요소의 위치를 역순으로 변경함.
sort() 리스트 전체의 요소를 정렬함.
unique() 같은 값이 인접해 있을 경우, 그 값들을 하나로 단일화함.
merge() 두 정렬된 리스트를 합병함.
splice() 두 리스트를 연결하거나, 한 쪽 리스트로 이동시킴.

벡터와 리스트의 차이

• Vector는 값을 삭제하더라도 메모리 해제를 하지 않는다. 심지어 Clear를 하더라도 메모리는 그대로 남게 된다.

• 반대로 List의 경우 변수가 해제 될때마다 메모리에서 해제하게 된다. 할당과 마찬가지로 해제또한 popback의 경우 vector가 훨씬 빠르다. 하지만 역시 중간에 값을 삭제하는 것은 List가 더 빠르다.

• 따라서 순서와 상관없거나 순차적으로만 추가, 삭제되는 데이터는 vector를 쓰는게 좋다. 임의 접근을 통한 빠른 접근이 장점이다.

• 순서가 중요하여 리스트의 중간위치에 값이 추가, 삭제가 되는 경우 list를 사용하는 것이 좋다. 요소들의 빠른 삽입과 삭제가 장점이다. (메모리는 더 먹지만 속도가 빠르다)

• 벡터에서, 반복자가 가리키는 요소를 삭제 할 경우 그 반복자는 무효화 된다. 
  vector에 대해 erase를 호출하면 방금 삭제된 요소 다음에 있는 요소들을 가리키는 모든 반복자는 무효화 된다.

• 또한 push_back을 사용하여 vector에 요소를 추가해도 해당 vector를 가리키고 있던 모든 반복자는 무효화 된다. 

• vector에 한 요소를 삭제하면 그 다음 요소들이 이동되고, 한 요소를 추가하면 새로운 요소를 위한 공간을 확보하기 위해 전체 vector가 재할당되기 때문이다.

• 하지만 list에서는 erase나 push_back이 다른 요소들에 대한 반복자를 무효화 시키지 않고 실제로 삭제된 요소를 가리키는 반복자만 무효화 된다. 왜냐하면 그 요소는 더 이상 존재하지 않기 때문이다. 

벡터와 배열의 차이

https://sueaty.tistory.com/59

• Vector는 근본적으로 동적인 성격을 띄기 때문에 빈번하게 요소들의 삽입 삭제가 이루어질 때 자동적으로 크기를 조절한다. 힙 메모리로의 포인터를 가지고 있는 template class이기 때문에 std::vector가 호출 될 때마다 'new'가 함께 호출된다. Vector도 물론 순차적이지만 요소로의 접근을 포인터로 하기 때문에 속도 측면에서는 느릴 수 밖에 없다. Vector의 요소들이 연속적인 메모리 블록에 저장되어 있기 때문에 iterator를 사용해서 쉽게 살펴볼 수 있다는 장점이 있다.

반복자 설명

컨테이너 어댑터

• 시퀀스, 연관 컨테이너의 인터페이스를 제한하여 만든 기능이 제한/변형된 컨테이너
• 각각의 '기반'이 되는 클래스의 인터페이스를 제한하여, 특정 형태의 동작만들 수행하도록 함
• iterator을 지원하지 않음 (기본적으로는)
• stack, queue, priority_queue

스택 (Stack)

• vector 클래스의 인터페이스를 제한하여, 전형적인 '스택 메모리 구조'의 인터페이스 제공
• 선형 메모리 공간에 데이터를 저장하면서 후입선출 시맨틱을 따름

Module 08

• 기본적으로 STL과 그 내부의 컨테이너, 이터레이터, 알고리즘을 이해하는 문제
• 개념 이해 뿐 아니라 왜 써야 하는지, 어떨 때 써야 하는지를 설명할 수 있어야 함
• 이전 모듈들이 STL을 사용하지 않고, 완전히 객체지향적으로 주어진 문제들을 해결해 보는 시도였다면, 08은 C++이 왜 효율적인지 일반화 프로그래밍을 통해 이해하는 것
• 어떠한 작업을 하냐에 따라서 속도차가 매우 크기 때문에, C++ 표준 라이브러리를 잘 사용하기 위해서는 내가 이 컨테이너를 어떠한 작업을 위해 사용하는지 정확히 인지하고, 적절한 컨테이너를 골라야 함.

ex00

• 템플릿 함수 easyfind를 만드세요
• 프로토타입은 easyfind(container T, int N) 형식이며, 두번 째 int형 인자 N이 컨테이너 T에서 처음으로 등장하는 지점을 찾습니다
• 만약 N이 T 내에 없으면 error 을 출력하세요 (std::exception 또는 error 리턴 밸류 중 원하는 것을 이용)

ex00에서 요구하는 것

• 템플릿 함수에 대한 이해 (어떤 인자가 들어오든 같은 작업을 수행하게 하는 함수)
• STL 표준 컨테이너에 대한 이해 (컨테이너와 이터레이터가 어떤 관계이며 어떻게 동작하는지 알기)
• STL iterator에 대한 이해
• STL 표준 알고리즘에 대한 이해와 사용
• 컨테이너 T 안에서 찾고자 하는 값이 있으면 찾았음을, 못 찾으면 에러를 띄워 주기
• iterator 객체를 선언하고, 표준 알고리즘 함수 중 find를 사용하여 순회하며 값을 찾은 후 iterator it에 위치를 저장해 주기
• 컨테이너 멤버함수 begin(), end() 사용하여 범위 지정해 주기
  - begin() 함수 : 컨테이너의 첫 번째 요소를 가리키는 반복자를 반환함.
  - end() 함수 : 컨테이너의 마지막 요소 바로 다음(past-the-end)을 가리키는 반복자를 반환함.
• 벡터의 경우 배열처럼 대괄호를 사용해 인덱스처럼 접근할 수 있음

ex01

• N개의 int를 저장할 수 있는 클래스를 만드세요
• N은 unsigned int이고, 생성자의 단일 파라미터로 사용합니다
• addNumber 라는 '하나의 숫자'를 저장하는 함수가 있어야 하고, 이미 N개가 클래스 안에 저장되어 있는 경우 새 숫자를 추가할 시 예외를 발생시켜야 합니다
• shortestSpan 함수는 벡터 내에 있는 원소들 중 차이가 가장 작은 값을 구합니다
• longestSpan 함수는 벡터 내에 있는 원소들 중 차이가 가장 큰 값을 구합니다
• 클래스 안에 숫자가 없거나 하나만 있으면 범위가 없으므로 예외를 발생시켜야 합니다

ex01에서 요구하는 것

• STL 알고리즘을 사용할 수 있는지, 개념을 알고 있는지 (iterator, vector, min_element, max_element, sort)
• STL 벡터에 대한 개념을 정확하게 이해하고 있는지
• 포인터로 를 해서 가리키는 주소값의 값을 보았던 것처럼, 벡터에서 연산자를 이용해서 itr 이 가리키는 원소를 볼 수 있습니다. 물론 itr 은 실제 포인터가 아니고 연산자를 오버로딩해서 마치 포인터 처럼 동작하게 만든 것임. 연산자는 itr 이 가리키는 원소의 레퍼런스를 리턴함.

ex02

-std::stack 컨테이너는 훌륭하지만, iterable이 아닌 유일한 STL 컨테이너 입니다. iterator를 std::stack 컨테이너에 접목시켜 이 문제를 해결해보세요.

• std::stack을 상속받아 MutantStack 만들기
• MutantStack 클래스는 std::stack의 모든 멤버 함수를 제공하고, iterator도 제공한다.
• 해당 MutantStack을 main으로 테스트했을 때, std::list와 똑같이 동작해야 합니다.
• STL의 Stack을 이용해(상속받아) MutantStack이라는 컨테이너를 만들어라. 단순히 Stack에 이터레이터를 더한 것처럼 동작되어야 한다. (팁 : STL의 스택은 보통 덱을 이용해 만든다. Stack 멤버 변수를 잘 봐서 적절히 호출시켜서 구현하면 됨)

ex02에서 요구하는 것

• 즉, 스택에 이터레이터 기능을 추가한 컨테이너 구현하는 것이 과제의 핵심. (Custom Stack)
• 클래스에 아래와 같은 iterator 타입 멤버를 추가해 줌

typedef typename std::stack<T>::container_type::iterator iterator; 

• std::stack을 상속받은, 타입 T형의 인스턴스를 만들고, 이 인스턴스 내의 iterator을 가져와서 iterator이라는 멤버로 만들어 주겠다는 뜻임

• stack 라이브러리를 까보면

template<class _Ty,
	class _Container = deque<_Ty> >
	class stack
	{ 
    // ...
    
    protected:
	_Container c;	// the underlying container
};

요런 부분이 있는데, protected접근권한자로 _Container 타입의 멤버변수가 있고, 이 타입이 deque임. 요 c 멤버변수로 접근하면 deque의 멤버함수들을 호출할 수 있고, stack을 상속받아 c 변수로 접근 가능하다면 deque의 함수들을 사용할 수 있음.

stack에서 사용하는 empty, size, top, push, pop등의 함수들도 내부에서는 deque함수를 호출해서 구현되어 있음.

deque는 vector의 단점을 보완하기 위해 만들어진 container임. 메모리가 부족하면 메모리를 처음부터 재할당하여 원소를 복사하는 vector의 단점 보완하기 위해, deque는 메모리가 부족할 때 마다 일정한 크기의 새로운 메모리 블럭을 할당함.

deque에서 가져오는 아이들

dq.begin();

• 첫번째 원소를 가리킵니다. (iterator와 사용)
• ex) deque::iterator iter = dq.begin();

dq.end();

• 마지막의 "다음"을 가리킵니다. (iterator와 사용)
• ex) deque::iterator iter = dq.end();

dq.rbegin();

• reverse begin을 가리킵니다.
• 맨 마지막원소를 마치 첫 번째 원소처럼 가리킵니다. (역으로)
• iterator와 사용.
• ex) deque::iterator iter = dq.rbegin();

dq.rend();

• reverse end 을 가리킵니다.
• 맨 첫번째 원소의 "앞"을 마지막 원소의 "다음" 처럼 가리칩니다.
• iterator와 사용.
• ex) deque::iterator iter = dq.rend();

출처: https://blockdmask.tistory.com/73 [개발자 지망생]