카테고리 없음

C++언어 강좌(공부) #★20장★

바래다주기 2024. 5. 8. 00:17

20. STL

STL(Standard Template Library)
클래스 템플릿의 집합인 표준 라이브러리
C++에서 제공하는 라이브러리의 일종으로, 프로그래밍에 필요한 자료구조 및 알고리즘을 클래스 템플릿화 하여 제공
템플릿 기반 -> 모든 자료형과 호환 -> 제너릭 프로그래밍

STL구성요소

컨테이너
알고리즘
함수 객체
반복자

컨테이너 - STL 구성요소(1)
데이터를 저장하는 객체, 자료구조를 구현한 객체
구분 기준

원소 배치 방법
a. 표준 시퀀스 컨테이너
b. 표준 연관 컨테이너
메모리 저장 방법
a. 배열 기반 컨테이너
b. 노드 기반 컨테이너
컨테이너 어댑터
근사 컨테이너

원소 배치 방법으로 구분하는 컨테이너

표준 시퀀스 컨테이너 : 원소마다 방향성이 존재함 ex) 연결 리스트는 단방향, 양뱡향 리스트가 존재함
종류로는 Vector, Deque, List 가 존재 -> 삽입, 삭제가 빈번한 자료의 경우 유용
표준 연관 컨테이너 : 시퀀스 컨텡너와 달리 방향성이 애매모호함 Tree 구조를 예시로 들 수 있음
대표적인 구조로 자가 균형 이진 탐색 트리(레드-블랙 트리) 존재 종류로는 Set, Map, Multi-Set, Multi-Map 존재 -> 정렬, 탐색이 빈번한 자료의 경우 유용

메모리 저장 방법으로 구분하는 컨테이너

배열 기반 컨테이너 -> Vetor, Deque
노드 기반 컨테이너 -> List, Map

컨테이너 어댑터 : 기본 컨테이너의 기능 중 일부 기능만 사용이 가능하며, 기능 제한이나 기능이 변형되어 있는 컨테이너 의 집합
ex) Queue(First In, First Out), Stack(First In, Last Out)

근사 컨테이너 : 템플릿의 형태를 띄고 있지만, 특정 자료형에 종속되는 컨테이너
ex) String, wString

알고리즘 - STL 구성요소(2) : 컨테이너 내에서 정렬, 삭제, 탐색 등을 해결하는 일반화된 방법을 제공하는 함수 템플릿
#include <algorithm> 사용

*시간 복잡도
Big-O 표기법을 사용하여 표기 -> 시간 복잡도를 O(n)형식으로 나타냄
수식의 가장 큰 항과 차수만을 표현한다

종류 1. 상수 시간 => 가장 이상적인 복잡도, 처리량에 상관 없이 속도 동일, 처리량 적으면 비효율적
2. 로그 시간
3. 선형 시간
4. 지수 시간 -> 가장 피해야 할 방식으로, 반복문의 중첩 등을 예시로 들 수 있음

함수 객체 - STL 구성요소(3)
함수 호출 연산자인()를 연산자 오버로딩하여 소유하는 클래스
일반적으로 STL알고리즘 함수 템플릿에 조건자라는 형태의 매개변수로 함수 객체를 전달하긱 위해 제작

반복자(iterator) - STL 구성요소(4)
컨테이너 내부의 원소를 순회, 접근하여 읽기와 쓰기를 수행하기 위해 제공되는 객체
포인터와 비슷한 원리로 동작하거나, 포인터가 아닌 객체 타입이다

Tip 컨테이너에 사입과 동시에 동적할당이 가능하다
ex)
list<CObj*> CObjList;
CObjList.push_bcak(new CObj);

Vector 컨테이너

#include
using namespace std;

vector vecInt;

**특징**

1. 동적 배열 기반 컨테이너

2. 배열 기반이므로 임의 접근(인덱스 접근)이 가능하여 탐색에 매우 유리

3. 원소 삽입 시 맨 뒤에 차곡차곡 쌓이는 형식으로 삽입

4. 중간 삽입이 가능하긴 하지만, 삽입된 원소 이후의 원소들에 대해 한 칸씩 뒤로 이동하는 작업 필요

5. 동적 배열 기반이므로, 인덱스 값을 초과한 수의 원소가 삽입될 경우 메모리 재할당 발생
→ n + n/2 (Visual Studio 기준) 공식만큼 재 할당

6. 특정 원소를 제거하더라도 할당받은 메모리 공간은 제거되지 않음
→ 재사용성 증가 및 메모리 재할당 횟수를 감소시켜 연산 효율 증대

→ 탐색에 유리하지만, 삽입/삭제시 비교적 비효율적인 모습을 보여주는 컨테이너

멤버 함수
vector vec = { 10, 20 };
vector vec2 = { 100, 200 };

vec[0]; // 벡터의 0번 원소에 임의 접근
vec.at(1); // 벡터의 1번 원소에 임의 접근 -> 인덱스 연산자와 달리 인덱스 초과 범위 입력시 out_of_range 반환
vec.push_back(30); // 벡터의 맨 뒤에 원소 삽입, 인덱스 초과할 경우 메모리 재 할당
vec.pop_back(); // 벡터의 맨 뒤 원소 제거
vec.size(); // 벡터의 사이즈, 즉 들어있는 원소의 수 반환
vec.capacity(); // 벡터가 할당받은 메모리의 크기 반환
vec.empty(); // 벡터가 비어있는지 여부를 bool형으로 반환
vec.swap(vec2); // 매개변수로 받은 벡터와 메모리를 맞교환하는 함수
vec.shrink_to_fit(); // 사용하지 않는 메모리 공간의 할당을 해제하는 함수
vec.front(); // 벡터의 첫 번째 원소 반환
vec.back(); // 백터의 마지막 원소 반환
vec.begin(); // 벡터의 시작 주소를 가리키는 iterator 반환
vec.end(); // 벡터의 마지막 원소 다음 위치를 가리키는 iterator 반환
vec.erase(vec.begin()); // 해당 위치에 존재하는 원소를 제거한 후 다음 위치의 iterator 반환하며, 메모리는 잔존
vec2.erase(vec2.begin(), vec2.end()); // 1번째 인자 ~ 2번째 인자 사이에 존재하는 원소 제거
vec.insert(vec.begin(), 1); // 1번째 인자의 위치에 2번째 인자 원소 삽입
vec.resize(5); // 벡터의 size와 capacity를 5로 조정
vec.reserve(10); // 벡터의 size는 건드리지 않은 채로 capacity만 10 증가

vector 컨테이너 지우는 법
vector vecInt;
vector().swap(vecInt);

아래 코드는 임시 메모리에 등록되어 해당 라인을 탈출하면 사라진다.
그렇게 사라지는 벡터와 현재 벡터를 swap하고 나면 현재의 벡터는 사라진다.

동적 할당된 원소 삭제 시 주의점
class CObj
{
// 클래스 내용
};

void main()
{
vector<CObj*> vecObj;
vecObj.push_back(new CObj);
vecObj.push_back(new CObj);
vecObj.push_back(new CObj);

vector<CObj*>::iterator iter = vecObj.begin();
delete (*iter);
(*iter) = nullptr;
iter = vecObj.erase(iter);
}

Heap 영역에 등록되어있는 원소의 경우 해당 원소에 접근하여 할당 해제를 해줌
→ 할당 해제는 되었지만, 아직 벡터의 원소에 해당 원소의 주소가 남아있음 (댕글링 포인터)
해당 영역의 값을 erase를 사용하여 지운 뒤, 반복자를 통한 추가 작업이 필요하면
반환 값을 받아 작업을 진행

클래스 내의 벡터에 대해 소멸시키려는 경우
// 함수 포인터 방식

template
void Safe_Delete(T& temp)
{
if (temp)
{
delete temp;
temp = nullptr;
}
}

// 함수 객체 방식
class SAFE_DELETE
{
public:
template
void operator()(T& temp)
{
if (temp)
{
delete temp;
temp = nullptr;
}
}
};

class CObj
{
// 코드
};

class CPlayer
{
public:
void Func()
{
vecObj.push_back(new CObj);
}

void Release()
{
// 방법 1. at()을 이용한 Release
for (size_t i = 0; i < vecObj.size(); ++i)
{
Safe_Delete<CObj*>(vecObj.at(i));
}
vecObj.clear();
vector<CObj*>().swap(vecObj);

// 방법 2. iterator을 이용한 Release
for (vector<CObj*>::iterator iter = vecObj.begin(); iter != vecObj.end(); ++iter)
{
Safe_Delete<CObj*>(*iter);
}

vecObj.clear();
vector<CObj*>().swap(vecObj);

// 방법 3. for_each, 함수 포인터를 이용한 Release
for_each(vecObj.begin(), vecObj.end(), Safe_Delete<CObj*>);
vecObj.clear();
vector<CObj*>().swap(vecObj);

// 방법 4. for_each, 함수 객체를 이용한 Release
for_each(vecObj.begin(), vecObj.end(), SAFE_DELETE());
vecObj.clear();
vector<CObj*>().swap(vecObj);

}

private:
vector<CObj*> vecObj;
};

기본 매커니즘

모든 컨테이너를 순회하며 각 원소들을 동적 할당 해제한다
할당 해제한 후 벡터 내 원소 모두 비움
swap 이용하여 벡터 삭제

List컨테이너
#include <list>
using namespace std;

list <int> List;

**특징**

노드 기반 컨테이너

앞, 뒤 어디든 원소 삽입이 가능

연손적인 공간이 아닌, 흩어진 메모리 공간에 각 앞, 뒤 노드의 포인터 주소를 가진 형태

0번 인덱스가 따로 존재하지 않기에 임의 접근이 불가

탐색시 특정점을 기준으로 순회 (맨 앞 노드부터 몇번째 위치)

삽입 및 삭제 시 노드의 포인터만 변경될 뿐 원소의 이동은 일어나지 않음

→ vector과 달리 삽입, 삭제가 용이하며 탐색이 비효율적이다.

**vector와의 차별점**

노드 기반 컨테이너 이므로 push_front(), pop_front() 함수 존재
퀵 정렬, 배열 기반 알고리즘은 sort()는 노드 기반인 리스트에서 사용이 불가능
대신 리스트는 멤버 함수로 sort를 가진다.
현재 노드들의 방향을 뒤바꿔주는 reverse() 함수 존재

**원소 탐색 방법**

임의 접근이 불가능하므로 iterator를 통해 접근해야 한다.

멤버 함수
list intList = { 10, 20 };
list intList2 = { 100, 200 };

intList.push_back(30); // 리스트의 맨 뒤에 원소 삽입
intList.pop_back(); // 리스트의 맨 뒤 원소 제거
intList.size(); // 리스트의 사이즈, 즉 들어있는 원소의 수 반환
intList.empty(); // 리스트가 비어있는지 여부를 bool형으로 반환
intList.swap(intList2); // 매개변수로 받은 리스트와 메모리를 맞교환하는 함수
intList.front(); // 리스트의 첫 번째 원소 반환
intList.back(); // 리스트의 마지막 원소 반환
intList.begin(); // 리스트의 시작 주소를 가리키는 iterator 반환
intList.end(); // 리스트의 마지막 원소 다음 위치를 가리키는 iterator 반환
intList.erase(intList.begin()); // 해당 위치에 존재하는 원소를 제거한 후 다음 위치의 iterator 반환하며, 메모리는 잔존
intList2.erase(intList2.begin(), intList2.end()); // 1번째 인자 ~ 2번째 인자 사이에 존재하는 원소 제거
intList.insert(intList.begin(), 1); // 1번째 인자의 위치에 2번째 인자 원소 삽입
intList.resize(5); // 리스트의 size를 5로 조정

intList.push_front(40); // 리스트의 맨 앞에 원소 삽입
intList.pop_front(); // 리스트의 맨 앞 원소 제거
intList.sort(); // 자체적인 정렬 알고리즘을 가짐
intList.reverse(); // 현재 리스트의 노드가 가리키는 방향을 거꾸로 뒤집어줌

Deque 컨테이너

Deque 컨테이너 : 전체적으로 vector 컨테이너와 비슷한 구조를 띄지만, 메모리의 구조가 다르다
deque는 메모리 블럭 단위로 관리한다 따라서 vector와 달리 push_front(0가 가능한데...
1. 현재 맨 앞 원소의 앞에 지정된 크기만큼의 메모리 블럭 생성하여 앞자리 생성
2. 기존 맨 앞 원소의 앞에 원소를 삽입

이런 방식으로 동작한다 만들어진 블럭에 데이터가 가득 차게 되는 경우에만 메모리 재할당이 일어난다

문제점 : vector의 insert()의 경우, 해당 지점 이후의 원소들만 이동하는 작업을 실시
deque의 insert()의 경우, 해당 앞/뒤 쪽이 모두 열려있는 형태이기에 전체적으로 상황을 파악한 뒤 작업을 진행하 는 방식을 택함
따라서 중간 삽입 시 vector보다 비효율적인 모습을 보여주며, 잘 사용되지 않는다.

Map 컨테이너

Map 컨테이너 : 표준 연관 컨테이너 Node기반 표준 시권스 컨테이너가 가로 형식이라면 표준 연관 컨테이너는 세로 형식 => 변형 리스트 방식
양뱡향 반복자 (++/--) 자가 균형 이진 탐색 트리(레드-블랙 트리)구조 -> 좌측에 작은 값, 우측에 큰 값 기준 으로 정렬

Map 컨테이너의 특징

Map의 노드는 Key와 Value로 구성되어 있으며, 두 가지 값을 가지므로 다항 템플릿 형태
Map은 Key값의 중복을 허가하지 않으며, Key값을 기준으로 정렬한다
인덱스 연산자가 오버로딩 되어 있어 Key값을 통한 임의 접근이 가능하다
Map에 한번 입력된 Key는 cosnt화 되어 변경할 수 없다. Value 값은 변경이 가능하다
insert()를 통한 중간 삽입을 진행하더라도 Map 컨테이너는 원소를 입력 받을 때마다 재정렬을 진행하므로 중간 삽입의 의미가 없다.
반복자를 사용하여 출력할 경우 자동으로 오름차순으로 정렬? → 정렬 방식 변경 가능
Map 컨테이너는 다항 템플릿의 형태로 최대 4개의 인자를 가질 수 있음
map<key, value, 조건자> 형식으로 선언하게 되면 조건자의 기준으로 정렬이 가능하다.
Map 컨테이너는 탐색이 용이한 특성에 따라 게임의 리소스 관리 등에서 많이 사용된다.
이 때, 사용할 리소스를 미리 전부 넣어두고 사용해야 하는데
매번 추가적인 자료를 삽입할 경우 매 순간 재정렬이 발생하여 연산속도 이슈가 발생한다.
이런 경우 차라리 clear를 통해 컨테이너를 비운 후 다시 자료를 집어넣는 것이 낫다.

다른 표준 연관 컨테이너들과의 차이점

Map VS Set
Map : Key와 Value가 한 쌍으로 구성됨
Set : Value가 곧 Key이다.
Map VS Multi-Map
Map : Key의 중복을 허용하지 않으며, Key를 통한 임의 접근이 가능하다.
Multi-Map : Key의 중복이 허가되지만, 임의 접근이 불가능하다.

이진 트리 구조 순회 방법

전위 순회 : Root Node를 기준으로 Root Node에 방문, 이후 좌측부터 탐색
(0 > 1 > 3 > 7 > 8 > 4 > 9 > 10 > 2 > 5 > 11 > 6)
중위 순회 : 가장 좌측 Node를 기준으로 가장 좌측 Node에 방문, 좌측에 가까운 순서로 탐색
(7 > 3 > 8 > 1 > 9 > 4 > 10 > 0 > 11 > 5 > 2 > 6)
후위 순회 : 하위 트리를 모두 방문한 뒤 그 상위 트리로 이동하며 탐색
(7 > 8 > 3 > 9 > 10 > 4 > 1 > 11 > 5 > 6 > 2 > 0)
층별 순회 : 상위 트리부터 계층 별로 탐색
(0 > 1 > 2 > 3 > 4 > 5 > 6 > 7 > 8 > 9 > 10 > 11)

>> Map의 형태인 자가 균형 이진 탐색 트리(레드 - 블랙 트리)는 중위 순회 방식을 사용

선언 map<int, int> mapInt;

원소 삽입
// (1)
pair<int, int> myPair;
myPair.first = 2; // Key
myPair.second = 200; // Value
mapInt.insert(myPair);

// (2)
pair<int, int> myPair2(1, 100);
mapInt.insert(myPair2);

tree 구조에서는 앞과 뒤의 구분이 모호하므로, insert() 형식의 삽입을 사용
또한 Key와 Value 두 개의 변수를 대입하기 위해 구조 체형 pair 사용

Map 컨테이너 노드 접근 방법

map<int, int>::iterator iter = mapInt.begin();
for (iter; iter != mapInt.end(); ++iter)
{
cout << iter->first << "\t << iter->second << endl;
}

Map 컨테이너에 원소를 삽입하는 8가지 방법

insert() 와 pair 객체를 사용하여 대입
ex)
map<int, int> mapSolution1;
pair<int, int> pairSolution1(1, 100);
mapSolution1.insert(pairSolution1);
pair 객체를 임시 객체로 사용하여 대입
ex)
map<int, int> mapSolution2;
mapSolution2.insert(pair<int, int>(1, 100));
make_pair를 사용하여 대입
ex)
map<int, int> mapSolution3;
mapSolution3.insert(make_pair(1, 100));
mapSolution3.insert(make_pair<int, int>(2, 200));

make_pair : pair형을 반환하는 함수 템플릿
2번줄 처럼 사용할 수 있지만 대입 되는 형에 따라 3번 줄 처럼 표기해야 하기도 함
내부적으로 pair 객체를 만드므로 결국 2번보다 비효율적인 연산

value_type을 사용하여 대입
ex)
map<int, int> mapSolution4;
map<int, int>::value_type Solution4(1, 100);
mapSolution4.insert(Solution4);

value_type : Map 내에 namespace로 typedef되어 제공되는 pair객체 내부적으로 pair객체를 생성함에는 다름이 없지만
pair<const, type> 형태로 Key값을 const 값으로 넘겨줌

value_type을 임시 객체로 사용하여 대입
ex)
map<int, int> mapSolution5;
mapSolution5.insert(map<int, int>::value_type(1, 100));
인덱스 연산자를 사용하여 대입
ex)
map<int, int> mapSolution6;
mapSolution6[1] = 100;

기존에 생성된 노드의 Value 값을 변경하는 것을 원할 경우 인덱스 연산자를 사용하여 변경 가능
인덱스 연산자를 이용할 때 해당 노드가 존재하지 않았다면 value가 0으로 초기화된 노드 삽입
-> insert() 함수는 새로운 노드를 생성하여 추가하는 방식
Key값의 변경을 허가하지 않는 Map의 특성 상 변경을 목적으로, 중복된 Key를 가지고 삽입되는 노드에 대해서 허가하지 않음
emplace()를 이용한 대입 (C++11 이후의 문법)
ex)
map<int, int> mapSolution7;
mapSolution7.emplace(1, 100);
내부에서 스스로 자료형에 대한 파악을 하여 대입
유니폼 초기화
ex)
map<int, int> mapSolution8;
mapSolution8.insert({ 1,100 });

find() 멤버 함수
ex)
map<int, int> mapFind;
mapFind.emplace(1, 100);
mapFind.emplace(2, 200);
mapFind.emplace(3, 300);

map<int, int>::iterator iterFind = mapFind.find(1);
cout << iterFind->first << "\t" << iterFind->second << endl;

매개 변수로 넣어준 Key값에 해당하는 노드로 이동하는 함수

find()멤버 함수의 문제점 : 문자열을 이름으로 가지는 파일에 대해 Map 컨테이너를 통한 정리를 하려는 경우...

map<const char*, int> -> char* 활용한 문자열 상수 방식
map<wchar_t*, int> -> w_char* 활용한 유니코드 문자열 상수 방식
map<string, int> -> string 컨테이너 활용한 방식

세가지 경우를 사용할 수 있는데 char*는 문자열 상수 방식이다
상수는 해당 상수에 대한 주소값을 상수 메모리에 저장한 뒤 프로그램 종료까지 해당 주소를
이용하여 해당 상수에 접근하는 방식으로 동작한다
프로젝트가 1개 뿐인 프로그램이라면 상관이 없겠지만, 여러 개의 프로젝트가 존재하는 프로그램
의 경우 각 프로젝트는 별개이 프로그램으로 취급되며, 각자 다른 메모리를 가진다

A프로젝트의 상수 메모리에 등록된 aaa 문자열의 주소가 0x32 라고 가정하면
B프로젝트의 상수 메모리에 등록된 aaa 문자열의 주소가 0x32 라고 확신할 수는 없다.
따라서 제대로 해당 문자열에 대한 값을 불러오지 못하는 경우가 발생한다.

해결법 : 1. 2번 또는 3번의 방식을 사용할 경우 해당 문제가 발생하지 않음

2. char* 형을 꼭 사용해야 하는 경우 find_if() 알고리즘을 사용한다

find_if()
map<const char*, int> mapResource;

mapResource.emplace("AAA", 100);
mapResource.emplace("BBB", 200);
mapResource.emplace("CCC", 300);

map<const char*, int>::iterator iterFindif = find_if(mapResource.begin(), mapResource.end(), Finder("CCC"));
if (iterFindif == mapResource.end())
{
// find_if() 알고리즘은 동작이 완료된 후 찾는 값을 발견하지 못했을 경우 end()를 반환
cout << "fail" << endl;
}
else
{
cout << iterFindif->first << "\t" << iterFindif->second << endl;

}

Map 컨테이너 사용 시 정렬 기준

Key 값으로 char형 사용 : 문자의 아스키 코드 순으로정렬
Key 값으로 char*형 사용 : 문자열 시작 주소를 기반으로 대소 비교하여 정렬
Key 값으로 string 컨테이너 사용 : 컨테이너 내에서 대소 비교가 오버로딩 되어 있으므로, 알파벳 순서로 정렬됨

반복자

vector vecInt = {10, 20, 30};
vector::iterator iter = vecInt.begin();

각 컨테이너의 원소를 순회하며 해당 원소에 접근하거나 가공하기 위한 문법
포인터와 상당히 유사하게 동작하지만, 반복자는 객체이다
컨테이너마다 각자의 반복자 템플릿을 소유하고 있다

반복자를 이용한 컨테이너 순회 방법
for(iter = vecInt.begin(); iter != vecInt.end(); ++iter)

주의할 점!
for문의 동작방식은(조건식 -> 내부 식 -> 증감식) 순서
특정 조건에 만족하여 내부 식 동작 후 증감식이 동작하면 반복자는 그 다음 원소를 가리키게 됨
-> 원소를 던너뛰는 현상이 발생

for(iter = vecInt.begin(); iter != vecInt.end();)
{
if(true == 조건)
{
// 내부 식
break;
}
else { ++iter; }
}

해당 식처럼 조건을 충족하는 경우 break로 탈출, 부합하는 경우 else에서 증감식을 동작시키므로써 반복자를 건너뛰는 문제를 해결할 수 있다

알고리즘

#include 으로 알고리즘 헤더 포함
#include 으로 조건자 헤더 포함

알고리즘(begin, end, 조건자) 형식으로 사용 -> 조건자는 직접 만들어서도 사용 가능
(조건자 -> 함수 포인터, 함수 객체, 람다식)

자주 사용하는 알고리즘

sort() : 퀵 정렬 방식, 배열 기반, 함스 템플릿 형식으로 만들어진 알고리즘
2번째 인자까지만 입력 시 default정렬방식인 오름차순으로 정렬된다 배열 기반이므로 노드 기반의 컨테이너 에 서는 사용이 불가능
count_if() : STL컨테이너를 순회하며 해당 컨테이너 내에서 조건자의 결과가 true일 경우 카운트를 1증가시키며, 순회가 끝나면 해당 카운트를 반환하는 알고리즘
for_each() : 반복자 사이의 거리만큼 컨테이너를 순회하며 조건자를 실행시키는 알고리즘