[VEDA] 13일차

나우히즈·2025년 4월 2일

C++veda 한화비전

VEDA

목록 보기

12/16

12장. STL와 컨테이너와 알고리즘

컨테이너에는 뭔가를 담는다.
→ 데이터, 오브젝트 등을 담게 될 것.
컨테이너란 객체를 저장할 수 있는. 일종의 창고와 같은 역할을 한다. (저장소)

반복자. 이터레이터는 컨테이너 내부 원소들을 순회하는 객체.
→ 반복을 할 수 있는 대상. 타겟.

클래스 템플릿 형태로 만들어져 있어서, 클래스 템플릿 안에 멤버 함수들을 다양하게 제공

std::array

고정 크기 배열.
[] 연산자로 각 원소에 접근가능하며, 초과된 인덱스에 접근 시 UB
→ 이 문제 해결을 위해 at() 함수 생성.
이 멤버 함수를 사용하면 범위를 초과했을 떄 outofrange 익셉션 출력.

size() 를 통해 크기값을 받아볼 수있따.
at 함수는 컨테이너면 대부분 구현이 되어있으므로, 안전한 코딩을 위해선 순차컨테이너 접근 시 at를 활용하면 안전한 코딩이 가능하다.

std::array<int, 5> my;
my = { 1 }; // 1, 0, 0, 0, 0 담김

✅ std::array 선언 기본 문법

std::array<타입, 크기> 이름;

✅ 1. 중괄호 초기화 (리스트 초기화) ✅ 가장 일반적인 방법

std::array<int, 5> arr = {1, 2, 3, 4, 5};

• 배열 전체가 정확히 초기화됨
• 개수가 부족하면 자동으로 0으로 채움
• 개수가 초과되면 컴파일 에러

std::array<int, 5> arr = {1, 2};       // 나머지: 0, 0, 0
std::array<int, 5> arr = {1, 2, 3, 4, 5, 6}; // ❌ 오류: 초과

✅ 2. C++17부터는 () 초기화도 가능

std::array arr1{1, 2, 3}; // C++17 이상에서 타입 추론 가능

• std::array<int, 3>로 추론됨
• 템플릿 매개변수 추론 가이드 (CTAD) 덕분에 타입 생략 가능

✅ 3. fill() 함수로 일괄 초기화

std::array<int, 5> arr;
arr.fill(42);  // 모든 원소가 42로 채워짐

• 모든 요소를 동일한 값으로 초기화할 때 유용
• 단, fill()은 런타임 호출이므로 컴파일 타임 초기화는 아님

✅ 4. 기본 생성 후 수동 대입

std::array<int, 3> arr;
arr[0] = 10;
arr[1] = 20;
arr[2] = 30;

• 일반 배열처럼 사용 가능

✅ 5. 구조체 멤버로 쓸 경우

struct MyData {
    std::array<int, 3> values{1, 2, 3};  // C++11 이상 초기화 지원
};

vector

초기화할 때,

vector<type> name;
vector<type> name(size);
vector<type> name(size, value);
vector<type> name = {val1, val2, ...};

마찬가지로 [], at() 가능.

push_back() 을 통해 벡터의 뒤에서부터 차곡 차곡 데이터를 쌓을 수 있음.

✅ std::vector란?

C++ STL에서 제공하는 동적 배열 컨테이너

요소들이 메모리상 연속적으로 배치되며,

자동으로 크기를 조절할 수 있습니다.

#include <vector>
#include <iostream>

✅ 핵심 특징

특징	설명
동적 크기 조절	push_back() 등으로 자동으로 크기 증가
연속된 메모리	C 배열처럼 [] 또는 포인터로 접근 가능
타입 안전	템플릿 기반, 자료형 명확
효율적	메모리 재할당은 필요 시만 발생 (성능 좋음)

✅ 주요 생성 방법

std::vector<int> v1;                      // 빈 벡터
std::vector<int> v2(5);                   // 크기 5, 값은 0
std::vector<int> v3(5, 10);               // 크기 5, 값은 10
std::vector<int> v4 = {1, 2, 3, 4, 5};    // 리스트 초기화

✅ 주요 멤버 함수

함수	설명
push_back(val)	끝에 요소 추가
pop_back()	마지막 요소 제거
size()	현재 요소 개수
capacity()	재할당 없이 담을 수 있는 최대 요소 수
resize(n)	크기 조정 (늘리면 0 또는 기본값으로 채움)
clear()	모든 요소 제거 (capacity는 유지)
empty()	비어있는지 확인
front(), back()	첫/마지막 요소 참조
at(i)	i번째 요소 접근 (범위 체크 O)
operator[i]	i번째 요소 접근 (범위 체크 X)
erase()	인자의 이터레이터 제거

✅ 반복자 사용

std::vector<int> v = {1, 2, 3};

for (std::vector<int>::iterator it = v.begin(); it != v.end(); ++it)
    std::cout << *it << " ";

for (int n : v)
    std::cout << n << " ";

✅ 메모리 관련

• vector는 내부적으로 포인터를 통해 메모리 할당하고,

• 크기가 초과되면 더 큰 공간을 새로 할당한 후 기존 데이터를 복사함

• 이 과정이 반복되지 않도록 미리 reserve()로 예약 가능:

v.reserve(100);  // capacity를 미리 확보해두면 reallocation 줄일 수 있음

push_back() vs emplace_back()

✅ 공통점

• 둘 다 컨테이너의 끝에 요소를 추가하는 함수입니다.

• 대상 컨테이너: vector, deque, list 등

✅ push_back() — 기존 객체를 복사(또는 이동)해서 추가

std::vector<std::string> vec;
std::string name = "Alice";
vec.push_back(name);           // 복사
vec.push_back(std::move(name)); // 이동

🔹 특징

항목	설명
인자	이미 생성된 객체
동작	복사 또는 이동 생성자를 통해 컨테이너에 추가
단점	한 번 생성 → 또 복사/이동 → 비효율 발생 가능

✅ emplace_back() — 객체를 직접 생성해서 추가

vec.emplace_back("Bob");  // 문자열 생성 + 바로 벡터에 삽입

🔹 특징

항목	설명
인자	객체를 구성하는 생성자 인자 전달
동작	컨테이너 내부에서 직접 생성자 호출하여 객체 생성 (in-place)
장점	불필요한 복사/이동 생략 → 성능 ↑

✅ 차이 정리

항목	push_back	emplace_back
인자	완성된 객체	생성자 인자
동작	복사 or 이동 생성자 호출	직접 생성자 호출 (in-place 생성)
성능	중간에 복사/이동 필요	복사/이동 생략 가능 → 성능 우수
사용 시기	기존 객체 있을 때	객체를 바로 만들고 추가할 때

✅ 예제 비교

struct Person {
    std::string name;
    int age;

    Person(std::string n, int a) : name(n), age(a) {
        std::cout << "생성됨: " << name << "\n";
    }
};

push_back 사용

std::vector<Person> people;
Person p("Alice", 30);
people.push_back(p);             // 복사
people.push_back(Person("Bob", 25)); // 이동

emplace_back 사용

people.emplace_back("Charlie", 20);  // 직접 생성 (in-place)

✔️ emplace_back()은 복사/이동 없이 바로 내부에서 Person("Charlie", 20) 생성

✅ 어떤 걸 써야 할까?

상황	추천 함수
이미 생성된 객체가 있다	push_back()
새 객체를 직접 추가하고 싶다	✅ emplace_back() (권장)
성능이 중요하다	emplace_back()이 더 효율적

vector에서 insert함수를 통해 중간 삽입이 가능하다.
삭제를 위해선 erase 함수를 사용하여 지정한 iterator 제거가 가능함~
const_iterator도 있는데, 이는 반복자가 가리키는 원소 값을 변경할 수 없게하기위함.
reverse_iterator는 뒤에서부터 rbegin(). + 할수록 뒤에서 앞으로 하나씩 온다.

std::list

중간 삽입 변경 삭제가 많이 이루어져야한다면 list 형태가 좀 더 효율적인 형태가 됨.

프로그램 틁성에 맞추어 알맞는 자료구조를 선태갛자

std::list는 이중 연결 리스트(doubly linked list)를 구현한 컨테이너예요.

✅ std::list란?

std::list는 C++ STL에서 제공하는 이중 연결 리스트 컨테이너입니다.

노드 기반 구조로, 각 요소가 앞뒤 노드를 가리키는 포인터를 가지고 있어

중간 삽입/삭제에 매우 효율적입니다.

✅ 기본 문법

#include <list>
#include <iostream>

std::list<int> myList;  // 빈 리스트

✅ 주요 특징

항목	내용
구조	이중 연결 리스트 (Doubly Linked List)
메모리	요소들이 연속되지 않음 (동적 노드 분산 배치)
접근	임의 접근 불가 ([] 연산자 없음)
삽입/삭제	중간 삽입/삭제가 매우 빠름 (O(1))
반복자	양방향(Bidirectional Iterator) 제공

✅ 주요 멤버 함수

함수	설명
push_back(val)	끝에 추가
push_front(val)	앞에 추가
pop_back() / pop_front()	끝/앞 제거
insert(pos, val)	반복자 위치에 삽입
erase(pos)	반복자 위치 삭제
clear()	전체 삭제
size() / empty()	크기 확인, 비어있는지 확인
sort()	정렬 (기본 오름차순)
remove(val)	해당 값 모두 제거
unique()	인접 중복 제거 (정렬된 상태에서 주로 사용됨)
merge(list2)	두 정렬된 리스트 병합
reverse()	리스트 뒤집기

✅ 반복자 사용 예

std::list<int> lst = {1, 2, 3, 4};

for (std::list<int>::iterator it = lst.begin(); it != lst.end(); ++it)
    std::cout << *it << " ";

또는 C++11 이상이라면 범위 기반 for문:

for (int x : lst)
    std::cout << x << " ";

✅ 예제 코드

std::list<int> nums;

nums.push_back(3);
nums.push_front(1);
nums.push_back(5);

// 출력: 1 3 5
for (int n : nums)
    std::cout << n << " ";

nums.sort();         // 정렬
nums.reverse();      // 뒤집기
nums.remove(3);      // 값 3 제거

✅ std::list vs std::vector

항목	std::list	std::vector
메모리	연결 리스트 (포인터 기반)	연속 메모리
임의 접근 ([i])	❌ 불가능	✅ 가능
중간 삽입/삭제	✅ 빠름 (O(1))	❌ 느림 (O(n))
반복자 무효화	대부분 안전	삽입/삭제 시 자주 무효화
캐시 효율성	낮음 (메모리 흩어짐)	높음 (연속성)
사용 추천	삭제/삽입 많은 경우	순차 접근/랜덤 접근 많은 경우

✅ 언제 std::list를 써야 할까?

• 중간 요소를 자주 삽입하거나 삭제해야 하는 경우

• 반복자는 유지한 채 요소 제거가 필요한 경우 (erase(it++))

• 정렬된 상태에서 삽입/병합/제거가 많은 경우

✅ 마무리 요약

✔️ std::list는 중간 삽입/삭제가 매우 빠른 이중 연결 리스트 컨테이너입니다.

✔️ 임의 접근은 안 되지만, 양방향 반복자를 통해 효율적인 순차 작업이 가능합니다.

✔️ 삽입/삭제 위주라면 list, 랜덤 접근이 많다면 vector를 선택하세요.

std::deque

벡터는 동적할당이니, 사이즈가 계속 늘어난다면 재할당을 계속 해야함.

연속적이여야되다보니, 기존 데이터들을 다시 새로운 공간에 옮기는 작업을 해야함.

새로운 공간을 확ㅇ보할때마다 속도가 좀 떨어진

→ deque을 통해 이 단점을 보완.

✅ std::deque란?

std::deque는 양쪽(앞/뒤)에서 삽입과 삭제가 모두 가능한 동적 시퀀스 컨테이너입니다.

std::vector와 비슷하게 임의 접근(random access)이 가능하면서도,

std::list처럼 앞쪽 삽입/삭제도 빠르게 처리할 수 있어요.

✅ 주요 특징 요약

항목	내용
구조	블록 기반의 연속 메모리 배열 (엄밀히 말하면 완전히 연속은 아님)
임의 접근	✅ 빠름 (O(1)) — [], at() 지원
앞뒤 삽입/삭제	✅ 빠름 (O(1)) — push_front, pop_front 지원
중간 삽입/삭제	❌ 느림 (O(n))
내부 구조	작은 배열 블록들을 연결한 구조 (vector보다 덜 연속적)

✅ 주요 함수

함수	설명
push_back(val)	뒤에 요소 추가
push_front(val)	앞에 요소 추가
pop_back()	뒤에서 제거
pop_front()	앞에서 제거
at(i) / operator[i]	i번째 요소 접근 (범위 체크 유무 차이)
front() / back()	앞/뒤 요소 참조
size() / empty() / clear()	기타 유틸리티 함수
insert(), erase()	중간 삽입/삭제 (느림)

✅ 사용 예시

#include <deque>
#include <iostream>

int main() {
    std::deque<int> dq;

    dq.push_back(10);
    dq.push_front(20);
    dq.push_back(30);

    for (int val : dq)
        std::cout << val << " ";  // 출력: 20 10 30

    dq.pop_front();  // 10 30
    std::cout << "\nfront: " << dq.front() 
					    << ", back: " << dq.back() << '\n';
}

✅ 언제 deque를 써야 할까?

• 앞뒤에서 삽입/삭제가 모두 빈번한 경우

• 임의 접근도 자주 필요

• std::vector보다 앞쪽 작업이 많은 경우

• 예: 슬라이딩 윈도우, 이중 버퍼링 구조 등

✅ 주의할 점

• 메모리 구조가 vector보다 약간 덜 연속적 → 대형 배열 연산엔 부적합할 수 있음

• 중간 삽입/삭제는 여전히 느림 (O(n))

• 반복자 무효화: 앞/뒤 삽입 시 모든 반복자가 무효화될 수 있음

✅ STL에서 deque가 기본 컨테이너인 경우

어댑터 컨테이너	내부 컨테이너
std::queue	기본적으로 std::deque
std::stack	기본적으로 std::deque

연관 컨테이너

특정 키(key)를 이용해서 컨테이너를 구상하고 컨테이너 내부에 키를 통해 접근하는 컨테이너를 연관 컨테이너를 한다.

검색을 많이 해야하는 경우 유용하다.

set / multiset / map / multimap

이 네 가지는 모두 정렬 기반의 컨테이너이며, 내부적으로 이진 탐색 트리 (보통 Red-Black Tree)로 구현되어 있어요.

따라서 자동 정렬, 중복 허용 여부, 키-값 구조 등의 차이만 잘 이해하면 됩니다!

✅ 핵심 요약 비교표

컨테이너	키(key)	값(value)	중복 허용	구조
set	O	X (key만)	❌ 중복 X	정렬된 키 집합
multiset	O	X (key만)	✅ 중복 O	정렬된 키 집합
map	O	O (value 있음)	❌ 중복 X	(key, value) 쌍
multimap	O	O (value 있음)	✅ 중복 O	(key, value) 쌍

✅ 1. std::set

중복 없는 정렬된 데이터 집합

🔹 특징

• key만 저장 (set, set 등)

• 자동으로 정렬됨 (기본 less<>, 오름차순)

• 중복된 값을 허용하지 않음

• 내부 구현: Red-Black Tree

🔹 사용 예

std::set<int> s;
s.insert(3);
s.insert(1);
s.insert(3);  // 중복 → 무시됨

for (int x : s)
    std::cout << x << " ";  // 출력: 1 3

✅ 2. std::multiset

중복을 허용하는 정렬된 집합

🔹 특징

• set과 동일하지만 중복된 값 허용

• 중복된 요소도 모두 저장

🔹 사용 예

std::multiset<int> ms;
ms.insert(3);
ms.insert(1);
ms.insert(3);  // 중복 → 허용됨

for (int x : ms)
    std::cout << x << " ";  // 출력: 1 3 3

✅ 3. std::map

key와 value 쌍으로 구성된 연관 컨테이너 (Key → Value)

🔹 특징

• std::map<Key, Value> 형태

• Key는 중복 불가, 자동 정렬됨

• Key를 기준으로 정렬, 삽입/탐색/삭제는 로그 시간 O(log n)

🔹 사용 예

std::map<std::string, int> phonebook;
phonebook["Alice"] = 1234; // 존재하지 않는 키 접근 시 자동 삽입.
phonebook["Bob"] = 5678;
phonebook["Alice"] = 1111;  // 기존 값 덮어쓰기

for (auto& [name, number] : phonebook)
    std::cout << name << ": " << number << '\n';
// 출력: Alice: 1111, Bob: 5678

C++의 std::map은 operator[]를 통해 존재하지 않는 키를 접근하면, 자동으로 삽입합니다.

✅ 동작 설명

std::map<char, int> m;
m['z'] = 12;

• 'z'라는 key가 map에 없으면

• 기본 생성자(default constructor)를 통해 value를 0으로 초기화한 후 삽입

• 그 다음 = 12 할당이 실행됨

즉, 이 코드는 다음과 같은 두 단계로 동작합니다:

m['z'] → key 'z'가 없으니 pair{'z', int()} 삽입 (int()는 0)
m['z'] = 12; → value에 12 대입

✅ 4. std::multimap

key 중복을 허용하는 map

🔹 특징

같은 key에 여러 value 저장 가능
key가 중복될 수 있으므로 operator[] 대신 insert()만 사용
erase 시 중복되는 원소들 모두 삭제
equal_range 라는 중복된 키의 밸류들을 모아보기 가능.

🔹 사용 예

std::multimap<std::string, int> grades;
grades.insert({"Alice", 80});
grades.insert({"Alice", 90});
grades.insert({"Bob", 85});

for (auto& [name, score] : grades)
    std::cout << name << ": " << score << '\n';

✅ 주요 차이 정리

구분	set	multiset	map	multimap
저장 구조	key	key	key-value	key-value
key 중복	❌	✅	❌	✅
value 접근	불가	불가	map[key] 또는 .at(key)	없음 (insert로만 접근)
정렬 여부	자동 정렬 (기본 오름차순)
내부 구현	Red-Black Tree (이진 탐색 트리 기반)

✅ Tip: 정렬 방식 바꾸기

std::set<int, std::greater<>> s;  // 내림차순 정렬

혹은 사용자 정의 정렬자도 가능해요.

컨테이너 어댑터

stack, queue 등 자료구조

이 둘은 STL 내부에서 컨테이너 어댑터(Container Adapters)라고 부르며,

기존 컨테이너를 기반으로 제한된 방식으로 동작하게 만든 구조입니다.

✅ std::stack - 후입선출 (LIFO)

📌 개념

마지막에 넣은 데이터가 가장 먼저 나오는 자료구조

한쪽 끝(Top)에서만 삽입과 삭제가 가능

📌 기본 문법

#include <stack>

std::stack<int> s;

📌 주요 함수

함수	설명
push(val)	요소 추가
pop()	top 요소 제거 (리턴 없음)
top()	맨 위 요소 반환 (읽기 전용)
size()	요소 개수
empty()	비었는지 여부

📌 예제

std::stack<int> s;
s.push(1);
s.push(2);
std::cout << s.top();  // 출력: 2
s.pop();
std::cout << s.top();  // 출력: 1

✅ std::queue - 선입선출 (FIFO)

📌 개념

먼저 들어간 데이터가 먼저 나오는 자료구조

앞(front)에서 꺼내고, 뒤(back)에 넣는 구조

📌 기본 문법

#include <queue>

std::queue<int> q;

📌 주요 함수

함수	설명
push(val)	뒤에 요소 추가
pop()	앞 요소 제거 (리턴 없음)
front()	맨 앞 요소 참조
back()	맨 뒤 요소 참조
size()	요소 개수
empty()	비었는지 여부

📌 예제

std::queue<int> q;
q.push(10);
q.push(20);
std::cout << q.front();  // 출력: 10
q.pop();
std::cout << q.front();  // 출력: 20

✅ 공통점: 컨테이너 어댑터

항목	설명
내부 컨테이너	기본적으로 std::deque 사용 (변경 가능)
접근 방식	제한적 인터페이스 제공 ([] 접근 불가)
동작 방식	stack: LIFO / queue: FIFO
안전성	pop() 호출 전에는 empty() 체크 권장

⚠️ 주의사항

• pop()은 반환값이 없습니다.

→ 값을 확인하려면 top() 또는 front()로 먼저 꺼낸 후 pop() 해야 해요.

int x = s.top(); s.pop();  // ❗ 이런 식으로 사용

• 직접 반복자를 사용할 수 없습니다 (begin() 없음).

→ 순회하려면 복사해서 꺼내는 방식 사용

12-2 알고리즘

✅ `<algorithm>`이란?

<algorithm>은 C++ 표준 라이브러리에서 제공하는 범용 알고리즘 함수들의 집합입니다.

정렬, 검색, 수치 연산, 복사, 변환, 제거 등 다양한 범용 알고리즘이 정의되어 있어요.

✔️ 모든 함수는 템플릿 기반으로 만들어졌고,

✔️ vector, array, list, deque 등 대부분의 STL 컨테이너와 호환됩니다.

✔️ 반복자 기반으로 작동하므로 유연하고 강력합니다.

✅ `<algorithm>`의 기능 분류

기능 범주	대표 함수
정렬	sort(), stable_sort(), partial_sort(), nth_element()
검색	find(), find_if(), binary_search(), count()
변형	copy(), move(), transform(), swap()
제거	remove(), remove_if(), unique()
수치 연산	accumulate(), iota(), inner_product() (→ `<numeric>`에 있음)
최대/최소	min(), max(), min_element(), max_element()
비교/검사	equal(), lexicographical_compare(), all_of()
기타	reverse(), rotate(), shuffle(), fill()

✅ 가장 자주 쓰는 함수 예제 모음

1. std::sort() - 정렬을 통해 빠른 검색 가능해짐

#include <algorithm>
#include <vector>

std::vector<int> v = {5, 3, 8, 1};
std::sort(v.begin(), v.end());  // 오름차순 정렬

std::sort(v.begin(), v.end(), std::greater<>());  // 내림차순 정렬

2. std::find()

auto it = std::find(v.begin(), v.end(), 8);
if (it != v.end()) std::cout << "찾았다!";

3. std::count() / count_if()

int c = std::count(v.begin(), v.end(), 3);  // 3의 개수 세기

int even = std::count_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; });

4. std::remove() + erase() (지우기 패턴)

v.erase(std::remove(v.begin(), v.end(), 3), v.end());  // 값이 3인 요소 모두 제거

5. std::reverse() / std::rotate()

std::reverse(v.begin(), v.end());  // 전체 뒤집기

std::rotate(v.begin(), v.begin() + 1, v.end());  // 첫 요소를 뒤로 보내기

6. std::min_element() / std::max_element()

auto it = std::min_element(v.begin(), v.end());
std::cout << *it;

✅ 반복자 기반이란?

• 대부분의 알고리즘은 다음처럼 사용됩니다:

std::algorithm(컨테이너.begin(), 컨테이너.end(), [조건/비교자]);

따라서 어떤 컨테이너든 반복자만 있으면 활용 가능합니다.

const를 붙여야하는 이유

C++에서 const는 “변경하지 않겠다”는 약속이자, 컴파일러가 타입 안전성을 보장해주는 도구입니다.

✅ 핵심 개념 1: std::sort()가 호출하는 비교 함수

```
bool comp(const Circle& lhs, const Circle& rhs) {
    return lhs < rhs;
}
```

여기서 lhs < rhs는 결국 다음과 같이 해석됩니다:

```
lhs.operator<(rhs);
```

그런데 lhs는 const Circle&이므로, lhs의 멤버 함수는 const여야 호출 가능합니다.
const 객체이기 때문에, 해당 객체의 멤버함수가 멤버변수 값을 바꾸지 않는다는 보장이 박혀있어야함.

✅ 핵심 개념 2: 멤버 함수 뒤에 const가 붙는 이유

```
bool Circle::operator<(const Circle& c) const {
    return this->radius < c.radius;
}
```

const는 이 멤버 함수가 객체의 멤버 변수를 변경하지 않겠다는 약속입니다.
this 포인터가 const Circle*로 해석되므로,

→ 이 함수 안에서는 radius를 읽기만 가능하고, 수정은 불가

이 const가 없으면, const Circle& lhs로 들어온 객체에서 operator<를 호출할 수 없습니다.
“const 객체에 비-const 멤버 함수 호출 불가” 에러가 납니다.

✅ 어떤 기준으로 const를 붙여야 할까?

멤버 함수에서 멤버 변수를 변경하지 않는다면 무조건 const 붙이세요!

예: getter, 비교 연산자, 출력 함수 등

int getRadius() const;             // ✅ 읽기 함수
bool operator<(const Circle&) const; // ✅ 비교 함수
void setRadius(int);              // ❌ 멤버 변경 → const 없이

std::sort와 std::stable_sort는 모두 C++ 헤더에서 제공하는 정렬 알고리즘입니다.

하지만 동작 방식과 정렬 안정성(Stable 여부)에서 중요한 차이가 있습니다.

✅ 핵심 차이 요약

항목	std::sort	std::stable_sort
정렬 안정성	❌ 불안정 정렬	✅ 안정 정렬 (순서 보존됨)
평균 시간 복잡도	O(n log n)	O(n log² n) 또는 O(n log n) (C++11 이후 개선)
내부 알고리즘	IntroSort (QuickSort + HeapSort + InsertionSort)	MergeSort 기반
비교 함수 지원	✅ 사용자 정의 비교자 가능	✅ 동일
사용 헤더

✅ 1. std::sort()

기본 정렬 함수로 빠르고 일반적인 정렬에 사용됩니다.

📌 특징

• 불안정 정렬 → 동일 값들의 상대 순서가 바뀔 수 있음

• 내부적으로 IntroSort 알고리즘 사용

• QuickSort + HeapSort + InsertionSort 조합

• 시간 복잡도 평균 O(n log n)

📌 사용 예

std::vector<int> v = {3, 1, 4, 1, 5};
std::sort(v.begin(), v.end());  // 오름차순 정렬

📌 사용자 정의 정렬

std::sort(v.begin(), v.end(), std::greater<>());  // 내림차순

✅ 2. std::stable_sort()

정렬된 후에도 같은 값들의 상대적 순서를 유지하는 정렬

📌 특징

• 안정 정렬 (Stable Sort)

→ 같은 key를 가진 요소들의 입력 순서가 유지

• 내부적으로 Merge Sort 사용

• 복잡도: O(n log² n) (C++11 이후 일부 구현은 O(n log n)까지 개선됨)

• 메모리 사용량이 많아질 수 있음 (일부 구현은 외부 버퍼 사용)

📌 사용 예

std::vector<std::pair<std::string, int>> people = {
    {"Alice", 25}, {"Bob", 25}, {"Carol", 30}
};

// 나이 기준 정렬, 이름 순서는 유지
std::stable_sort(people.begin(), people.end(),
    [](auto& a, auto& b) { return a.second < b.second; });

✔️ 결과: Alice, Bob, Carol — 나이는 같지만 입력 순서 유지

✅ “Stable”이 중요한 상황 예시

struct Student {
    std::string name;
    int score;
};

std::vector<Student> students = {
    {"Alice", 90},
    {"Bob", 90},
    {"Charlie", 85}
};

❌ std::sort로 정렬하면:

결과: Bob, Alice, Charlie (입력 순서 바뀔 수 있음)

✅ std::stable_sort로 정렬하면:

결과: Alice, Bob, Charlie (입력 순서 유지)

✅ 마무리 요약

구분	std::sort	std::stable_sort
빠름?	✅ 빠름 (O(n log n))	❌ 느릴 수 있음 (O(n log² n))
순서 유지?	❌ 불안정	✅ 안정
추천 상황	일반 정렬	정렬 기준 중복 값 많고, 순서 중요할 때
사용자 비교자	✅ 지원	✅ 지원

✔️ 성능 중시 → std::sort

✔️ 정렬 후 동일 값의 순서도 중요하다 → std::stable_sort

필요하시면 구조체 다중 정렬(2차 기준 등)에서 두 정렬의 차이도 예제로 보여드릴게요! 😊

✅ 1. std::find (범용 알고리즘)

#include <algorithm>
#include <vector>

std::vector<int> v = {1, 2, 3, 4};
auto it = std::find(v.begin(), v.end(), 3);

📌 특징

항목	설명
정의 위치	헤더
범용 알고리즘	✅ 반복자 범위로 탐색 (어떤 컨테이너든 가능)
반환값	찾은 위치의 반복자 (끝이면 .end() 반환)
동작 방식	선형 탐색 (O(n))
요구 조건	== 연산자 정의되어 있어야 함

✅ 2. 컨테이너 멤버 함수 find()

주로 연관 컨테이너(map, set 등)에서 제공하는 전용 탐색 함수

📌 특징

항목	설명
정의 위치	각 컨테이너 클래스 내부 (std::map, std::set 등)
지원 컨테이너	✅ 연관 컨테이너 (set, map, unordered_map, 등)
반환값	해당 key의 반복자 (end()이면 못 찾음)
동작 방식	O(log n) (트리 기반) 또는 O(1) (해시 기반)
비교 방식	operator< (트리 기반), 해시 + operator== (unordered)

✅ 차이 요약

항목	std::find	컨테이너의 find()
사용 대상	모든 컨테이너 (vector, list, array 등)	연관 컨테이너 (set, map, unordered_*)
필요 조건	== 연산자 필요	키 타입에 operator< or 해시 필요
시간 복잡도	O(n) (선형 탐색)	O(log n) or O(1)
호출 방식	헤더 함수	컨테이너의 멤버 함수

컨테이너 std::find 멤버 find() 권장
vector, deque, list ✅ 사용 가능 (선형 탐색) ❌ 없음 ✔️ std::find
set, map, unordered_set, unordered_map ❌ 느림 (선형 탐색) ✅ 고성능 (O(log n) or O(1)) ✔️ 멤버 find() 사용 권장

컨테이너	std::find	멤버 find()	권장
vector, deque, list	✅ 사용 가능 (선형 탐색)	❌ 없음	✔️ std::find
set, map, unordered_set, unordered_map	❌ 느림 (선형 탐색)	✅ 고성능 (O(log n) or O(1))	✔️ 멤버 find() 사용 권장

std::find() 는 원소 갯수가 많으면 좀 느리다(O(n)).

원소 순서대로 접근하기 때문. (순차 검색 알고리즘)

대상이 정렬되어있다면, std::binary_search를 사용하는게 좋다.

특별 : std::distance

std::distance는 C++ 표준 라이브러리에서 제공하는 아주 유용한 반복자 관련 유틸리티 함수입니다.

“두 반복자 간의 거리(간격)“를 계산해주는 역할을 하죠!

✅ std::distance란?

```
#include <iterator>

template<class InputIterator>
typename std::iterator_traits<InputIterator>::difference_type
distance(InputIterator first, InputIterator last);
```

🔹 [first, last) 범위 내 요소의 개수를 계산해서 반환

🔹 즉, 두 반복자 사이에 몇 개의 요소가 있는지 계산

✅ 기본 사용 예시

#include <iostream>
#include <vector>
#include <iterator>

int main() {
std::vector<int> v = {10, 20, 30, 40, 50};

auto it1 = v.begin();
auto it2 = v.begin() + 3;

std::cout << "거리: " << std::distance(it1, it2) << '\n';  // 출력: 3
}

✅ 어떤 컨테이너에서든 사용 가능

• vector, list, deque, set, map 등 모든 반복자 타입에 사용 가능

• 단, 반복자 타입에 따라 성능 차이가 있습니다!

✅ 반복자 타입에 따른 성능

반복자 종류	예시 컨테이너	std::distance 성능
Random Access Iterator	vector, deque, array	✅ O(1) (빠름)
Bidirectional Iterator	list, set, map	❗ O(n) (반복 순회)
Input Iterator	istream_iterator, forward_list	❗ O(n), 단방향 반복

✅ 주의: 거꾸로 거리 구할 때는 음수도 가능

auto it1 = v.begin() + 3;
auto it2 = v.begin();
std::cout << std::distance(it1, it2);  // 출력: -3

단, InputIterator 계열은 음수 거리 계산 불가 → first가 앞에 있어야 함!

✅ 실전 용도 예

1. 중간 위치를 알고 싶을 때

auto mid = v.begin() + std::distance(v.begin(), v.end()) / 2;

2. 범위 길이 확인

if (std::distance(range.begin(), range.end()) > 10)
std::cout << "요소가 10개 이상입니다.\n";

항목	내용
역할	두 반복자 사이의 거리(요소 개수)를 계산
반환값	정수형 difference_type
성능	반복자 종류에 따라 다름 (O(1) ~ O(n))
활용	중간 위치 계산, 범위 검사, 거리 측정 등

✔️ std::distance(first, last)는 반복자 간의 거리를 구하는 가장 범용적인 도구입니다.

✔️ 단, 반복자 종류에 따라 성능에 차이가 있으므로 컨테이너에 맞게 사용해야 해요!

나우히즈

이전 포스트

[VEDA] 12일차

다음 포스트

[VEDA] 13일차

VEDA

12장. STL와 컨테이너와 알고리즘

std::array

vector

push_back() vs emplace_back()

std::list

std::deque

✅ std::deque란?

연관 컨테이너

✅ 1. std::set

✅ 2. std::multiset

✅ 3. std::map

✅ 4. std::multimap

컨테이너 어댑터

✅ std::stack - 후입선출 (LIFO)

✅ std::queue - 선입선출 (FIFO)

✅ 공통점: 컨테이너 어댑터

12-2 알고리즘

✅ `<algorithm>`이란?

✅ `<algorithm>`의 기능 분류

const를 붙여야하는 이유

특별 : std::distance

[VEDA] 12일차

[VEDA] QT programming 1

0개의 댓글

[VEDA] 13일차

VEDA

12장. STL와 컨테이너와 알고리즘

std::array

vector

push_back() vs emplace_back()

std::list

std::deque

✅ std::deque란?

연관 컨테이너

✅ 1. std::set

✅ 2. std::multiset

✅ 3. std::map

✅ 4. std::multimap

컨테이너 어댑터

✅ std::stack - 후입선출 (LIFO)

✅ std::queue - 선입선출 (FIFO)

✅ 공통점: 컨테이너 어댑터

12-2 알고리즘

✅ <algorithm>이란?

✅ <algorithm>의 기능 분류

const를 붙여야하는 이유

특별 : std::distance

[VEDA] 12일차

[VEDA] QT programming 1

0개의 댓글

✅ `<algorithm>`이란?

✅ `<algorithm>`의 기능 분류