✍️Today I Learned

1. STL

---

STL(Standard Template Library)

• C++ 표준 템플릿 라이브러리
• 템플릿이기 때문에 데이터에 의존하지 않고 사용할 수 있는 라이브러리이다.

STL 구성요소

• 컨테이너: 데이터를 담는 자료구조
• 알고리즘: 동작
• 반복자: 각각 컨테이너나 알고리즘의 세부사항을 몰라도 동일한 문법으로 사용할 수 있게 해준다.

---

컨테이너

데이터를 담는 자료구조

특징
1. 템플릿으로 구현되어 있다.
2. 메모리 관리를 내부적으로 하여 메모리 해제를 직접 고려하지 않아도 된다. (new, delete 사용하지 않음)
3. 대부분 반복자를 제공한다.

Vector

배열과 유사한 컨테이너이다. 동일하지 않다.

1. 템플릿 클래스로 구현되어 특정 타입에 종속되지 않는다.
2. 내부 배열의 크기가 자동으로 조정된다.
3. 인덱스를 통해 특정 위치에 접근이 가능하다. (임의 접근 가능)
4. 삽입/삭제는 맨 뒤에서 하는게 좋다.
   : 앞이나 중간에서 하게 되면 기존 데이터들이 하나씩 뒤로 밀리면서 연산을 많이 하게 되어서 비효율적이다. 계속 맨 뒤가 아닌 위치에서 동작으로 해야한다면 다른 컨테이너를 고르는게 좋다.

Vector의 선언

#include <vector>
//빈 벡터 선언
vector<type> name;
// 초기화
vector<type> name(size, value);	// value: 초기값
// 초기화 리스트
vector<int> name = {1, 2, 3};
// 다른 벡터 복사하거나 대입
vector<type> name2(name);	// name 벡터값 복사
// 2차원 벡터
vector<vector<int>> vector2D(3, vector<int>(4, 7));

Vector의 동작

메서드 이름	동작	시간 복잡도
push_back(value)	맨 뒤에 원소 추가	O(1), 메모리 재할당시: O(N)
pop_back()	맨 끝 원소 제거	O(1)
size()	벡터의 요소 개수를 반환	O(1)
erase(address)	특정 위치(또는 구간) 원소 제거하고 다음 원소 주소 출력	O(N)
erase(first,last)	특정 구간 원소 제거. first에서 last 이전 까지 제거	O(N)

Set

중복되지 않는 원소들을 오름차순 정렬된 상태로 저장하는 컨테이너이다.
내부적으로 데이터를 정렬할 때 레드 블랙 트리를 사용한다.

1. 중복된 원소를 허용하지 않는다.
2. 원소 삽입과 동시에 오름차순으로 자동 정렬된다.
3. 정렬 상태를 유지하는 특성상 원소를 바로 수정할 수 없다.
4. 원소 변경 시 기존 원소를 삭제하고 새로운 값을 삽입->O(logN)
5. 인덱스를 지원하지 않는다.

❗정렬 상태를 유지하며 중복된 값을 저장해야 하는 경우->multiset
❗원소의 정렬이 필요하지 않고 빠른 탐색이 중요한 경우->unordered_set
❗인덱스를 지원하지 않으므로 인덱스로 원소에 접근해야 하는 경우->vector

Set의 선언

#include <set>
//빈 셋 선언
set<type> name;
// 초기화 리스트
set<int> name = {3, 4, 1, 2, 3};	//중복 허용X, 오름차순 정렬
									// {1, 2, 3, 4}로 생성 됨
// 다른 셋 복사
set<type> name2 = name;	// name 복사

Set의 동작

메서드 이름	동작	시간 복잡도
insert()	원소 삽입할 때 마다 정렬된 상태를 유지	O(logN)
erase(address)	원소 삭제할 때 마다 정렬된 상태를 유지	O(logN)
clear()	모든 원소 삭제	O(N)

Map

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

1. 키-값 쌍은 pair<const Key, Value> 형태로 저장된다.
2. 키값을 기준으로 내부데이터가 오름차순으로 자동 정렬된다.(원소가 추가될 때도 자동 정렬)
3. 중복된 키값은 허용되지 않는다.

Map의 선언

#include <iostream>
#include <map>
// 맵 선언
map<key type, value type> name;
// 맵 초기화
map<string, int> name = {{"A", 1}, {"B", 2}};
// 맵 복사
map<key type, value type> name2 = name;
// 요소 추가
// key없으면 추가, 있으면 value 변경
name[key] = value;
// 요소 변경
// key없으면 out of range 예외 발생
name.at(key) = value;
// insert()
// 이미 있는 key를 삽입하려하면 삽입은 무시되고
// 해당 키-값 쌍의 반복자와 함께 삽입 성공 여부의 bool값을 반환한다.
// pair<iterator, bool>
name.insert({key, value});
name.insert(make_pair(key, value));
// 요소 출력
for(const auto& pair : name){
	std::cout << pair.first << endl;	// Key
    std::cout << pair.second << endl;	// Value
}

Map의 동작

메서드 이름	동작	시간 복잡도
insert()	make_pair나 {}로 키-값 쌍을 만들어 추가	O(log N)
find()	특정 키가 map에 존재하는지 확인	O(log N)
size()	맵의 키-값쌍의 개수를 반환	O(1)
erase(key)	특정 key를 가진 요소 삭제	key 이용:O(log N)/반복자 이용: O(1)
clear()	맵의 모든 요소 삭제	O(N)

---

알고리즘

다양한 컨테이너와 독립적으로 동작하는 범용 알고리즘(find, sort...)
반복자에 의해 특정 컨테이너의 내부 구현을 몰라도 동일한 방식으로 알고리즘을 적용할 수 있다.

sort()

기본 타입의 경우 사용자 정렬 함수가 없으면 오름차순으로 정렬된다.
시간 복잡도: 평균적으로 O(N log N)

// 배열 정렬
#include <algorithm>

bool comp(int a, int b){
	return a > b;	//내림차순
}

int main(){

in array[] = {5, 2, 9, 1, 5, 6};
sort(array.begin(), array.end(), comp);

}

// 사용자 정의 class 정렬
#include <iostream>
#include <vector>
#include <algorithm> // sort 함수 포함
using namespace std;

class Person {
private:
    string name;
    int age;

public:
    // 생성자
    Person(string name, int age) : name(name), age(age) {}

    // Getter 함수
    string getName() const { return name; }
    int getAge() const { return age; }
};

// 다중 기준 정렬 함수 (나이 오름차순 → 이름 오름차순)
// C++ 라이브러리가 정보를 알 수 없기때문에 사용자 정렬 함수를 필수적으로 구현해야한다.
bool compareByAgeAndName(const Person& a, const Person& b) {
    if (a.getAge() == b.getAge()) {
        return a.getName() < b.getName(); // 이름 오름차순
    }
    return a.getAge() < b.getAge(); // 나이 오름차순
}

int main() {
    vector<Person> people = {
        Person("Alice", 30),
        Person("Bob", 25),
        Person("Charlie", 35),
        Person("Alice", 25)
    };

    // 나이 → 이름 순으로 정렬
    sort(people.begin(), people.end(), compareByAgeAndName);

    // 결과 출력
    for (const Person& person : people) {
        cout << person.getName() << " (" << person.getAge() << ")" << endl;
    }
    return 0;
}

사용자 정렬 함수 comp(a, b) 구현시 알아야할 점

1. 현재 컨테이너에서 첫 번째 인자 a가 앞에 있는 원소를 의미한다.
2. comp(a, b)의 반환 타입은 bool
3. comp(a, b)가 True이면 순서 유지, False이면 a와 b의 순서를 바꾼다.

find()

컨테이너 내부에서 특정 원소를 찾아 해당 원소의 반복자를 반환한다.
시간 복잡도: O(N)
find(first, last, 찾을 값)
1. [first, last)가 탐색 대상
2. 원소를 찾은 경우 해당 원소의 반복자를 반환한다.
3. 찾지 못한 경우 last 반복자를 반환한다.

count()

범위 [first, last) 내에서 특정 값이 몇 번 등장하는지를 반환한다.
시간 복잡도: O(N)
count(first, last, value)

unique()

범위 [first, last) 내에서 연속된 중복 요소를 제거한다.
시간 복잡도: O(N)
unique(first, last)
1. 연속되지 않은 중복 값은 제거하지 않는다.
2. 실제로 컨테이너에서 원소가 삭제되는 것은 아니며 각 원소의 첫번째만 유지되도록 원소들을 앞부터 덮어씌워 재배열한다.
3. 중복 제거 후 마지막 고유 원소의 다음 위치를 가리키는 반복자를 반환한다.
4. 반환된 반복자 이후 영역은 남아있으므로 erase()로 완전히 제거한다.

// unique()와 erase()를 조합해 실제로 중복 원소 삭제
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {1, 1, 2, 2, 3, 3, 3};

    v.erase(unique(v.begin(), v.end()), v.end());

    for (int val : v) {
        cout << val << " ";
    }

    return 0;
}
// 출력결과: 1 2 3
// erase–remove idiom을 통해 연속된 중복 요소가 완전히 제거됨

---

반복자

컨테이너 요소에 대한 일관된 접근 방법을 제공하여 알고리즘이 특정 컨테이너의 내부 구현과 무관하게 동작할 수 있게 도와준다.

순방향 반복자

앞에서 뒤로 순차적으로 순회하는 반복자
1. begin(): 컨테이너의 첫 번째 원소를 가리키는 반복자
2. end(): 컨테이너의 마지막 원소 다음을 가리키는 반복자
- 일관된 반복 구조를 유지한다.
- 탐색 실패를 쉽게 표현할 수 있다.

역방향 반복자

뒤에서 앞으로 역순으로 순회하는 반복자
1. rbegin(): 컨테이너의 마지막 원소를 가리키는 반복자
2. rend(): 컨테이너의 첫 번째 원소 이전을 가리키는 반복자