[C++] STL (Standard Template Library) 1편 - Container

저번에 포스팅 한 Template는 Generic Programing을 위한 C++의 문법이었다. 

2024.01.23 - [Language/C++] - [C++] Template(템플릿)

[C++] Template(템플릿)

 

Generic은 일반이라는 말이다. 우리가 평상시에 일반화 하면 안된다고 하지만 Generic 프로그래밍의 장점은 중복 코드를 줄일 수 있다는 것이다. 생각해보면 다 똑같이 둔다면 관리도 용이할 것 같다. 그게 C++ 에서 Template이다.

 

우리가 Java의 List, ArrayList, Map을 살펴보았을때, 이는 자바에서 Package로 제공하는 일종의 Generic이다. C++도 똑같이 Pacakage가 지원해주는건 아니고 STL(표준 템플릿 라이브러리)로 지원하게 된다.

( 발명자는 HP 리서치팀의 연구원들 이었다. 참... 대단한 사람 많다)

 

 

# STL(Standard Template Library) 구분

표준 템플릿 라이브러리는 3가지 템플릿으로 구분 지을 수 있다.

• Container(컨테이너)
• Iterator(반복자)
• Algorithm(알고리즘)

# STL(Standard Template Library) Container

같은 타입의 여러 객체를 저장하는 일종의 집합이며, 클래스 Template이며 컨테이너에 변수를 선언할 때 포함할 요소의 자료형을 명시할 수 있다.

컨테이너 종류	설명	컨테이너
시퀀스 컨테이너	데이터를 선형으로 저장하며, 특별한 제약이나 규칙이 없는 가장 일반적인 컨테이너	vector, deque, list, forward_list
연관 컨테이너	데이터를 일정 규칙에 따라 조직화하고 저장하고 관리하는 컨테이너	set, multiset, map, multimap
컨테이너 어댑터	간결함과 명료성을 위해 인터페이스를 제한한 시퀀스나 연관 컨테이너의 변형 단, 반복자를 지원하지 않고 STL알고리즘에서는 사용할 수 없다.	stack, queue, priority_queue

 

# Sequence Cotainer

일반적인 선형자료구조를 구현한 내용이다. 저장하는데 특별한 제약이나 규칙이 없고, 삽입된 요소 순서대로 유지하게 된다. 몇가지 요구 사항이 있는데,요소가 직선순서대로 배치되어야하며, 반복자가 이동하면서 요소들의 순서가 변하지 않아야한다. 순서를 갖기 때문에 특정 위치를 참조해서 연산이 가능해야한다.

 

• vector
  • 동적 배열이다 ➡️ JAVA에서 list, Array List랑 비슷한듯
  • 동적배열은 결국 요소가 추가될때마다 메모리를 재할당 한다는 뜻이다.
  • 임의접근이 가능하다.

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

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

	vc.push_back(40);				// vector 요소의 추가 
	cout << "현재 벡터의 크기는 " << vc.size() << "입니다." << endl;
	cout << "현재 벡터의 네 번째 요소는 " << vc[3] << "입니다." << endl;
	
	cout << "현재 벡터의 모든 요소는 다음과 같습니다 :" << endl;
	copy(vc.begin(), vc.end(), ostream_iterator<int>(cout, " "));
	return 0;
}

 

위를 보면 알겠지만 push_back 키워드를 통해 데이터를 삽입 할 수가 있다. 

여러 함수가 있는데,  size() ➡️ 반환값: vector 크기 , begin() ➡️ 반환값: 반복자 시작점을 반환, end() ➡️ 반복자  마지막 값을 반환

 

• deque(데큐)
  • 양쪽끝으로 데이터를 뺄 수 있는 큐를 붙여놓은 구조 (front 와 rear 둘다 in/out 가능)
  • 즉, 컨테이너 양끝에서 빠르게 데이터 삽입과 삭제에 유리한 구조

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

int main()
{
  deque<int> dq;

  for(int i = 1; i <= 10; i++){
     if(i > 5) dq.push_back(i);
     else dq.push_front(i); 
  }

  for(int i = 0; i < dq.size(); i++){
     cout << dq[i] << " ";
  }
	
  cout << endl << "현재 데큐의 첫 번째 요소는 " << dq.front() << "입니다." << endl;

  cout << endl;

  return 0;
}

//결과값
5 4 3 2 1 6 7 8 9 10 
현재 데큐의 첫 번째 요소는 5입니다.

 

사실 deque를 이해하면서 어디서 front고 어디가 back인지 몰랐다. 결과값을 보면 알 수 있다.

내가 짠 함수는 5보다 크면 push_back()을 통해서 넣고 있다. 

• push_front(); ➡️ 왼쪽부터 넣는다.
• push_rear(); ➡️ 오른쪽 부터 넣는다.

그렇다면 front();는? 왼쪽 기준 가장 앞단에 있는 데이터 이다. 왼쪽이 앞이고 오른쪽이 뒤다.

 

• list
  • 이중연결리스트의 템플릿 표현이다.
  • 선형 자료구조중 하나인 이중연결리스트는 데이터 삽입 삭제가 빠르다.
  • 임의의 접근은 불가능하다.
  • 삽입이 빠르다는건 정렬이 빠르다는 것을 의미한다. 

#include <iostream>
#include <iterator>
#include <list>
using namespace std;

int main(void)
{
	list<int> ls = {3, 1, 3, 1, 4, 5, 4, 5};	// list 객체의 선언 및 초기화 
	list<int> ls1 = {6,7,8,9,10};
	
	ls.splice(ls.begin(),ls1);
	cout << "현재 리스트의 모든 요소는 다음과 같습니다 :" << endl;
	copy(ls.begin(), ls.end(), ostream_iterator<int>(cout, " "));
	cout << endl;
	
	ls.merge(ls1);
	cout << "현재 리스트의 모든 요소는 다음과 같습니다 :" << endl;
	copy(ls.begin(), ls.end(), ostream_iterator<int>(cout, " "));
	cout << endl;
	
	ls.sort();	// 1, 2, 3, 4, 5
	cout << "현재 리스트의 모든 요소는 다음과 같습니다 :" << endl;
	copy(ls.begin(), ls.end(), ostream_iterator<int>(cout, " "));
	cout << endl;
	
	ls.unique();	// 1, 2, 3, 4, 3, 5
	cout << "현재 리스트의 모든 요소는 다음과 같습니다 :" << endl;
	copy(ls.begin(), ls.end(), ostream_iterator<int>(cout, " "));
	return 0;
}

 

vector와 list 차이에 대해서 많은 레퍼런스가 나와있는데 일단 생긴거 부터 다르다. vector는 동적 배열이고 list는 잘 알고 있듯이 이중 연결리스트로 구현되어있어서 삽입삭제가 용이한 대신 임의적으로 접근이 불가능하다. 임의적으로 접근이 불가능하다는 것 vector와 같이 특정 인덱스로 접근이 불가능하다는 것이다. ( vc[i]와 같이 )

 

# Associate Cotainer

위에서는 시퀀스 컨테이너에 대해 알아보았다. 다시 복습해보면 순서가 있는 컨테이너 템플릿을 시퀀스 템플릿이라고 한다. 연관 컨테이너에서는 순서가 없고 (key, value)를 한쌍으로 저장하는 컨테이너이다. 그래서 원하는 요소를 찾을 때 빨리 찾을 수 있지만 내가 원하는 위치에 리스트를 저장할 수는 없다.
(java의 Map과 유사하다.)

 

• set과 multiset
  • set은 중복된 값을 허용하지 않고, muti set은 중복된 값을 허용한다.
  • 또한, 두가지다 모두 오름차순 정렬을 통해서 들어간다. 

#include <iostream>
#include <iterator>
#include <set>
using namespace std;

int main(void)
{
	int arr[7] = {10, 20, 30, 40, 50,90,90};	// 배열 생성 및 초기화 
	set<int> st(arr, arr+7);			// 배열의 일부 요소를 가지고 셋 컨테이너를 생성함. 
	cout << "현재 set의 모든 요소는 다음과 같습니다." << endl;
	copy(st.begin(), st.end(), ostream_iterator<int>(cout, " "));
	cout << endl;
	
	st.insert(60);	// 요소의 추가 
	st.insert(70);	// 요소의 추가 
	st.erase(20);	// 요소의 삭제 
	cout << "현재 set의 모든 요소는 다음과 같습니다." << endl;
	copy(st.begin(), st.end(), ostream_iterator<int>(cout, " "));
	
	cout << endl;
	cout << endl;
	cout << "멀티셋 확인" << endl;
	multiset<int> mst(arr, arr+7);			// 배열의 일부 요소를 가지고 셋 컨테이너를 생성함.
	cout << "현재 multiset의 모든 요소는 다음과 같습니다." << endl;
	copy(mst.begin(), mst.end(), ostream_iterator<int>(cout, " "));
	cout << endl;
	
	mst.insert(70);	// 요소의 추가 
	mst.insert(70);	// 요소의 추가 
	mst.erase(20);	// 요소의 삭제 
	cout << "현재 multiset의 모든 요소는 다음과 같습니다." << endl;
	copy(mst.begin(), mst.end(), ostream_iterator<int>(cout, " "));
	return 0;
}

 

• map과 multimap
  • key, value로 데이터를 관리
  • 검색속도가 빠르다.
  • key 중복을 허용하지 않는다. 단, mutimap은 1:m 맵핑이 가능하다.

#include <iostream>
#include <iterator>
#include <map>
using namespace std;

int main(void)
{
	map<string, int> mp;
	mp.insert(pair<string, int>("국어", 80));	// 익명의 pair 객체를 생성하여 추가함. 
	mp["수학"] = 100;							// 첨자 연산자를 이용하여 추가함. 
	
	cout << "현재 맵의 모든 요소는 다음과 같습니다." << endl;
	map<string, int>::iterator it;
	for(it = mp.begin(); it != mp.end(); it++)
	{
		cout << it->first << " : " << it->second << endl;
	}
	return 0;
}

 

 

# Cotainer Adapter

컨테이너 어댑터는 기존 컨테이너들에서 인터페이스르 제한하여 만든 기능이 제한되거나 변형된 컨테이너이다. 특정 형태에서만 동작하도록 수행이 이루어진다.

• stack ➡️ vector 인터페이스에 기반
• queue ➡️ deque 인터페이스에 기반
• 우선순위 큐 ➡️ vector 인터페이스에 기반

위에는 자료구조에서 다루었던 내용과 같기 때문에 아래를 참고하면 좋을거 같다.(자바랑 문법만 다를뿐!)

2023.11.16 - [Computer Science/Data Structure] - [Data Structure] 선형 - 스택(Stack)

2023.11.15 - [Computer Science/Data Structure] - [Data Structure] 선형 - 큐(Queue)

[Data Structure] 선형 - 큐(Queue)

[Data Structure] 선형 - 스택(Stack)

---

사실은 stl 전문을 다룰려고 했지만 전문을 다루지는 않았다. iterator나 alogrithm이 남아있다. 사실 자바를 공부하면서 C++를 공부하는 과정이 재밌다. 뭔가 자료구조를 더 딥하게 들어갈 수 있고 메모리 할당과 메모리 해제 등 뭔가 더 Computer Science적인 요소들이 포함되어 있는 것 같다. 차후에 자료구조를 작성하면서 공부했던 내용을 좀 더 다듬을 수 있을 것같다.

 

다음번에는 된다면 iterator와 algorithm까지 통째로 작성토록하겠다.