컨테이너 어댑터

순차열 컨테이너를 다른 기능을 제공하는 순차열 컨테이너로 정의하기 위해 래핑되는 클래스 템플릿.

기존 인터페이스를 확장(Adapt)한다.

  1. stack<T> 는 deque<T> 컨테이너를 Push-Down 스택으로 저장하는 방식으로 변환하는 어댑터 클래스 템플릿.
  2. queue<T>는 deque<T> 컨테이너를 큐로 저장하는 방식으로 변환하는 아댑터 클래스 템플릿
  3. priority_queue<T> 컨테이너는 vector<T> 컨테이너를 가장 큰 원소가 항상 앞에 오도록 원소들의 순서를 관리하는 큐로 변환하는 아댑터 클래스 템플릿(Heap)

Stack 컨테이너

연산

  1. top() 스택 상위에 있는 원소 T&을 반환한다.
  2. push(const T& obj) 스택 상위에 obj의 복사본을 넣는다. push_back() 기반
  3. push(T&& obj) 스택 상위에 obj을 이동한다.
  4. pop() 스택상위에 원소를 삭제한다.
  5. size() 스택에 있는 원소의 갯수를 반환한다.
  6. empty() 스택에 원소가 하나도 없으면 true
  7. emplace() T생성자 호출후, 컨테이너 내부에 객체 생성하고 stack<T>상위에 객체를 추가
  8. swap(stack<T> &ohter_stack) 현재 스택의 원소와 전달된 원소들을 교환. 같은 타입이어야만 한다.

stack<T>에서 operator=() 의 복제버전과 이동버전이 모두 정의되어 있음.

stack 객체끼리 비교할수 있는 연산자도 정의되어 있음. 비교방식은 대응하는 원소들을 사전순서에 맞춰 비교한다.

Remove 함수

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <cmath>
#include <iostream>
#include <stack>
#include <algorithm>
#include <stdexcept>
#include <string>

using namespace std;

inline size_t preceudence(const char op)
{
	if (op == '+' || op == '-')
		return 1;
	if (op == '*' || op == '/')
		return 2;
	if (op == '^')
		return 3;

	throw runtime_error{ string {"invalid operator:"} +op };
}

double execute(std::stack<char>& ops, std::stack<double>& operands)
{
	double result{};
	double rhs{ operands.top() };		// 우측값
	operands.pop();
	double lhs{ operands.top() };		// 좌측값
	operands.pop();

	switch (ops.top())
	{
	case '+':
		result = lhs + rhs;
		break;
	case '-':
		result = lhs - rhs;
		break;
	case '*':
		result = lhs * rhs;
		break;
	case '/':
		result = lhs / rhs;
		break;
	case '^':
		result = pow(lhs, rhs);
		break;
	default:
		throw runtime_error{ string {"invalid_operator: "} +ops.top() };
	}

	ops.pop();
	operands.push(result);
	return result;
}
int main()
{

	stack<double> operands;
	stack<char> operators;
	string exp;
	cout << "An arithmetic expression can include the operator +, -, *, / and ^ for exponentiation." << endl;

	try
	{
		while (true)
		{
			cout << "Enter an anitrhmetic expression and press enter - enter an empty line to end." << endl;
			getline(cin, exp, '\n');
			if (exp.empty())
				break;

			// 공백 제거
			exp.erase(remove(begin(exp), end(exp), ' '), end(exp)); // remove는 원소를 제거하지 않고, 제거할 원소들을 덮어쓰면서 원소를 이동한다.
			// remove가 리턴한 반복자로 remove를 수행한 문자열에서 마지막으로 유효한 문자를 가르킨다. 

			size_t index{};

			operands.push(stod(exp, &index)); // 스택에 첫번째 피 연산자 (lhs)을 넣는다.

			while (true)
			{
				operators.push(exp[index++]);

				// Get rhs operand
				size_t i{};										// 서브스트링의 인덱스
				operands.push(stod(exp.substr(index), &i));		// 우측값 피 연산자를 넣는다.
				index += i;

				if (index == exp.length())		// 식의 끝이라면?
				{
					while (!operators.empty())	 // 처리되지 않은 연산자 진행
						execute(operators, operands);
					break;
				}

				// 아직 처리할 연산자가 남아있음. 이전 연산자와 같거나, 더 높은 우선순위라면 실행
				while (!operators.empty() && preceudence(exp[index]) <= preceudence(operators.top()))
					execute(operators, operands);
			}

			cout << "resutl = " << operands.top() << endl;
		}
	}
	catch (exception &e)
	{
		cerr << e.what() << endl;
	}

	cout << "Calculrator ending ... " << endl;


    return 0;
}

Queue 컨테이너

연산

  1. front()큐에 있는 첫번째 윈소에 대한 참조 반환, const라면 const& 반환
  2. back() 큐에 있는 마지막 원소에 대해 참조를 반환, const라면 const& 반환
  3. push(const T& obj) obj의 복제본을 큐의 끝에 추가한다.
  4. push(T&& obj) 큐의 끝에 obj을 이동해서 추가한다.
  5. pop() 큐에서 첫번째 원소를 삭제
  6. size() 큐에 있는 원소의 개수 반환
  7. empty() 큐에 원소가 하나도 없으면 true
  8. emplace() T 생성자 호출해 컨테이너 내부에 객체를 생성하고 큐의 끝에 추가
  9. swap(queue<T> &other_q) 현재 큐에 있는 원소들과 인수로 전달된 원소들을 교환한다. 큐와 같은 타입으로 되어 있어야됨.

operator=() 복제 버전과 이동 버전이 정의되어 있음.

stack의 비교 연산자와 같은 방식으로 동작

stack과 마찬가지로 queue에도 반복자가 없다.

Priotiry Queue 컨테이너

우선순위 큐 컨테이너는 윈소들을 정렬된 순서로 담아두는 큐를 정의한다. priotiry_queue<T>는 3가지 매개변수가 있고, 그 중에 두가지는 기본인수다.

우선순위 큐는 Heap이라는 자료구조로 이루어져 있고 Heap은 트리구조로, 최소힙, 최대힙이 있다.

1
2
3
4
template <typename T, typename Container=std::vector<T>, typename Compare=std::less<T>>
class priority_queue
    
// 벡터 컨테이너를 기본으로 래핑. functional 헤더에 정의된 less<T> 함수 객체 타입은 기본 순서 조건자로 이용해서, 가장 큰 객체가 앞에 오게 할수 있다. 또는 greater<T>도 정의되어 있음.

우선순위 큐 생성

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
priority_queue<string> words;  // 생성

// 타입이 일치하는 객체를 범위로 지정해서 우선순위 큐 초기화도 가능
string word[] {"one", "two", "three", "four"};
priority_queue<string> words {begin(wrd), end(wrds)};

// 복제 생성자로 타입이 같고 템플릿 타입인수가 같은 우선순위 큐 객체를 복제할수 있다.
priority_queue<string> copt_words {words};

// string 객체를 operator>() 함수로 비교하면서 우선순위 큐를 생성한다.
string wrd[] {"one", "two", "three", "four"};
priority_queue<string, vector<string>, greater<string>> words1 {
    begin(wrds), end(wrds)
};

vector<int> values {21, 22, 13, 3, 24, 54, 56};
priority_queue<int> numbers {less<int>(), values}; // 초기화에 쓸 원소를 지정할수 있음.

연산

  1. push(const T& obj) 컨테이너 obj의 복제본을 순차열의 적절한 위치에 넣는다
  2. push(T&& obj) 컨테이너 안으로 obj를 이동해서 순차열의 적절한 위치에 넣는다.
  3. emplace(T constructor args): emplace()에 전달된 인수로 생성자 호출해 T 객체 바로생성하고 순차열의 적절한 위치에 넣는다. 보통은 정렬 작업이 필요
  4. top() 우선순위 큐의 첫번째 객체의 참조를 반환
  5. pop() 첫 번째 원소를 제거
  6. size() 큐에 있는 객체의 갯수 반환
  7. empty() 큐에 하나도 없으면 true
  8. swap(priority_queue<T>& other) 현재 큐에 있는 원소들과 인수로 전돨된 원소들을 교환

우선순위 큐는 할당 연산자가 구현되어 있고, 각 복제 버전과 이동버전이 정의되어 있음.

우선순위 큐는 비교 연산자가 정의되어 있지 않다. 새원소를 추가하면 우선순위 큐의 유지에 필요한 정렬을 수행하느라 느려진다.