[C++] STL

📌STL(Standard Template Library)

표준 템플릿 라이브러리. 자료구조(컨테이너, 이터레이터, 알고리즘)를 모아놓은 라이브러리.

컨테이너(자료구조), 반복자(iterator), 알고리즘, 수치

기능을 제공하고 손쉽게 구현할 수 있도록 재사용을 목적으로 만들어진 라이브러리. C언어는 CRT(C Runtime Library)라는 이름의 라이브러리를, C++은 C++ Standard Library를 가지고 있다. 1994년 C++ 표준 라이브러리에 STL이 추가되었다.

표준 템플릿 라이브러리라는 뜻 그대로 일반화 프로그래밍(Generic Programming)을 기반으로 무분별한 여러가지 형태의 코드를 지양하고 표준화된 코드를 지향한다. 표준이므로 이식성이 좋다.

각 자료구조마다 성능의 차이가 있으므로 검색, 정렬, 삽입, 삭제에 최적화된 자료구조를 적절히 골라 사용한다.

예외 처리가 쉽지 않다는 단점이 있다.

 

📌컨테이너(Container)

Java의 컬렉션과 유사한 개념으로 데이터의 집합을 저장하고 관리하는데 사용한다.

• 시퀀스 컨테이너(순차 컨테이너) (Sequence Containers)
  • vector 동적 배열로, 크기가 자동으로 조정된다. 인덱스를 통해 접근할 수 있으며, 효율적인 끝에 요소 추가/제거를 지원한다. 중간 삽입 삭제는 요소 개수에 따라 처리 속도가 비례한다. 모든 요소를 뒤로 밀거나 앞으로 당기기 때문. 유사) 동적배열, arraylist
  • deque 양쪽 끝에서 빠르게 삽입/삭제가 가능한 데큐(더블 엔디드 큐). 성능 또한 벡터와 마찬가지로 요소 개수에 따라 처리 속도가 비례한다.
  • list 양방향 연결 리스트로, 임의의 위치에서의 삽입과 삭제가 효율적. 요소의 삽입 및 삭제가 위치와 상관없이 같은 속도. 각각의 노드가 포인터로 연결되어있다.
  • array 고정 크기의 배열. std::array는 크기가 컴파일 타임에 결정된다.
• 정렬 연관 컨테이너 (Sort Associative Containers)
  • 연관된 다른 타입들을 담을 수 있는 컨테이너. 키를 사용하여 데이터를 신속하게 찾아낼 수 있음. 실행 시 크기를 동적으로 변경할 수 있음.
  • set 고유한 요소들을 정렬된 상태로 저장한. 키의 중복은 허용하지 않는다. 원하는 키를 빠르게 찾아낸다.
  • map 키-값 쌍을 저장하며, 키를 통해 값을 빠르게 조회할 수 있다. 키의 중복은 허용하지 않는다. 키를 사용하여 원하는 값, 즉 객체를 빠르게 찾아낸다. key:value
  • multiset 중복을 허용하는 정렬된 집합.
  • multimap 중복된 키를 허용하는 키-값 쌍의 집합.
• 비순차 컨테이너 (Unordered Containers)
  • unordered_set 해시 기반의 집합으로, 요소들은 정렬되지 않음.
  • unordered_map 해시 기반의 키-값 쌍의 집합.
  • unordered_multiset 해시 기반의 중복을 허용하는 집합.
  • unordered_multimap 해시 기반의 중복된 키를 허용하는 키-값 쌍의 집합.
• 반복자(Iterator)
  • 컨테이너(또는 배열)의 요소를 순차적으로 읽기 위해서는 요소의 타입이 무엇인지 알아야한다. 요소의 메모리 크기만큼을 이동하며 읽어야 올바른 데이터를 읽을 수 있기 때문이다. 사용자가 크기나 타입을 신경쓰지 않고도 모든 요소를 순차적으로 읽을 수 있도록 제공해주는 것이 바로 반복자다. 컨테이너의 요소를 가리키는 객체. 컨테이너의 시작부터 끝까지 이동하면서 요소를 읽거나 쓰기 위해 사용한다.
• 알고리즘(algorithm)
  • 정렬 및 검색하는 알고리즘을 구현한 함수.
  • 변경 불가 순차 알고리즘
  • 변경 가능 순차 알고리즘
  • 정렬 알고리즘
  • 범용 수치 알고리즘
• 기타
  • stack: LIFO(Last In First Out) 방식의 컨테이너.
  • queue: FIFO(First In First Out) 방식의 컨테이너.
  • priority_queue: 우선순위가 있는 큐로, 가장 높은 우선순위를 가진 요소를 우선적으로 꺼낸다.

 

 

📌벡터(Vector)

일반화된 컨테이너 중 가장 많이 사용된다. 필요한 크기만큼 메모리를 자동으로 재할당하여 늘릴 수 있다.(동적 배열) 템플릿 기반으로 타입에 무관함.

초기 생성된 길이만큼 데이터가 꽉 차있을 때 더 넣으려고 시도하면 내부에서 크기를 늘린다.

`vector<T> vectorName;` `vector<int> intVector;` `vector<int> intVector(5);`

배열처럼 인덱스로 요소를 가져올 수 있다.

 

	for (int i = 0; i < vec.size(); i++) {
		cout << vec[i] << endl;
	}

 

 

📌데크(Deque)

벡터와 유사하나 양쪽 끝에서 데이터를 삽입 삭제할 수 있는 컨테이너. 앞/중간 인덱스에 데이터를 삽입할 경우 모든 요소의 인덱스가 뒤로 밀리면서 성능이 떨어지는 벡터의 단점을 보완하기 위해 만들어진 컨테이너.

`deque<T> dqName; deque<int> dq;`

 

📌리스트(List)

 

이중 연결 리스트로 구현된 컨테이너. 각각의 요소가 포인터로 연결되어있다. 데이터가 물리적으로 인접해 있지 않고, 논리적인 순서를 기억하여 포인터로 이전 또는 다음 노드를 가리키고 있기 때문에 데이터 삽입 및 삭제 속도가 일정하다.

list<T> li; list<int> li;

 

📌 연결리스트(Linked-List)

 

요소들이 인접해있는 것이 아니라 메모리 도처에 흩어져서 자신의 이전 또는 다음 요소의 위치를 포인터로 가리키고 있는 리스트. 추상적 순서와 물리적 순서가 일치하는 배열과 달리 연결리스트는 물리적인 순서와 상관이 없다. 임의의 위치에 대한 요소의 삽입 및 삭제 속도가 동일하다.

 

연결리스트에서 원소는 데이터(값)와 링크(메모리 주소값)를 동시에 가지며 링크는 후행 원소의 주소값이다. 이러한 단위 구조를 노드(node)라고 한다. 각 요소는 데이터 외에 이전/다음 노드의 링크를 추가로 가지고 있어야 한다.

다음 노드의 정보만을 가진 리스트를 단일 연결 리스트(Single Linked List), 이전과 다음 노드의 정보를 둘 다 가지고 있는 리스트를 이중 연결 리스트(Double Linked Llist)라고 한다.

 

struct Node{
	T value;
	Node* next;
}

 

#include <iostream>

using namespace std;

struct Node {
	int value;
	Node* next;
};

Node* head;
Node* now;

void InitLinkedList() {
	head = (Node*)malloc(sizeof(Node));
	
	head->value = NULL;
	head->next = NULL;
	now = head;
}

Node* InsertNode(Node* now, int value) {

	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->value = value;
	
	newNode->next = now->next;
	now->next = newNode;

	return newNode;
}

bool DeleteNode(int index) {
	
	Node* prev = head;
	Node* del;

	for (int i = 0; i < index; i++) {
		prev = prev->next;

		if (prev == NULL) {
			return false;
		}
	}

	del = prev->next;
	if (del == NULL) {
		return false;
	}

	prev->next = del->next;
	free(del);

	return true;

}

bool DeleteNode(Node* targetPrev) {

	Node* del; 

	del = targetPrev->next;

	if (del->next == NULL) {
		return false;
	}

	targetPrev->next = del->next;
	free(del);

	return true;

}

void DeleteList() {
	free(head);
	head = NULL;
}

int main() {

	InitLinkedList();

	for (int i = 0; i < 10; i++) {
		InsertNode(now, i + 1);
		now = now->next;
	}

	for (now = head->next; now; now = now->next) {
		cout << now->value << endl;
	}

	cout << endl;

	//bool result = DeleteNode(head);
	bool result = DeleteNode(9);

	cout << endl;

	cout << "result : " << result << endl;
	
	for (now = head->next; now; now = now->next) {
		cout << now->value << endl;
	}

	DeleteList();

}

 

 

 

📌Set

 

정렬 연관 컨테이너. 순서가 없고 중복을 허용하지 않는 자료구조. 값을 오름차순으로 정렬한다.

 

#include <iostream>
#include <set>

using namespace std;

int main() {

	int arr[] =  {1, 2, 3, 2, 5, 6, 3};
	
	
	set<int> scon;

	set<int>::iterator it;

	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++) {
		scon.insert(arr[i]);
	}

	for (it = scon.begin(); it != scon.end(); it++) {
		cout << *it << endl;
	}
	
	return 0;

}

 

 

 

📌Map

 

키:값 형태로 하나의 쌍을 이루어 관리된다. 값을 오름차순으로 정렬한다. 검색 속도가 빠르다.

대용량 데이터를 검색할 경우 유리하다.

삽입 및 삭제 시 데이터의 이동이 발생하므로 상대적으로 느리다.

 

`map<keyType, dataType> m; map<string, int> ageList;`

`first` 는 키, `second` 는 값.

 

	map<string, int> phoneBook;
	map<string, int>::iterator it;

	string name;

	for (int i = 0; i < sizeof(phoneList) / sizeof(phoneList[0]); i++) {
		phoneBook[phoneList[i].name] = phoneList[i].phone;
	}

	while (true) {
		cout << "종료: [q]";
		cout << "이름을 입력하세요: ";
		cin >> name;

		if (name == "q") {
			break;
		}

		// phoneBook[name]은 value만을 불러오지만,
		// 반복자로 it = phoneBook.find(name);를 사용하면
		// 요소의 주소값을 가져오기 때문에 키와 값을 모두 사용할 수 있다!
		if (phoneBook[name]) {
			cout << "번호는 " << phoneBook[name] << "입니다." << endl;
		}
		else {
			cout << "찾을 수 없습니다.  [" << name << "]" << endl;
		}

	}

 

 

📌해시맵(hashMap)

 

STL에서는 해시맵을 지원한다. hash 자료구조를 사용하기 때문에 검색 속도가 빠르다.

* `hash_map` 이 deprecated 되었습니다. `unordered_map` 을 사용할 수 있습니다.

 

unordered_map<string, int> coffee;
coffee["아메리카노"] = 2000;

unordered_map<string, int>::iterator it;

for (it = coffee.begin(); it != coffee.end(); it++) {
	cout << "[" << it->first << "] " << it->second << "원" << endl;
}

 

	unordered_map<string, vector<string>> devLang;

	vector<string> c;
	c.push_back("C");
	c.push_back("C++");
	c.push_back("C#");

	vector<string> script;

	devLang["C 계열"] = c;

	vector<string> scr;
	scr.push_back("JavaScript");
	scr.push_back("TypeScript");

	devLang["Script 계열"] = scr;

	unordered_map<string, vector<string>>::iterator mapIt;
	vector<string>::iterator it;

	for (mapIt = devLang.begin(); mapIt != devLang.end(); mapIt++) {
		cout << "[" << mapIt->first << "]" << endl;
		for (it = mapIt->second.begin(); it != mapIt->second.end(); it++) {
			cout << *it << " " << endl;
		}

		cout << endl;
	}

[Script 계열]
JavaScript
TypeScript

[C 계열]
C
C++
C#

 

 

📌반복자(Iterator)

 

컨테이너의 구간에 대해 값을 읽어올 수 있도록 기능을 제공한다. 모든 컨테이너에 동일하게 동작한다.(내부 구조를 모르더라도 같은 함수로 값을 읽을 수 있다.)

`list::iterator listIter; vector::iterator vectorIter;`

 

 

포인터와 유사함. `listIter++` 처럼 반복자를 증가시키는 것은 그 다음 요소를 읽어오는 것을 뜻한다.

자료구조의 `begin()` 은 시작 요소를 의미한다. `end()` 는 마지막값이 아니라 마지막값의 다음을 의미한다.

 

 

문자열은 다음과 같이 문자 포인터로 각 문자를 읽을 수 있다.

char arr[] = "Hello!";

char* ptr = arr;

while (*ptr) // ptr != NULL
{
    cout << *ptr;
    ptr++;
}

 

 

컨테이너도 이처럼 반복자를 사용하면 내부 구조를 모르더라도 동일한 함수를 사용하여 컨테이너 내 포함된 요소를 순차적으로 가리킬 수 있다.

컨테이너의 타입에 따라 반복자를 선언하고 사용할 수 있다.

 

int intArr[] = { 1, 2, 3, 4, 5 };

vector<int> vec(&intArr[0], &intArr[sizeof(intArr) / sizeof(intArr[0])]);
vector<int>::iterator it;

for (it = vec.begin(); it != vec.end(); it++) {
    cout << *it << " ";
}

list<int> li;
list<int>::iterator it;

for (int i = 0; i < 5; i++) {
    li.push_back(i + 1);
}

for (it = li.begin(); it != li.end(); it++) {
    cout << *it << " ";
}

 

 

📌알고리즘(Algorithm)

 

컨테이너에 적용할 수 있는 기능들을 체계적으로 정리해둔 함수. 정렬, 검색, 조작 등의 연산을 수행한다. 특정 컨테이너에 종속된 것이 아니라 일반적으로 적용할 수 있음.

 

ex) `find()` `first`와 `last` 사이에 `value`가 있는지 검사하고 찾는 값이 있다면 해당 위치의 반복자를 리턴한다.

ex) `for_each()` 전 구간을 순회하면서 인자로 받은 함수를 호출한다. `for_each`는 루프를 돌리는 역할만 하므로 구체적인 동작을 하는 함수 객체가 반드시 필요하다. 내부에서 반복자를 사용한다.

ex) `copy()` 컨테이너의 범위값을 대상이 되는 컨테이너에 복사하는 함수.

ex) `sort()` 기본은 오름차순 정렬. 내림차순으로 정렬하려면 `greator<int>()` 를 전달해야함.

 

	int intArr[] = { 1, 2, 3, 4, 5 };

	vector<int> vec(&intArr[0], &intArr[sizeof(intArr) / sizeof(intArr[0])]);
	vector<int>::iterator it;

	if (find(vec.begin(), vec.end(), 5) != vec.end()) {
		cout << "Found Five!";
	}
	else {
		cout << "Not Found";
	}