[C++ STL] Standard template library /Container adaptor

STL (Standard template library)

C++의프로그래밍 개발 효율성을 높여주는 라이브러리이다. C++ 국제 표준에서 제정만하고 구현은 개발자가 알아서 하는 것이다. data structure와 algorithm 등을 구현해둔 라이브러리이다.

 

container에 데이터를 저장할 수 있는 공간이다. vector, array, deque(덱): double ended que, list 등이 있다.

deque는 앞과 뒤 모두 in/out이 가능하다. 일반적인 큐처럼도 사용이 가능하다. vector와 array, deque는 모두 배열이어서 연속된 공간이 필요하다. 이런 연속되지 않은 공간을 사용하기 위해 C언어에서 SLL과 DLL을 사용했는데, STL 에서는 SLL은 forward list, DLL은 list로 구현되어 있다. forward list와 list의 경우 Linked list 기반이기 때문에 index에 의한 random access가 불가능하고 메모리 공간을 배열보다 더 사용하게 된다. 대신, 중간에 데이터를 삽입하고 삭제하는 것이 편리하다. 

 

iterator는 container안의 데이터에 대해서 통일된(접근하려는 대상에 상관없이) 접근 방법을 제공한다. 포인터라고 생각하면 된다. 배열로 구성이 되건, list이건 동일하게 순차적 접근이 가능하다. 

 

예시 코드>

1) 1,2,3,4,5를 넣는다.

#include <iostream>
#include <deque>
#include <iterator>

using namespace std;


int main() {
	deque<int> mydeque;

	mydeque.push_back(3);
	mydeque.push_back(4);
	mydeque.push_back(5);
	mydeque.push_front(1);
	mydeque.push_front(2);

	return 0;
}

2) 맨 앞, 맨 끝 요소를 읽는다.

	cout << "deque front: " << mydeque.front() << endl;
	cout << "deque back: " << mydeque.back() << endl;

3) 차례로 읽는다

	for (auto e = mydeque.begin(); e != mydeque.end(); e++) {
		cout << *e << " "; 
	}
	cout << endl;

4) 역순으로 읽는다

	for (auto e = mydeque.rbegin(); e != mydeque.rend(); e++) {
		cout << *e << " ";
	}
	cout << endl;

5) insert at the middle

	//2번 자리에 100을 넣는다.
	auto loc = mydeque.cbegin(); //c는 constant의 약자
	advance(loc, 1);
	mydeque.insert(loc, 100);

6) delete at the middle

	//4를 삭제
	loc = mydeque.cbegin();
	advance(loc, 4);
	mydeque.erase(loc);

 

 

 

Container adaptor

기존에 있는 container에 우리가 잘 아는 데이터 구조처럼 동작하게끔 한 겹을 더 씌워서 마치 그런 구조처럼 사용할 수 있도록 만드는 것이다. 실제로 자료를 저장하는 곳이 아니다. < add 'how to access' to catainer >

vector에 stack adaptor를 씌우면 stack처럼 쓸 수 있도록한다. stack, queue, priority_queue 등이 있다.

* stack : push, pop, top, empty, size

* queue: push, pop, front, back, empty, size

* priority_queue: push, pop, top, empty, size   (우선순위 제일 높은 애가 top에 있음)

 

스택 코드>

	//default container를 이용해서 stack을 만드는것
	stack<int, vector<int>> mystack;

	mystack.push(5);
	mystack.push(4);
	mystack.push(3);

	//top은 꺼내지 않고 맨위가 뭔지 보는 것
	//pop은 보지 않고 꺼내어 버리는 것

	cout << "top: " << mystack.top() << endl;
	cout << "size: " << mystack.size() << endl;
	cout << "empty: " << mystack.empty() << endl;

	while (mystack.empty() != true) {
		cout << mystack.top() << " ";
		mystack.pop();
	}
	cout << endl;

 

큐 코드>

	//default는 deque
	queue<int> myqueue;

	myqueue.push(5);
	myqueue.push(4);
	myqueue.push(3);

	cout << "front: " << myqueue.front() << endl;
	cout << "back: " << myqueue.back() << endl;
	cout << "size: " << myqueue.size() << endl;
	cout << "empty: " << myqueue.empty() << endl;

	while (myqueue.empty() != true) {
		cout << myqueue.front() << " ";
		myqueue.pop();
	}
	cout << endl;

 

object를 큐에 넣는 코드>

class Person
{
public:
	string name;
	int age;
	Person(string _name, int _age) : name(_name), age(_age) {};
	void printPersonInfo()
	{
		cout << name << "is" << age << "years old" << endl;
	}
};

int main(){
	queue<Person> classqueue;

	classqueue.push(Person("James",20));
	classqueue.push(Person("Cindy", 19));
	classqueue.push(Person("Jinho", 21));

	cout << "front: " << classqueue.front().name << endl;
	cout << "back: " << classqueue.back().name << endl;
	cout << "size: " << classqueue.size() << endl;
	cout << "empty: " << classqueue.empty() << endl;

	while (classqueue.empty() != true) {
		classqueue.front().printPersonInfo();
		classqueue.pop();
	}
	cout << endl;
}

 

*** 큐 안에 벡터를 넣는 코드는 동작을 하지 않는다.

queue<Person, vector<Person>> vqueue; 사용 불가능

error C2039 : 'pop_front': is not a member of 'std::vector<Person,std::allocator<Person>' 

 

 

 

 

우선순위 큐 코드>

	priority_queue<int> mypqueue;

	mypqueue.push(3);
	mypqueue.push(4);
	mypqueue.push(5);
	mypqueue.push(9);
	mypqueue.push(2);
	mypqueue.push(1);

	cout << "top: " << mypqueue.top() << endl;
	cout << "size: " << mypqueue.size() << endl;
	cout << "empty: " << mypqueue.empty() << endl;

	while (mypqueue.empty() != true) {
		cout << mypqueue.top() << endl;
		mypqueue.pop();
	}
	cout << endl;

 

 

** 우선순위를 정하는 방법

#include <iostream>
#include <iterator>
#include <vector>
#include <queue>

using namespace std;

class Person
{
public:
	string name;
	int age;
	Person(string _name, int _age) : name(_name), age(_age) {};
	void printPersonInfo() const
	{
		cout << name << "is" << age << "years old" << endl;
	}
};

class ComparePerson
{
public:
	bool operator()(Person& p1, Person& p2) {
		return (p1.age < p2.age);
	}
};

int main() {
	
	//Person object를 저장한다, 걔네들을 vector안에 넣고 
	//ComparePerson operator를 가지고 우선순위를 정함
	priority_queue<Person, vector<Person>, ComparePerson> mypqueue;

	mypqueue.push(Person("James",20));
	mypqueue.push(Person("Cindy", 19));
	mypqueue.push(Person("Jinho", 21));

	cout << "top: " << mypqueue.top().name << endl;
	cout << "size: " << mypqueue.size() << endl;
	cout << "empty: " << mypqueue.empty() << endl;

	while (mypqueue.empty() != true) {
		mypqueue.top().printPersonInfo();
		mypqueue.pop();
	}
	cout << endl;
	return 0;
}