[C++학습] 7. STL

1. STL (Standard Template Library)

C++ 표준 라이브러리의 일부로, 컨테이너, 알고리즘, 반복자 등의 템플릿 기반 구성 요소를 포함한다. STL을 사용하면 다양한 자료구조와 알고리즘을 직접 구현하지 않고도 사용할 수 있다. 

---

 [1. 자주 사용되는 컨테이너]

컨테이너란 데이터를 담는 자료구조를 말한다.

모든 컨테이너는 템플릿으로 구현되어 있어 다양한 타입의 데이터를 저장할 수 있고, 메모리 관리를 내부적으로 하고 있어 사용 시 메모리 해제를 직접 고려하지 않아도 된다.

대부분 컨테이너는 반복자를 제공하기 때문에 내부 구현을 몰라도 동일한 방식으로 컨테이너를 순회할 수 있다.

---

1) 벡터(vector)

벡터는 배열과 매우 유사한 컨테이너이다. 특징은 다음과 같다.

 -1. 템플릿 클래스로 구현되어 특정 타입에 종속되지 않는다.

 -2. 삽입되는 원소 개수에 따라 내부 배열의 크기가 자동으로 조정된다.

 -3. 인덱스를 통해 임의 접근이 가능하다.

 

먼저 벡터를 선언해야 한다. 타입만 명시해서 선언하거나, 초기값까지 같이 선언해야 한다.

(초기값 선언하는 경우) : vector<int> vec(5,10); --> 크기는 5. 모든 원소가 10으로 초기화.

 

2차원 배열처럼 벡터를 사용하려면, 벡터의 타입을 벡터로 하면 된다.

예를 들어, vector<int> vec( 3, vector<int> ( 4, 7 )); (선언만 한 경우) --> 가로줄이 3개이고, 세로줄이 4개. 모든 원소는 7 초기화.

결론적으로 3 x 4 2차원 배열을 만든다. 가로줄은 행(row), 세로줄은(colomn). row번호를 먼저 만들고 그 오른쪽으로 채워나간다.

그 다음으로는 벡터에서 제공하는 메서드 중 자주 사용하게 될 메서드를 알아보려고 한다.

 

 -1. push_back : 벡터의 맨 끝에 원소를 추가하는 메서드. 원소의 개수가 늘어남에 따라 크기는 자동으로 증가한다.

ex1) vec.push_back(10) : 맨 끝에 10이라는 원소를 추가한다.

 

ex2) 2차원 벡터에 데이터를 추가하고 싶을 때는?

 ex2-1) 2차원 벡터에 새로운 1차원 벡터(행)을 통째로 집어넣고 싶다면 : vector<T> 타입의 객체를 push_back

vector<int> vec2 = {1, 2, 3};

vec2.push_back(vec1);

 

 ex2-2) 이미 존재하는 특정 행에 개별 데이터를 넣고 싶다면 : 인덱스를 이용해서 해당 행을 찾고 그 행에서 push_back

vec[1].push_back(10); vec 벡터의 인덱스 1 (두번째 행)의 마지막에 숫자 10을 추가.

---

 -2. pop_back : 벡터의 맨 끝 원소를 제거하는 메서드. 원소가 제거되면 벡터 크기가 자동으로 줄어든다. push_back 과 반대 개념으로 사용하면 된다.

 

단, 2차원 벡터에서 만약 2번째 (vec[1])에서 맨 마지막 원소만 pop_back한다고 하면 2번째 행의 크기만 감소하고 나머지 행의 크기는 그대로이다. 이때, vec.size()를 해보면 행의 개수는 유지하고 있음을 알 수 있다.

주의할 점으로는 빈 행에서 pop_back을 하는 경우다. size가 0인 경우 pop_back을 하면 에러가 난다. 그래서 일반적으로는 다음과 같이 확인부터 하고 진행하는 것이 좋다.

 if (!vec[1].empty()) { vec[1].pop_back(); }

---

 -3. size : 현재 벡터의 크기(원소 개수)를 확인할 때 사용하는 메서드. 보통 벡터의 전체 원소를 대상으로 반복문을 돌릴 때 유용하게 사용한다.

vec.size() 로 사용하면 된다.

---

 -4. erase : 특정 위치(또는 구간)의 원소를 제거하는 함수이다. 자주 사용하지 않는 것이 좋다(시간 복잡도가 커짐).

주로 vec.begin()과 함께 많이 사용된다. vec.begin()은 벡터의 첫 번째 원소를 가리키는 반복자를 반환한다.

반대로 vec.end()는 벡터의 마지막 원소 다음을 가리키는 반복자를 반환한다.

 

 ex1) 예를 들어 벡터의 두 번째 요소를 제거하고 싶다면,

// vec.erase(vec.begin() + 1); --> index 1 제거

이런 식으로 사용한다.

 

 ex2) 벡터의 두 번째 부터 네 번째 요소(구간)를 제거하고 싶다면,

// vec.erase(vec.begin() + 1, vec.begin() + 3); --> index 1~3 제거

이런 식으로 사용한다.

---

2) 맵

특정 키를 사용하여 값을 검색하는 기능을 제공하는 컨테이너이다.

맵은 키를 활용해서 키와 값을 쌍으로 저장하고 검색한다.

키-값 쌍은 pair<const Key, Value> 형태로 저장되고, 키값을 기준으로 내부 데이터가 자동으로 정렬된다.

중복된 키 값은 허용되지 않는다.

 

맵을 선언하기 위해서는 우선 #include <map>하고, 키-값 쌍을 저장하기 위해 키 타입과 값 타입 두 가지를 지정해야 한다. 키 타입은 비교 연산이 가능해야 한다. 

 

 <사용법>

첫번째, map을 선언한다.

// map<string, string> contryMap; (map의 키값쌍, map별명)

두번째, 요소를 추가한다.

//countryMap["KR"] = "Korea"; (키값은 KR(string이니까 ""), 값은 Korea("")

세번째, 요소를 출력해본다.

//for (const auto& pair : countryMap) { cout << pair.first << ", " << pair.second << endl; }

//출력 결과 : KR, Korea

 

맵에서 사용하는 대표적인 함수를 알아보자.

 

 -1. map은 key 순으로 오름차순 정렬(자동)된다. 그래서 key값이 비교 연산이 가능해야 한다는 것이다.

 

그러면 내림차순 정렬하게 만들고 싶으면?

 -1.1) map 선언할 때 세번째 인자에 greater<int>를 추가한다. 선언 시점부터 내림차순으로 관리된다.

 //map<int, string, greater<int>> myMap; (선언시 key값 자료형 int 기준으로 내림차순)

 

 -1.2) map은 그대로 오름차순으로 두고 출력할 때만 거꾸로 훑어가면서 출력하기. 역방향 반복자를 사용한다.

//for (auto it = myMap.rbegin(); it != myMap.rend(); ++ it) {...};

//(auto랑 같이 관습적으로 반복자(it라고 이름을 붙이고) 사용. 역방향이면 rbegin, rend() 를 사용한다

---

 -2. insert()

make_pair()를 이용해서 pair 객체를 생성한 후 insert 함수를 사용할 수 있다. {} 또는 []를 사용해서 값을 추가할 수도 있다.

 

 -2.1 make_pair() + insert() 사용해서 추가하기

//map<int, string> myMap;

//myMap.insert(make_pair(1, "Apple"));

 

 -2.2 {} or [] + insert() 사용해서 추가하기. 

//myMap.insert({2, "Banana"});

//myMap[3] = "Grape";

---

-3. find()

find 메서드를 사용하면 특정 키가 map에 존재하는 지 확인할 수 있다.

find는 키가 존재하면 해당 키의 반복자(iterator)를 반환하고, 존재하지 않으면 map.end()를 반환한다.

//int key = 2;

//auto it = myMap.find(key); (키 2를 찾기)

//if (it != myMap.end()) {...} (키가 존재하면, 이라는 조건식)

 

-4. size()

맵에 키-값 쌍의 개수를 반환하는 함수.

//myMap.size();

 

-5. erase(key)

맵의 특정 key를 가진 요소만 삭제하는 함수.

//myMap.erase(2); (key값이 2인 요소를 삭제한다)

//존재하지 않는 키값을 삭제해도 문제는 없으나, 삭제되었는지 여부를 알기 위해서 다음과 같이 함께 사용해본다.

//int removed = myMap.erase(2);

//if (removed == 0) { cout <<... << endl; } (키값이 없어서 삭제가 안된 경우 문자열이 별도로 출력되게 함)

 

-6. clear()

맵에 있는 모든 원소를 삭제하는 함수.

//myMap.clear();

---

 [2. 자주 사용되는 알고리즘]

STL은 다양한 컨테이너와 독립적으로 동작하는 범용 알고리즘을 제공한다. 이 범용 알고리즘을 적용하기 위해서는 반복자를 활용해야 한다. 반복자는 컨테이너의 요소를 추상화하여 일관된 방식으로 접근할 수 있도록 도와준다. 반복자를 함께 활용하는 대표적인 범용 알고리즘을 살펴본다.

 

 -1. sort()

#include <algorithm> 필요.

컨테이너 내부의 데이터를 정렬하는 함수. int/double과 같이 기본 타입의 경우, 사용자 정렬 함수가 없다면 오름차순 정렬한다.

//int arr[] : ~ , //int size = sizeof(arr) / sizeof(arr[0]);

//sort(arr, arr + size); (sort (시작 위치, 끝나는 위치). 즉 arr은 배열의 첫번째 주소이고 arr + size 는 시작 주소에 크기를 더한 값. 다시말해 마지막 데이터 바로 다음의 메모리 주소를 가리킨다. 이렇게 하는 이유는 C++ 표준 알고리즘 함수 대부분은 시작점은 포함하고 끝점은 포함하지 않기 때문이다. 기본적으로 i < n 이 포함되어 있다고 생각하면 될 것 같다.)

 

만약 사용자 정렬 함수를 이용해서 정렬하고 싶으면 대표적으로 comp(a, b)를 구현하게 된다.

comp(a, b) : 첫 번째 인자 a가 앞에 있는 원소를 의미하고, true 면 a와 b의 순서가 유지되고 false면 순서를 바꾼다.

오름차순 구현하는 방법은 다음과 같다.

//bool comp(int a, int b) { return a < b; } (오름차순)

//sort(arr, arr + size, comp); (세번째 인자로 comp 함수를 전달하여 정렬 규칙을 지정한다.)

 

 -2. find()

컨테이너 내부에서 특정 원소를 찾아 해당 원소의 반복자를 반환하는 함수.

find(first last, 찾을 값) 의 형식으로 사용한다. first last 가 탐색 대상이고, 원소를 찾은 경우 해당 원소의 반복자를 반환한다. 원소를 찾지 못한 경우 last 반복자를 반환한다.

//auto it = find(arr, arr + size, 4); (특정 값 4를 찾음)

//값이 있다면 특정 값 4의 반복자를 반환. 값이 없다면 last 반복자 반환.

 

---

 [3. 반복자]

알고리즘은 반복자를 기반으로 동작하기 때문에 반복자가 무엇인지 알 필요가 있다.

반복자는 컨테이너의 요소에 대한 일관된 접근 방식을 제공하므로,

알고리즘이 특정 컨테이너의 내부 구현과 무관하게 동작할 수 있다.

 

1. 순방향 반복자

begin() : 컨테이너의 첫 번째 원소를 가리키는 반복자.

end() : 컨테이너의 마지막 원소 다음을 가리키는 반복자. 대부분 find() 메서드 사용 시 찾지 못한 경우 end() 반복자를 반환.

 

2. 역방향 반복자

rbegin() : 컨테이너의 마지막 원소를 가리키는 역방향 반복자.

rend() : 컨테이너의 첫 번째 원소의 이전을 가리키는 역방향 반복자.

 

---

 

*오늘의 코드카타*

 

<평균 구하기>

 

정수를 담고 있는 배열 arr의 평균값을 return하는 함수, solution을 완성해보세요.

arr은 길이 1 이상, 100 이하인 배열입니다.

arr의 원소는 -10,000 이상 10,000 이하인 정수입니다.

 

1) 주어진 조건 안에서 해결

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

// arr_len은 배열 arr의 길이입니다.
double solution(int arr[], size_t arr_len) {
    double answer = 0;
    double sum = 0;
    
    for (size_t i = 0; i < arr_len; i++) {
        sum += arr[i];
    }
    
    answer = sum / arr_len;
    
    return answer;
}

sum을 선언 후 초기화

 

size_t i =0 부터, arr_len보다 작으면 i를 증가시키고,

sum에 arr[] i번째 인덱스에 있는 값을 더해라.

 

2) vector 사용

#include <vector>
#include <numeric>

using namespace std;

double solution(vector<int> arr) {
    double sum = accumulate(arr.begin(), arr.end(), 0.0);
    return sum / arr.size();

#include <vector>

accumulate(); 를 사용하려면 #include <numeric>이 필요

vector와 accumulate(); 를 사용해서  arr.begin() 부터 arr.end()-1 까지 더할 수 있다.

0.0을 쓰면 자료형 double을 굳이 쓸 필요 없이 알아서 자료형을 인식한다.