[C++] STL ( pair, vector, list, iterator, algorithm 사용 예시 코드 )

[C++] STL 정리 ( pair, vector, stack, queue, deque, map, set, algorithm )

위 포스팅에서 STL에 대해 전반적으로 총정리를 해봤습니다. 오늘은 이 중에서도 자주 사용되는 pair, vector, list 컨테이너에 대해 집중적으로 살펴보고 iterator 의 응용, 그리고 algorithm 을 사용해보는 방법까지 알아보도록 하겠습니다.

 

STL(Standard Template Library) 는 이름 그대로 C++ 표준 템플릿 라이브러리입니다. 이전에 템플릿에 대해 배웠는데 미리 만들어놓은 템플릿을 사용하자! 라는 것이죠. PS 에 있어서 매우 필수적이고 응용하는 것이 중요한 라이브러리입니다.

 

다른 이름으로는 일반화 라이브러리 (Generic library) 라고도 불립니다. 오늘 알아볼 STL의 3개의 분류는 다음과 같습니다.

• 컨테이너 클래스 : 자료구조 (stack, queue, vector, list ... )
• 이터레이터 : 모든 자료구조의 원소에 동일한 접근 방법을 제공(마치 포인터 같은 역할, 포인터와는 다르다.)
• 알고리즘 : 함수(sort, reverse, swap, size ... )

예제 코드를 중심으로 사용법에 대해 알아보도록 하겠습니다.

 

 pair 사용법

pair 는 first 와 second 라는 멤버 변수를 가지고 있는 자료형입니다. 사용법은 템플릿의 구체화 사용방법과 동일합니다. pair 자료형은 <utility> 파일에 선언되어 있어 #include <utility> 를 사용해야 하지만 제가 알기로는 <iostream> 내에 포함되어 있어서 <utility> 를 따로 inlcude 하지 않아도 사용할 수 있습니다.

 

생성자로는 make_pair(a, b) 함수 생성자를 사용하거나, 선언할 때 이름(a, b) 식의 매개변수 생성자를 통해 값을 pair 에 집어넣을 수 있습니다. 

// pair 사용
#include <iostream>
#include <utility>
using namespace std;

int main(void) {
	pair<int, int> p1;
	p1 = make_pair(10 , 20);			// 함수 생성자
	pair<int, int> p2(30, 40);			// 생성자
	pair<pair<int, int>, pair<double, double>> pp2;	// pair 내부에 또 pair 사용 가능
	pp2 = make_pair(make_pair(100, 200), make_pair(10.2, 34.4));

	printf("p1 = ( %d %d )\n", p1.first, p1.second);
	printf("p2 = ( %d %d )\n", p2.first, p2.second);

	printf("pp2.first = ( %d %d )\n", pp2.first.first, pp2.first.second);
	printf("pp2.second = ( %lf %lf )\n", pp2.second.first, pp2.second.second);
}

pair 를 사용할 때는 first 와 second 가 마치 template <typename T1, typename T2> 와 같이 2개의 제너릭 타입으로 선언되어 있기 때문에 다른 자료형을 넣는 것이 가능합니다. main 함수의 4번째 줄을 보면 pair의 원소로 다시 pair 를 넣는 것도 가능하기 때문에 선언할 때 구체화 타입을 잘 써줘서 이를 선언하고 사용하면 됩니다. 생성자로 선언하는 방법만 알아도 사용하는데 지장은 없지만 make_pair 함수 정도는 알아놓는 것이 좋습니다.

 

 

 vector 사용법

 

매우 자주 사용하는 동적 배열입니다. 임의의 위치에 있는 원소의 접근과 뒤에서 원소를 추가하는 연산은 O(1) 을 보장합니다. 사용하려면 <vector> 를 include 한 이후 사용합니다. 예제 코드를 중점으로 확인해보도록 하겠습니다.

 

vector 생성자

vector<[type]> v	[type]형의 빈 vector를 생성
vector<[type]> v(n)	0으로 초기화 된 n개의 원소를 가지는 [type]형의 vector를 생성
vector<[type]> v(n, m)	m으로 초기화 된 n개의 원소를 가지는 [type]형의 vector를 생성
vector<[type]> v2(v1)	v1을 복사하여 v2 vector를 생성
vector<vector<[type]>> v	[type]형의 2차원 vector 생성
vector<[type]> v = {a1, a2, a3, ... }	{a1, a2, a3, ...} 으로 초기화 된 [type]형의 vector 생성

 

vector 멤버함수

v.assign(n, m)	m으로 n개의 원소 할당
v.at(index)	index번째 원소를 반환한다. 유효한 index인지 체크하기 때문에 안전하다.
v[index]	index번째 원소를 반환한다. 배열과 같은 방식이며 유효성을 체크하지 않는다.
v.front()	첫 번째 원소를 반환한다.
v.back()	마지막 원소를 반환한다.
v.clear()	모든 원소를 제거한다. 메모리는 그대로 남아있게 된다. (size는 줄어들고 capacity는 유지)
v.begin()	첫 번째 원소를 가리키는 반복자(iterator)를 반환한다.
v.end()	마지막 원소 다음을 가리키는 반복자(iterator)를 반환한다.
v.push_back(m)	마지막 원소 뒤에 원소 m을 삽입한다.
v.pop_back()	마지막 원소를 제거한다.

v.rbegin()	거꾸로 시작해서 첫 번째 원소를 가리키는 반복자(iterator)를 반환한다.
v.rend()	거꾸로 시작해서 마지막 원소를 가리키는 반복자(iterator)를 반환한다.
v.reserve(n)	n개의 원소를 저장할 공간을 예약한다.
v.resize(n)	크기를 n개로 변경한다. 커진 경우에는 빈 곳을 0으로 초기화한다.
v.resize(n, m)	크기를 n개로 변경한다. 커진 경우에는 빈 곳을 m으로 초기화한다.
v.size()	원소의 개수를 반환한다.
v.capacity()	할당된 공간의 크기를 반환한다. (size()와 다름)
v2.swap(v1)	v1과 v2를 swap한다.
v.insert(iter, m)	iter가 가리키는 위치에 m의 값을 삽입한다. 그리고 해당 위치를 가리키는 반복자(iterator)를 반환
v.insert(iter, k, m)	iter가 가리키는 위치부터 k개의 m 값을 삽입한다. 다음 원소들은 뒤로 밀린다.
v.erase(iter)	iter 반복자가 가리키는 원소를 제거한다. capacity는 그대로 유지된다.
v.erase(start, end)	start 반복자부터 end 반복자까지 원소를 제거한다.
v.empty()	vector가 비어있으면 true를 반환한다.
v.max_size()	v가 담을 수 있는 최대 원소의 개수(메모리 크기) 반환
v.shrink_to_fit()	capacity의 크기를 vector의 실제 크기에 맞춤

#include <iostream>
#include <vector>
using namespace std;

class CPoint {
	int x, y;
public:
	CPoint(int a = 0, int b = 0) :x(a), y(b) {}
	void Print() { cout << "(" << x << ", " << y << ")" << endl; }
};

int main() {
	int i;
	vector<CPoint> cAry(3);
	for (i = 0; i < 3; i++) cAry[i] = CPoint(i + 1, i + 1);
	for (i = 0; i < 5; i++) cAry.push_back(CPoint(10 * i + 1, 20 * i + 1));
	for (i = 0; i < cAry.size(); i++) cAry.at(i).Print();
}

우선 이터레이터는 사용하지 않는 vector 의 멤버 함수를 응용한 예제 코드입니다. size() 를 통해 vector 의 원소 개수를 알아낼 수 있고, vector 에 객체를 저장할 수 있다는 것도 위 코드로 확인할 수 있습니다. .at(i) 는 [i] 랑 똑같은 역할을 합니다. push_back 은 앞으로 정말 자주 사용하게 될텐데, 배열의 마지막에 데이터를 삽입하는 멤버 함수입니다.

 

// vector 클래스에 pair 원소를 갖는 vector 객체
#include <iostream>
#include <vector>
#include <utility>
using namespace std;

int main() {
	const int size = 3;
	vector<pair<int, string>> vPair;
	string strarray[] = { "Song", "Computer", "Blog" };
	for (int i = 0; i < size; i++)
		vPair.push_back(make_pair(i, strarray[i]));
	for (int i = 0; i < size; i++) {
		cout << "vPair[" << i << "] = " << "( " << vPair[i].first << " " << vPair[i].second << " )" << endl;
	}
}

vector 의 원소로는 pair 도 들어갈 수 있습니다. pair 안에도 pair 이 들어갈 수 있으니 무궁무진하게 활용할 수 있겠죠?

 

// vector 함수 인자 전달
#include <iostream>
#include <vector>

void printVector(vector<int> &v) {
	for (int i = 0; i < v.size(); i++)
		cout << v.at(i) << ' ';
	cout << endl;
}

int getAverage(vector<int> &v) {
	int sum = 0;
	for (int i = 0; i < v.size(); i++)
		sum += v.at(i);
	return sum / v.size();
}

using namespace std;
int main() {
	vector<int> v; // 벡터 객체 생성
	cout << "정수를 5개 입력하세요>>";
	for (int i = 0; i < 5; i++) {
		int num;
		cin >> num;
		v.push_back(num); //입력받은 수를 벡터에 저장
	}
	printVector(v); // 벡터의 모든 수 출력
	cout << "평균 = " << getAverage(v) << endl; // 평균 계산 후 출력
}

vector 를 함수 인자로 전달할 때는 어떤 것을 저장하는지 구체화 한 것을 인자로 전달해야하고 중요한 점이 참조 변수로 전달하는 것이 좋다는 점입니다. 참조 변수로 전달하지 않아도 실행은 되지만, 참조변수로 전달하지 않는 경우 vector 전체가 복사되어 함수에 전달됩니다. vector 가 커지면 커질수록 굉장히 비효율적인 코드가 되기 때문에 값을 변경하지 않는 경우에도  참조 변수로 전달하는 것이 일반적입니다.

 

---

 

 

 이터레이터 (iterator)

 

이터레이터는 반복자 라는 이름으로도 많이 불립니다. 이터레이터는 일종의 포인터와 유사한 역할을 하는 객체 입니다. 여러가지 컨테이너의 원소를 가리킬 때 사용합니다. 사용법은 구체적인 컨테이너를 지정하여 반복자 변수를 생성하여 보통 .begin() 과 .end() 와 묶어서 많이 사용합니다. 사용 예를 보면 금방 이해할 수 있습니다.

 

포인터와 유사한 역할을 하나 주소를 저장하는 변수는 아닌 객체입니다. 그런데도 포인터 연산과 비슷하게 ++ 연산이나 +기로 컨테이너의 다음 원소로 접근할 수 있는데, 이는 컨테이너 내부에서 iterator 에 대한 연산자 중복이 구현되어 있기 때문입니다. 일반적으로 iterator 는 다음과 같이 동작합니다.

 

1. begin() 함수로 시작하여 컨테이너의 첫 번째 요소를 가리킨다.
2. end() 함수로 종료하여 컨테이너의 마지막 요소 다음을 가리킨다.
3. ++ 연산자를 사용해 다음 요소로 이동한다.
4. *연산자를 이용해 현재 iterator 가 가리키는 요소에 접근한다.

조금 주의해야 할 부분은 .end() 함수가 마지막 요소를 가리키는 것이 아니라 마지막 요소의 다음을 가리킨다는 점입니다.

#include <iostream>
#include <vector>
using namespace std;

int main() {
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);

	vector<int>::iterator it;

	for (it = v.begin(); it != v.end(); it++)
		*it *= 2;

	for (it = v.begin(); it != v.end(); it++)
		cout << *it << ' ';


	// 동작은 하지만 사용하진 말자. 수행된다 정도만 체크
	int i = 0;
	for (it = v.begin(); i < v.size(); i++)
		cout << *(it+i) << ' ';
}


// 출력 결과 : 2 4 6 2 4 6

마지막에 iterator 도 포인터 연산처럼 더하기로 되나? 라고 체크를 해보았는데요, 수행되긴 수행됩니다. 그래도 저런 방식은 일반적이지 않으니 사용하지 말고 2번째처럼 사용하도록 합시다.

 

 

 

 list 사용법

 

list 컨테이너는 노드 기반의 컨테이너로 원소가 노드 단위로 구성됩니다. 연결 리스트를 구현해놓은 것으로, 이중 연결리스트로 구현되어 있습니다. 연결 리스트로 구성되어 있는 자료 구조의 경우 vector 같은 배열 형태의 자료구조보다 삽입/삭제가 매우 빠르다는 장점이 있습니다. 따라서 사용하는 데이터가 삽입/삭제가 많이 수행되는 경우는 list 컨테이너를, 삽입/삭제가 많이 이루어지지 않으면 vector 컨테이너를 사용하는 것이 좋습니다.

 

list 컨테이너의 경우 내부 구조는 리스트지만 사용은 거의 배열과 유사하게 사용할 수 있도록 구현되어 있으나 [] 연산자는 제공하지 않습니다. 대신 이터레이터를 사용해 배열과 유사한 방식으로 접근이 가능합니다. 또한  #include <list>를 추가해줘야 list 를 사용할 수 있습니다.https://songsite123.tistory.com/19

 

list 멤버함수

멤버 함수 list it(100, 5);
lt.back()	lt의 마지막 원소를 참조
p=lt.begin()	p는 lt의 첫 원소를 가리키는 반복자
lt.empty()	lt가 비었는지 조사
p=lt.end()	p는 lt의 끝을 표식하는 반복자
lt.front(), it.back()	lt의 첫 번째(마지막) 원소를 참조
q=lt.insert(p,x)	p가 가리키는 위치에 x 값을 삽입한다. q는 삽입한 원소를 가리키는 반복자
lt.insert(p,n,x)	p가 가리키는 위치에 n 개의 x 값을 삽입
lt.insert(p,b,e)	p가 가리키는 위치에 반복자 구간 [b,e)의 원소를 삽입
lt.pop_back()	lt의 마지막 원소를 제거
lt.pop_front()	lt의 첫번째 원소를 제거
lt.push_back(x)	lt의 끝에 x를 추가
lt.push_front(x)	lt의 앞쪽에 x를 추가
lt.size()	lt 원소의 개수 반환
lt.sort()	lt의 모든 원소를 오름 차순 으로 정렬
lt.sort(pred)	lt의 모든 원소를 pred(조건자)를 기준으로 정렬
lt.swap(lt2)	lt와 lt2를 swap

// list 사용
#include <iostream>
#include <list>
using namespace std;

int main(void) {
	int i = 0;
	list<int> MyList(5, 10); // int형 5개, 초기값 10인 list 생성
	list<int>::iterator it;
	for (it = MyList.begin(); it != MyList.end(); it++) {
		*it = *it * (i + 1);
		cout << *it << ' ';
		i++;
	}
	cout << endl;
	cout << MyList.front() << endl;
	cout << *MyList.begin() << endl;
	cout << MyList.back() << endl;
	cout << *(--MyList.end()) << endl;
}

다양한 방법으로 list 도 원소에 접근할 수 있습니다. iterator 를 사용하면 vector 와 거의 동일한 방식으로 원소에 접근합니다.

#include <iostream>
#include <list>
#include <vector>
using namespace std;
int main() {
	list<int> mylist;
	list<int>::iterator it;
	for (int i = 1; i <= 5; i++) mylist.push_back(i);
	// 1 2 3 4 5

	it = mylist.begin();
	it++; // 두번째 원소를 가리킨다.
	mylist.insert(it, 10);	// 1 10 2 3 4 5, it 는 3번째 원소를 가리킨다.
	mylist.insert(it, 2, 20);	// 1 10 20 20 2 3 4 5, it 는 5번째 원소를 가리킨다.
	it--; // 2번째 20, 즉 4번째 원소를 가리킨다.
	vector<int> myvector(2, 30);	// 30 30 vector
	mylist.insert(it, myvector.begin(), myvector.end()); // 1 10 20 30 30 20 2 3 4 5
	cout << "mylist contains : ";
	for (it = mylist.begin(); it != mylist.end(); it++) cout << *it << ' ';
}

다양한 insert 를 연습해보는 예제입니다. insert 는 가리키고 있는 위치에 집어넣고 나머지를 쭉 뒤로 밀어준다? 라고 생각하셔도 좋습니다. 이 삽입 과정은 연결리스트로 이루어져있으므로 포인터를 바꾸는 4번의 연산으로 이루어지기 때문에 vector 에 비해 매우 빠릅니다.

 

 

 

 algorithm 사용법

 

#include <algorithm> 을 통해 사용할 수 있는 STL 알고리즘은 다양한 함수를 제공합니다. 여러 타입에 적용할 수 있는 템플릿 함수이면서, 전역 함수입니다. 즉 위처럼 멤버 함수로 사용하지 않아도 된다는 것이죠. 일반적으로 iterator 와 함께 동작합니다. 가장 많이 사용하는 sort() 함수에 대한 예제 코드만 살펴보도록 하겠습니다.

 

vector<int> v;
...
// void sort(RandomAccessIterator first, RandomAccessIterator last);
sort(v.begin(), v.begin()+3); // v.begin()에서 v.begin()+2까지, 처음 3개 원소 정렬
sort(v.begin()+2, v.begin()+5); // 벡터의 3번째 원소에서 v.begin()+4까지, 3개 원소 정렬
sort(v.begin(), v.end()); // 벡터 전체 정렬


// void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

 

sort 함수의 첫 번째 매개변수는 정렬을 시작한 원소의 주소, 두 번째 매개변수는 정렬 범위의 마지막 원소 다음 주소입니다. 그리고 매개 변수 3개를 사용하는 경우 3번째는 정렬 기준을 정해주는 comp 함수가 매개변수로 들어갑니다. comp 함수를 통해 정렬하는 기준을 내림차순으로 바꾸거나 혹은 다양하게 설정해줄 수 있습니다.

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	vector<int> v;

	cout << "5개의 정수를 입력하세요 : ";
	for (int i = 0; i < 5; i++) {
		int n;
		cin >> n;
		v.push_back(n);
	}

	sort(v.begin(), v.end());
	vector<int>::iterator it;
	for (it = v.begin(); it != v.end(); it++) cout << *it << ' ';
}

가장 기본적인 형태의 오름차순 sort 입니다. 내림차순으로 정렬하기 위해서는 comp 함수를 구현하여 3번째 매개변수로 넣어주면 됩니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void PrintVector(vector<int> v, string name) {
	vector<int>::iterator it;
	cout << ">> " << name << " : ";
	for (it = v.begin(); it != v.end(); it++) cout << *it << ' ';
	cout << endl;
}

bool IntCompare(int a, int b) { return (a > b) ? true : false; }

int main() {
	vector<int> v;

	cout << "5개의 정수를 입력하세요 : ";
	for (int i = 0; i < 5; i++) {
		int n;
		cin >> n;
		v.push_back(n);
	}

	PrintVector(v, "정렬 전");
	sort(v.begin(), v.end());
	PrintVector(v, "오름차순 정렬 후");
	sort(v.begin(), v.end(), IntCompare);
	PrintVector(v, "내림차순 정렬 후");
}

 

 

마지막으로 연산자 오버로딩을 통해 객체를 오름차순으로 정렬하는 예시를 보며 마무리하도록 하겠습니다. sort 함수가 내부적으로 < 연산을 진행하기 때문에 < 연산자를 통해 객체의 멤버 정렬을 하여 bool 로 내보내면 comp 매개변수 없이도 정렬이 가능합니다.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

class CPoint {
	int x, y;
public:
	CPoint(int a = 0, int b = 0) : x(a), y(b) {}
	bool operator<(CPoint&);
	friend ostream& operator<<(ostream& os, CPoint& Po);
};

bool CPoint::operator<(CPoint& Po) {
	if ((x + y) < (Po.x + Po.y)) return true;
	else return false;
}

ostream& operator<<(ostream& os, CPoint& Po) {
	os << "(" << Po.x << ", " << Po.y << ")"; 
	return os;
}

void PrintVector(vector<CPoint> intV, string name) {
	vector<CPoint>::iterator iter;
	cout << ">> " << name << " : ";
	for (iter = intV.begin(); iter != intV.end(); iter++)
		cout << *iter << " ";
	cout << endl;
}

int main(void) {
	vector<CPoint> intV(5); intV[0] = CPoint(5, 3);
	intV[1] = CPoint(2, 9); intV[2] = CPoint(1, 1);
	intV[3] = CPoint(2, 5); intV[4] = CPoint(3, 7);
	PrintVector(intV, "정렬 전");
	sort(intV.begin(), intV.end()); //기준 모든 원소 정렬, < 연산자 오버로딩을 클래스에 포함시키면 별도 comp 전달 X
	PrintVector(intV, "정렬 후");
}