STL 컨테이너: vector, list, map 활용법 🚀

C++ 프로그래머라면 STL(Standard Template Library)의 중요성을 잘 알고 계실 겁니다. STL은 C++의 핵심 라이브러리로, 효율적이고 재사용 가능한 컴포넌트들을 제공합니다. 그 중에서도 vector, list, map은 가장 많이 사용되는 컨테이너들입니다. 이 글에서는 이 세 가지 컨테이너의 특징과 활용법에 대해 자세히 알아보겠습니다. 🧐

프로그래밍 세계에서는 효율적인 데이터 관리가 성능의 핵심입니다. 마치 재능넷에서 다양한 재능을 효과적으로 관리하고 연결하는 것처럼, C++에서도 데이터를 잘 다루는 것이 중요하죠. 그래서 오늘은 STL 컨테이너의 활용법을 통해 여러분의 코딩 실력을 한 단계 업그레이드 해보겠습니다! 💪

먼저, 각 컨테이너의 특징을 간단히 살펴보겠습니다:

📌 Vector: 동적 배열, 빠른 임의 접근
📌 List: 이중 연결 리스트, 빠른 삽입과 삭제
📌 Map: 키-값 쌍, 빠른 검색과 정렬된 데이터

이제 각 컨테이너에 대해 자세히 알아보겠습니다. 준비되셨나요? 그럼 시작해볼까요! 🚀

1. Vector: 동적 배열의 강자 💪

Vector는 STL에서 가장 많이 사용되는 컨테이너 중 하나입니다. 동적 배열이라고도 불리는 vector는 크기가 자동으로 조절되는 배열이라고 생각하면 됩니다. 마치 고무줄처럼 늘었다 줄었다 하는 거죠! 😄

1.1 Vector의 특징

연속적인 메모리 할당: 데이터가 메모리상에 연속적으로 저장됩니다.
동적 크기 조절: 필요에 따라 자동으로 크기가 조절됩니다.
빠른 임의 접근: 인덱스를 통한 접근이 O(1) 시간에 가능합니다.
끝에서의 빠른 삽입/삭제: 벡터의 끝에서 요소를 추가하거나 제거하는 것이 매우 빠릅니다.

이러한 특징들 때문에 vector는 많은 상황에서 기본적으로 선택되는 컨테이너입니다. 특히 데이터의 크기를 미리 알 수 없거나, 자주 변경될 수 있는 경우에 유용합니다.

1.2 Vector 사용법

Vector를 사용하기 위해서는 먼저 #include <vector>를 통해 헤더 파일을 포함시켜야 합니다. 그 다음, 다음과 같이 vector를 선언할 수 있습니다:

std::vector<int> numbers;  // 정수를 저장하는 빈 벡터
std::vector<std::string> names(5);  // 5개의 빈 문자열로 초기화된 벡터
std::vector<double> prices = {10.5, 20.3, 30.9};  // 초기값이 있는 벡터

Vector의 주요 멤버 함수들은 다음과 같습니다:

push_back(): 벡터의 끝에 요소를 추가합니다.
pop_back(): 벡터의 마지막 요소를 제거합니다.
size(): 벡터의 현재 크기를 반환합니다.
capacity(): 벡터의 현재 용량을 반환합니다.
empty(): 벡터가 비어있는지 확인합니다.
clear(): 벡터의 모든 요소를 제거합니다.
resize(): 벡터의 크기를 변경합니다.
reserve(): 벡터의 용량을 미리 할당합니다.

이제 간단한 예제를 통해 vector의 사용법을 살펴보겠습니다:

#include <iostream>
#include <vector>
#include <string>

int main() {
    std::vector<std::string> fruits;

    // 요소 추가
    fruits.push_back("Apple");
    fruits.push_back("Banana");
    fruits.push_back("Cherry");

    // 벡터 순회
    for (const auto& fruit : fruits) {
        std::cout << fruit << " ";
    }
    std::cout << std::endl;

    // 크기 확인
    std::cout << "Size: " << fruits.size() << std::endl;

    // 요소 접근
    std::cout << "Second fruit: " << fruits[1] << std::endl;

    // 마지막 요소 제거
    fruits.pop_back();

    // 다시 순회
    for (const auto& fruit : fruits) {
        std::cout << fruit << " ";
    }
    std::cout << std::endl;

    return 0;
}

이 예제에서는 문자열을 저장하는 vector를 생성하고, 요소를 추가, 접근, 제거하는 방법을 보여줍니다. 실행 결과는 다음과 같을 것입니다:

Apple Banana Cherry 
Size: 3
Second fruit: Banana
Apple Banana

1.3 Vector의 성능 고려사항

Vector를 사용할 때는 몇 가지 성능 관련 사항을 고려해야 합니다:

용량 증가: Vector는 용량이 부족할 때마다 새로운 메모리를 할당하고 모든 요소를 복사합니다. 이는 비용이 큰 작업입니다.
중간 삽입/삭제: Vector의 중간에 요소를 삽입하거나 삭제하면 그 뒤의 모든 요소를 이동시켜야 하므로 비효율적입니다.
메모리 사용: Vector는 연속된 메모리를 사용하므로, 큰 데이터를 다룰 때 메모리 단편화 문제가 발생할 수 있습니다.

이러한 문제를 완화하기 위해 다음과 같은 방법을 사용할 수 있습니다:

reserve() 함수를 사용하여 미리 용량을 할당합니다.
중간 삽입/삭제가 빈번하다면 다른 컨테이너(예: list)의 사용을 고려합니다.
메모리 사용이 중요한 경우, 더 작은 단위의 vector들로 나누어 관리하는 것을 고려합니다.

1.4 Vector의 활용 예시

Vector는 다양한 상황에서 유용하게 사용될 수 있습니다. 몇 가지 실제 활용 예시를 살펴보겠습니다:

1.4.1 동적 배열 구현

C++에서 vector는 동적 배열을 쉽게 구현할 수 있게 해줍니다. 예를 들어, 사용자로부터 입력받은 숫자들을 저장하고 처리하는 프로그램을 만들 수 있습니다:

#include <iostream>
#include <vector>
#include <numeric>

int main() {
    std::vector<int> numbers;
    int num;

    std::cout << "Enter numbers (enter -1 to stop):\n";
    while (true) {
        std::cin >> num;
        if (num == -1) break;
        numbers.push_back(num);
    }

    // 합계 계산
    int sum = std::accumulate(numbers.begin(), numbers.end(), 0);

    std::cout << "Sum: " << sum << std::endl;
    std::cout << "Average: " << static_cast<double>(sum) / numbers.size() << std::endl;

    return 0;
}

1.4.2 2D 벡터를 이용한 행렬 표현

Vector를 중첩하여 사용하면 2차원 배열이나 행렬을 쉽게 표현할 수 있습니다:

#include <iostream>
#include <vector>

int main() {
    std::vector<std::vector<int>> matrix = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };

    // 행렬 출력
    for (const auto& row : matrix) {
        for (int num : row) {
            std::cout << num << " ";
        }
        std::cout << std::endl;
    }

    return 0;
}

1.4.3 객체 저장 및 관리

Vector는 사용자 정의 객체를 저장하고 관리하는 데에도 매우 유용합니다. 예를 들어, 재능넷에서 사용자 정보를 관리하는 시스템을 구현한다고 가정해봅시다:

#include <iostream>
#include <vector>
#include <string>

class User {
public:
    User(std::string name, std::string skill) : name(name), skill(skill) {}
    std::string getName() const { return name; }
    std::string getSkill() const { return skill; }
private:
    std::string name;
    std::string skill;
};

int main() {
    std::vector<User> users;

    users.push_back(User("Alice", "Programming"));
    users.push_back(User("Bob", "Design"));
    users.push_back(User("Charlie", "Writing"));

    for (const auto& user : users) {
        std::cout << user.getName() << " - " << user.getSkill() << std::endl;
    }

    return 0;
}

이 예제에서는 User 객체들을 vector에 저장하고 관리합니다. 이런 방식으로 재능넷과 같은 플랫폼에서 사용자 데이터를 효율적으로 관리할 수 있습니다.

1.5 Vector의 고급 기능

Vector는 기본적인 기능 외에도 몇 가지 고급 기능을 제공합니다. 이러한 기능들을 잘 활용하면 더욱 효율적인 프로그래밍이 가능합니다.

1.5.1 벡터의 정렬

STL의 algorithm 라이브러리와 함께 사용하면 vector를 쉽게 정렬할 수 있습니다:

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> numbers = {5, 2, 8, 1, 9};

    std::sort(numbers.begin(), numbers.end());

    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

1.5.2 벡터의 검색

마찬가지로 algorithm 라이브러리를 사용하여 vector에서 특정 요소를 검색할 수 있습니다:

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};

    auto it = std::find(numbers.begin(), numbers.end(), 3);

    if (it != numbers.end()) {
        std::cout << "Found 3 at position: " << std::distance(numbers.begin(), it) << std::endl;
    } else {
        std::cout << "3 not found" << std::endl;
    }

    return 0;
}

1.5.3 벡터의 변환

STL의 transform 알고리즘을 사용하면 vector의 모든 요소에 특정 연산을 적용할 수 있습니다:

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};
    std::vector<int> squared(numbers.size());

    std::transform(numbers.begin(), numbers.end(), squared.begin(),
                   [](int x) { return x * x; });

    for (int num : squared) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

이 예제에서는 lambda 함수를 사용하여 각 요소를 제곱합니다.

1.6 Vector와 메모리 관리

Vector를 효율적으로 사용하기 위해서는 메모리 관리에 대한 이해가 필요합니다. Vector는 동적으로 크기가 조절되지만, 이 과정에서 메모리 재할당이 발생할 수 있습니다.

1.6.1 Capacity vs Size

Vector의 size는 현재 저장된 요소의 수를 나타내며, capacity는 재할당 없이 저장할 수 있는 요소의 최대 수를 나타냅니다. capacity가 부족해지면 vector는 더 큰 메모리 블록을 할당하고 모든 요소를 새 위치로 이동시킵니다.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> numbers;

    std::cout << "Initial size: " << numbers.size() << ", capacity: " << numbers.capacity() << std::endl;

    for (int i = 0; i < 10; ++i) {
        numbers.push_back(i);
        std::cout << "Size: " << numbers.size() << ", capacity: " << numbers.capacity() << std::endl;
    }

    return 0;
}

이 예제를 실행하면 size와 capacity가 어떻게 변하는지 볼 수 있습니다.

1.6.2 reserve() 함수 사용

많은 수의 요소를 추가할 것을 알고 있다면, reserve() 함수를 사용하여 미리 충분한 capacity를 확보할 수 있습니다. 이렇게 하면 불필요한 재할당을 방지할 수 있습니다.

#include <iostream>
#include <vector>
#include <chrono>

int main() {
    const int N = 1000000;

    // reserve() 사용하지 않은 경우
    {
        std::vector<int> v1;
        auto start = std::chrono::high_resolution_clock::now();
        for (int i = 0; i < N; ++i) {
            v1.push_back(i);
        }
        auto end = std::chrono::high_resolution_clock::now();
        std::chrono::duration<double> diff = end - start;
        std::cout << "Without reserve: " << diff.count() << " s" << std::endl;
    }

    // reserve() 사용한 경우
    {
        std::vector<int> v2;
        v2.reserve(N);
        auto start = std::chrono::high_resolution_clock::now();
        for (int i = 0; i < N; ++i) {
            v2.push_back(i);
        }
        auto end = std::chrono::high_resolution_clock::now();
        std::chrono::duration<double> diff = end - start;
        std::cout << "With reserve: " << diff.count() << " s" << std::endl;
    }

    return 0;
}

이 예제는 reserve() 함수 사용 여부에 따른 성능 차이를 보여줍니다.

1.7 Vector의 주의사항

Vector를 사용할 때 주의해야 할 몇 가지 사항이 있습니다:

1.7.1 Iterator Invalidation

Vector의 크기가 변경되면 기존의 iterator들이 무효화될 수 있습니다. 예를 들어:

#include <iostream>
#include <vector>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};
    auto it = numbers.begin() + 2;  // 3을 가리키는 iterator

    numbers.push_back(6);  // 이 작업이 재할당을 trigger할 수 있음
    
    // 위험: it가 이제 유효하지 않을 수 있음
    std::cout << *it << std::endl;  // 미정의 동작

    return 0;
}

1.7.2 범위 검사

Vector의 operator[]는 범위 검사를 수행하지 않습니다. 안전한 접근을 위해서는 at() 함수를 사용하는 것이 좋습니다:

#include <iostream>
#include <vector>

int main() {
    std::vector<int> numbers = {1, 2, 3};

    try {
        std::cout << numbers.at(5) << std::endl;  // 예외 발생
    } catch (const std::out_of_range& e) {
        std::cout << "Error: " << e.what() << std::endl;
    }

    return 0;
}

1.7.3 메모리 누수

Vector 자체는 메모리를 자동으로 관리하지만, vector에 포인터를 저장하는 경우 주의가 필요합니다:

#include <iostream>
#include <vector>

class MyClass {
public:
    MyClass() { std::cout << "MyClass created" << std::endl; }
    ~MyClass() { std::cout << "MyClass destroyed" << std::endl; }
};

int main() {
    std::vector<MyClass*> objects;

    for (int i = 0; i < 3; ++i) {
        objects.push_back(new MyClass());
    }

    // 메모리 누수! 포인터들을 직접 삭제해야 함
    for (auto obj : objects) {
        delete obj;
    }

    return 0;
}

이런 경우, std::unique_ptr나 std::shared_ptr를 사용하는 것이 안전합니다.

1.8 Vector와 다른 컨테이너의 비교

Vector는 많은 상황에서 좋은 선택이지만, 모든 상황에 적합한 것은 아닙니다. 다른 컨테이너와의 비교를 통해 vector의 장단점을 더 잘 이해할 수 있습니다.

1.8.1 Vector vs Array

Vector: 동적 크기, 자동 메모리 관리
Array: 고정 크기, 더 작은 메모리 오버헤드

크기가 고정되어 있고 성능이 중요한 경우에는 array가 더 적합할 수 있습니다.

1.8.2 Vector vs List

Vector: 빠른 임의 접근, 연속된 메모리
List: 빠른 삽입/삭제, 비연속 메모리

중간에 요소를 자주 삽입하거나 삭제해야 하는 경우에는 list가 더 효율적일 수 있습니다.

1.8.3 Vector vs Deque

Vector: 한쪽 끝에서만 효율적인 삽입/삭제
Deque: 양쪽 끝에서 효율적인 삽입/삭제

양쪽 끝에서 요소를 자주 추가하거나 제거해야 하는 경우 deque가 더 적합할 수 있습니다.

1.9 Vector의 실제 응용 사례

Vector는 다양한 실제 상황에서 유용하게 사용됩니다. 몇 가지 응용 사례를 살펴보겠습니다.

1.9.1 그래픽 처리

2D 또는 3D 그래픽 프로그래밍에서 vector는 점, 선, 다각형 등을 표현하는 데 사용될 수 있습니다:

#include <vector>
#include <cmath>

struct Point {
    double x, y;
    Point(double x, double y) : x(x), y(y) {}
};

class Polygon {
private:
    std::vector<Point> vertices;

public:
    void addVertex(const Point& p) {
        vertices.push_back(p);
    }

    double calculateArea() {
        double area = 0.0;
        int j = vertices.size() - 1;
        for (int i = 0; i < vertices.size(); i++) {
            area += (vertices[j].x + vertices[i].x) * (vertices[j].y - vertices[i].y);
            j = i;
        }
        return std::abs(area / 2.0);
    }
};

int main() {
    Polygon triangle;
    triangle.addVertex(Point(0, 0));
    triangle.addVertex(Point(1, 0));
    triangle.addVertex(Point(0, 1));

    double area = triangle.calculateArea();
    // 면적 출력...

    return 0;
}

1.9.2 텍스트 처리

문서나 로그 파일의 라인을 처리할 때 vector를 사용할 수 있습니다:

#include <iostream>
#include <vector>
#include <string>
#include <fstream>

std::vector<std::string> readLines(const std::string& filename) {
    std::vector<std::string> lines;
    std::ifstream file(filename);
    std::string line;

    while (std::getline(file, line)) {
        lines.push_back(line);
    }

    return lines;
}

int main() {
    auto lines = readLines("example.txt");

    for (const auto& line : lines) {
        std::cout << line << std::endl;
    }

    return 0;
}

1.9.3 시뮬레이션

물리 시뮬레이션이나 게임 개발에서 vector는 동적 객체 관리에 유용합니다:

#include <vector>
#include <algorithm>

class GameObject {
public:
    virtual void update() = 0;
    virtual bool isAlive() const = 0;
};

class GameWorld {
private:
    std::vector<GameObject*> objects;

public:
    void addObject(GameObject* obj) {
        objects.push_back(obj);
    }

    void updateAll() {
        for (auto& obj : objects) {
            obj->update();
        }

        // 죽은 객체 제거
        objects.erase(
            std::remove_if(objects.begin(), objects.end(),
                           [](const GameObject* obj) { return !obj->isAlive(); }),
            objects.end());
    }
};

// 사용 예:
// GameWorld world;
// world.addObject(new Player());
// world.addObject(new Enemy());
// world.updateAll();

1.10 Vector의 최적화 기법

Vector를 더욱 효율적으로 사용하기 위한 몇 가지 최적화 기법을 살펴보겠습니다.

1.10.1 Move Semantics 활용

C++11 이상에서는 move semantics를 를 활용하여 불필요한 복사를 줄일 수 있습니다:

#include <vector>
#include <string>

std::vector<std::string> createVector() {
    std::vector<std::string> vec;
    vec.push_back("Hello");
    vec.push_back("World");
    return vec;  // 여기서 move semantics가 자동으로 적용됨
}

int main() {
    std::vector<std::string> myVec = createVector();  // 복사 대신 이동
    return 0;
}

1.10.2 emplace_back() 사용

push_back() 대신 emplace_back()을 사용하면 객체를 직접 vector 내부에서 생성할 수 있어 효율적입니다:

#include <vector>
#include <string>

class MyClass {
public:
    MyClass(int a, std::string b) {}
};

int main() {
    std::vector<MyClass> vec;
    
    // push_back 사용
    vec.push_back(MyClass(1, "test"));
    
    // emplace_back 사용 (더 효율적)
    vec.emplace_back(1, "test");
    
    return 0;
}

1.10.3 Shrink to fit

많은 요소를 제거한 후에는 shrink_to_fit()을 사용하여 불필요한 capacity를 줄일 수 있습니다:

#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec(1000);
    std::cout << "Capacity: " << vec.capacity() << std::endl;

    vec.clear();
    std::cout << "Capacity after clear: " << vec.capacity() << std::endl;

    vec.shrink_to_fit();
    std::cout << "Capacity after shrink_to_fit: " << vec.capacity() << std::endl;

    return 0;
}

1.11 Vector와 알고리즘 라이브러리

STL의 알고리즘 라이브러리와 vector를 함께 사용하면 강력한 기능을 구현할 수 있습니다.

1.11.1 정렬과 검색

#include <vector>
#include <algorithm>
#include <iostream>

int main() {
    std::vector<int> vec = {5, 2, 8, 1, 9};

    // 정렬
    std::sort(vec.begin(), vec.end());

    // 이진 검색
    if (std::binary_search(vec.begin(), vec.end(), 8)) {
        std::cout << "Found 8" << std::endl;
    }

    return 0;
}

1.11.2 범위 기반 알고리즘

#include <vector>
#include <algorithm>
#include <iostream>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};

    // 모든 요소에 2를 곱함
    std::for_each(vec.begin(), vec.end(), [](int &n) { n *= 2; });

    // 최대값 찾기
    auto max = std::max_element(vec.begin(), vec.end());
    std::cout << "Max: " << *max << std::endl;

    return 0;
}

1.12 Vector의 메모리 관리 심화

Vector의 내부 메모리 관리에 대해 더 자세히 알아보겠습니다.

1.12.1 Small String Optimization (SSO)

많은 C++ 구현에서 std::vector<std::string>은 SSO를 활용합니다. 이는 작은 문자열의 경우 동적 할당을 피하고 vector 내부에 직접 저장하는 최적화 기법입니다.

1.12.2 Allocator

Vector는 메모리 할당을 위해 allocator를 사용합니다. 사용자 정의 allocator를 사용하여 메모리 관리를 커스터마이즈할 수 있습니다:

#include <vector>
#include <memory>

template <typename T>
class MyAllocator : public std::allocator<T> {
    // 커스텀 할당 로직
};

int main() {
    std::vector<int, MyAllocator<int>> vec;
    // 사용...
    return 0;
}

1.13 Vector의 성능 분석

Vector의 주요 연산들의 시간 복잡도를 살펴보겠습니다:

임의 접근 (operator[]): O(1)
끝에 요소 추가/제거 (push_back/pop_back): 평균 O(1), 최악의 경우 O(n)
중간에 요소 삽입/제거: O(n)
크기 조회 (size): O(1)
용량 조회 (capacity): O(1)

1.14 Vector와 멀티스레딩

Vector는 기본적으로 thread-safe하지 않습니다. 멀티스레드 환경에서 vector를 안전하게 사용하려면 적절한 동기화 메커니즘이 필요합니다:

#include <vector>
#include <mutex>

class ThreadSafeVector {
private:
    std::vector<int> vec;
    mutable std::mutex mtx;

public:
    void push_back(int value) {
        std::lock_guard<std::mutex> lock(mtx);
        vec.push_back(value);
    }

    int at(size_t index) const {
        std::lock_guard<std::mutex> lock(mtx);
        return vec.at(index);
    }
};

1.15 결론

Vector는 C++ STL에서 가장 널리 사용되는 컨테이너 중 하나입니다. 동적 배열의 편리함과 효율성을 제공하며, 다양한 상황에서 유용하게 활용될 수 있습니다. 그러나 각 상황에 맞는 적절한 컨테이너를 선택하는 것이 중요하며, vector의 특성과 한계를 잘 이해하고 사용해야 합니다.

이제 vector에 대해 깊이 있게 살펴보았습니다. 다음으로 list와 map에 대해 알아보겠습니다.

2. List: 이중 연결 리스트의 강점 💪

List는 STL에서 제공하는 또 다른 중요한 컨테이너입니다. 이중 연결 리스트(doubly linked list)로 구현되어 있어, 특정 상황에서 vector보다 더 효율적일 수 있습니다. 마치 재능넷에서 다양한 재능들이 서로 연결되어 있는 것처럼, list의 요소들도 서로 연결되어 있죠! 😊

2.1 List의 특징

비연속적 메모리 할당: 각 요소가 메모리상에 연속적으로 저장되지 않습니다.
양방향 접근: 각 노드는 이전 노드와 다음 노드에 대한 포인터를 가집니다.
빠른 삽입과 삭제: 어느 위치에서든 O(1) 시간에 요소를 삽입하거나 삭제할 수 있습니다.
느린 임의 접근: 특정 위치의 요소에 접근하려면 처음부터 순회해야 합니다.

2.2 List 사용법

List를 사용하기 위해서는 #include <list>를 통해 헤더 파일을 포함시켜야 합니다. 다음과 같이 list를 선언할 수 있습니다:

std::list<int> numbers;  // 정수를 저장하는 빈 리스트
std::list<std::string> names(5);  // 5개의 빈 문자열로 초기화된 리스트
std::list<double> prices = {10.5, 20.3, 30.9};  // 초기값이 있는 리스트

List의 주요 멤버 함수들은 다음과 같습니다:

push_back(): 리스트의 끝에 요소를 추가합니다.
push_front(): 리스트의 시작에 요소를 추가합니다.
pop_back(): 리스트의 마지막 요소를 제거합니다.
pop_front(): 리스트의 첫 번째 요소를 제거합니다.
insert(): 지정된 위치에 요소를 삽입합니다.
erase(): 지정된 위치의 요소를 제거합니다.
size(): 리스트의 크기를 반환합니다.
empty(): 리스트가 비어있는지 확인합니다.
clear(): 리스트의 모든 요소를 제거합니다.

2.3 List 사용 예제

간단한 예제를 통해 list의 사용법을 살펴보겠습니다:

#include <iostream>
#include <list>
#include <string>

int main() {
    std::list<std::string> fruits;

    // 요소 추가
    fruits.push_back("Apple");
    fruits.push_front("Banana");
    fruits.push_back("Cherry");

    // 리스트 순회
    for (const auto& fruit : fruits) {
        std::cout << fruit << " ";
    }
    std::cout << std::endl;

    // 크기 확인
    std::cout << "Size: " << fruits.size() << std::endl;

    // 첫 번째와 마지막 요소 접근
    std::cout << "First fruit: " << fruits.front() << std::endl;
    std::cout << "Last fruit: " << fruits.back() << std::endl;

    // 중간에 요소 삽입
    auto it = std::next(fruits.begin());
    fruits.insert(it, "Dragonfruit");

    // 요소 제거
    fruits.pop_front();

    // 다시 순회
    for (const auto& fruit : fruits) {
        std::cout << fruit << " ";
    }
    std::cout << std::endl;

    return 0;
}

이 예제에서는 문자열을 저장하는 list를 생성하고, 요소를 추가, 접근, 삽입, 제거하는 방법을 보여줍니다. 실행 결과는 다음과 같을 것입니다:

Banana Apple Cherry 
Size: 3
First fruit: Banana
Last fruit: Cherry
Dragonfruit Apple Cherry

2.4 List vs Vector

List와 vector는 각각 장단점이 있습니다. 상황에 따라 적절한 컨테이너를 선택해야 합니다:

삽입/삭제: List는 어느 위치에서든 O(1) 시간에 삽입/삭제가 가능합니다. Vector는 끝에서의 삽입/삭제는 평균 O(1)이지만, 중간에서는 O(n)입니다.
임의 접근: Vector는 O(1) 시간에 임의 접근이 가능하지만, list는 O(n) 시간이 걸립니다.
메모리 사용: List는 각 요소마다 추가적인 포인터를 저장해야 하므로 더 많은 메모리를 사용합니다.
캐시 효율성: Vector는 연속된 메모리를 사용하므로 캐시 효율성이 높습니다. List는 그렇지 않습니다.

2.5 List의 활용 예시

List는 다양한 상황에서 유용하게 사용될 수 있습니다. 몇 가지 실제 활용 예시를 살펴보겠습니다:

2.5.1 LRU (Least Recently Used) 캐시 구현

LRU 캐시는 가장 오래된 항목을 제거하는 캐싱 알고리즘입니다. List를 사용하면 이를 효율적으로 구현할 수 있습니다:

#include <list>
#include <unordered_map>

class LRUCache {
private:
    int capacity;
    std::list<int> lru_list;
    std::unordered_map<int, std::list<int>::iterator> cache;

public:
    LRUCache(int capacity) : capacity(capacity) {}

    int get(int key) {
        if (cache.find(key) == cache.end()) {
            return -1;
        }
        updateLRU(key);
        return *cache[key];
    }

    void put(int key, int value) {
        if (cache.find(key) != cache.end()) {
            lru_list.erase(cache[key]);
        } else if (lru_list.size() >= capacity) {
            int lru_key = lru_list.back();
            lru_list.pop_back();
            cache.erase(lru_key);
        }
        lru_list.push_front(key);
        cache[key] = lru_list.begin();
    }

private:
    void updateLRU(int key) {
        lru_list.splice(lru_list.begin(), lru_list, cache[key]);
        cache[key] = lru_list.begin();
    }
};

2.5.2 다항식 표현

List를 사용하여 다항식을 표현하고 연산할 수 있습니다:

#include <list>
#include <iostream>

struct Term {
    int coefficient;
    int exponent;
    Term(int c, int e) : coefficient(c), exponent(e) {}
};

class Polynomial {
private:
    std::list<Term> terms;

public:
    void addTerm(int coefficient, int exponent) {
        terms.push_back(Term(coefficient, exponent));
        terms.sort([](const Term& a, const Term& b) {
            return a.exponent > b.exponent;
        });
    }

    void print() {
        for (const auto& term : terms) {
            std::cout << term.coefficient << "x^" << term.exponent << " ";
        }
        std::cout << std::endl;
    }
};

int main() {
    Polynomial poly;
    poly.addTerm(3, 2);
    poly.addTerm(2, 1);
    poly.addTerm(1, 0);
    poly.print();  // 출력: 3x^2 2x^1 1x^0 
    return 0;
}

2.6 List의 고급 기능

List는 몇 가지 고급 기능을 제공합니다. 이러한 기능들을 잘 활용하면 더욱 효율적인 프로그래밍이 가능합니다.

2.6.1 splice()

splice() 함수는 한 리스트의 요소들을 다른 리스트로 이동시킬 때 사용됩니다. 이 연산은 포인터만 조작하므로 매우 효율적입니다:

#include <iostream>
#include <list>

int main() {
    std::list<int> list1 = {1, 2, 3};
    std::list<int> list2 = {4, 5, 6};

    // list2의 모든 요소를 list1의 두 번째 위치로 이동
    list1.splice(std::next(list1.begin()), list2);

    for (int n : list1) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    return 0;
}

2.6.2 merge()

merge() 함수는 두 개의 정렬된 리스트를 하나의 정렬된 리스트로 병합합니다:

#include <iostream>
#include <list>

int main() {
    std::list<int> list1 = {1, 3, 5};
    std::list<int> list2 = {2, 4, 6};

    list1.merge(list2);

    for (int n : list1) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    return 0;
}

2.6.3 unique()

unique() 함수는 연속된 중복 요소를 제거합니다:

#include <iostream>
#include <list>

int main() {
    std::list<int> numbers = {1, 2, 2, 3, 3, 3, 4, 5, 5};

    numbers.unique();

    for (int n : numbers) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    return 0;
}

2.7 List와 알고리즘

STL의 알고리즘 라이브러리와 list를 함께 사용할 때 주의해야 할 점이 있습니다. List는 양방향 반복자(bidirectional iterator)를 제공하지만, 임의 접근 반복자(random access iterator)는 제공하지 않습니다. 따라서 일부 알고리즘은 list와 함께 사용할 수 없거나 비효율적일 수 있습니다.

예를 들어, std::sort()는 list와 직접 사용할 수 없습니다. 대신 list의 멤버 함수인 sort()를 사용해야 합니다:

#include <iostream>
#include <list>
#include <algorithm>

int main() {
    std::list<int> numbers = {5, 2, 8, 1, 9};

    // 이렇게 하면 컴파일 에러 발생
    // std::sort(numbers.begin(), numbers.end());

    // 대신 이렇게 사용
    numbers.sort();

    for (int n : numbers) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    return 0;
}

2.8 List의 성능 고려사항

List를 사용할 때는 몇 가지 성능 관련 사항을 고려해야 합니다:

메모리 사용: List는 각 요소마다 두 개의 포인터(이전 노드와 다음 노드를 가리키는)를 추가로 저장해야 하므로, vector에 비해 더 많은 메모리를 사용합니다.
캐시 효율성: List의 요소들은 메모리상에 연속적으로 저장되지 않기 때문에, 캐시 효율성이 떨어질 수 있습니다.
순회 성능: List를 순회할 때는 포인터를 따라가야 하므로, vector에 비해 성능이 떨어질 수 있습니다.

따라서 다음과 같은 상황에서 list 사용을 고려해볼 수 있습니다:

요소의 삽입과 삭제가 빈번하게 일어나는 경우
요소의 개수가 자주 변하는 경우
요소들의 순서를 자주 변경해야 하는 경우

2.9 List와 메모리 관리

List는 각 요소를 동적으로 할당하기 때문에, 메모리 관리에 주의를 기울여야 합니다. 특히 사용자 정의 타입을 저장하는 경우, 메모리 누수를 방지하기 위해 적절한 소멸자를 정의해야 합니다.

또한, list의 요소로 포인터를 저장하는 경우, 해당 포인터가 가리키는 객체의 수명 관리에 주의해야 합니다. 스마트 포인터를 사용하면 이러한 문제를 쉽게 해결할 수 있습니다:

#include <list>
#include <memory>

class MyClass {
    // ...
};

int main() {
    std::list<std::unique_ptr<MyClass>> myList;

    myList.push_back(std::make_unique<MyClass>());
    myList.push_back(std::make_unique<MyClass>());

    // 리스트가 소멸될 때 자동으로 모든 MyClass 객체들이 삭제됩니다.
    return 0;
}

2.10 List의 실제 응용 사례

List는 다양한 실제 상황에서 유용하게 사용됩니다. 몇 가지 응용 사례를 더 살펴보겠습니다.

2.10.1 작업 스케줄러

작업 스케줄러를 구현할 때 list를 사용할 수 있습니다. 새로운 작업을 쉽게 추가하고, 완료된 작업을 효율적으로 제거할 수 있습니다:

#include <list>
#include <string>
#include <iostream>

struct Task {
    std::string name;
    int priority;
    Task(std::string n, int p) : name(n), priority(p) {}
};

class Scheduler {
private:
    std::list<Task> tasks;

public:
    void addTask(const std::string& name, int priority) {
        tasks.push_back(Task(name, priority));
        tasks.sort([](const Task& a, const Task& b) {
            return a.priority > b.priority;
        });
    }

    void executeNextTask() {
        if (!tasks.empty()) {
            std::cout << "Executing task: " << tasks.front().name << std::endl;
            tasks.pop_front();
        }
    }
};

int main() {
    Scheduler scheduler;
    scheduler.addTask("Task 1", 2);
    scheduler.addTask("Task 2", 1);
    scheduler.addTask("Task 3", 3);

    scheduler.executeNextTask();  // Executes "Task 3"
    scheduler.executeNextTask();  // Executes "Task 1"

    return 0;
}

2.10.2 텍스트 편집기의 실행 취소 기능

텍스트 편집기의 실행 취소(undo) 기능을 구현할 때 list를 사용할 수 있습니다:

#include <list>
#include <string>
#include <iostream>

class TextEditor {
private:
    std::string text;
    std::list<std::string> history;
    std::list<std::string>::iterator current;

public:
    TextEditor() {
        history.push_back("");
        current = history.begin();
    }

    void write(const std::string& newText) {
        text += newText;
        history.push_back(text);
        current = std::prev(history.end());
    }

    void undo() {
        if (current != history.begin()) {
            --current;
            text = *current;
        }
    }

    void redo() {
        if (std::next(current) != history.end()) {
            ++current;
            text = *current;
        }
    }

    void print() {
        std::cout << "Current text: " << text << std::endl;
    }
};

int main() {
    TextEditor editor;
    editor.write("Hello ");
    editor.write("world!");
    editor.print();  // Output: Hello world!

    editor.undo();
    editor.print();  // Output: Hello

    editor.redo();
    editor.print();  // Output: Hello world!

    return 0;
}

2.11 List의 최적화 기법

List를 더욱 효율적으로 사용하기 위한 몇 가지 최적화 기법을 살펴보겠습니다.

2.11.1 노드 재사용

요소를 자주 추가하고 제거하는 경우, 노드를 재사용하면 메모리 할당과 해제의 오버헤드를 줄일 수 있습니다:

#include <list>
#include <vector>

class NodePool {
private:
    std::vector<std::list&lt  int>::node_type*> pool;

public:
    std::list<int>::node_type* allocate() {
        if (pool.empty()) {
            return new std::list<int>::node_type();
        } else {
            auto node = pool.back();
            pool.pop_back();
            return node;
        }
    }

    void deallocate(std::list<int>::node_type* node) {
        pool.push_back(node);
    }

    ~NodePool() {
        for (auto node : pool) {
            delete node;
        }
    }
};

// 사용 예:
// NodePool pool;
// std::list<int, std::allocator<int>, NodePool> myList(pool);

2.11.2 캐시 친화적인 리스트

List의 캐시 효율성을 높이기 위해, 노드들을 연속된 메모리 블록에 할당할 수 있습니다:

#include <list>
#include <vector>

template <typename T, size_t BlockSize = 4096>
class CacheFriendlyAllocator {
private:
    std::vector<std::vector<T>> blocks;

public:
    T* allocate() {
        if (blocks.empty() || blocks.back().size() == BlockSize) {
            blocks.emplace_back();
            blocks.back().reserve(BlockSize);
        }
        blocks.back().emplace_back();
        return &blocks.back().back();
    }

    void deallocate(T* ptr) {
        // 실제 구현에서는 ptr을 재사용 가능한 상태로 표시
    }
};

// 사용 예:
// std::list<int, CacheFriendlyAllocator<std::list<int>::node_type>> myList;

2.12 List와 멀티스레딩

List도 vector와 마찬가지로 기본적으로 thread-safe하지 않습니다. 멀티스레드 환경에서 list를 안전하게 사용하려면 적절한 동기화 메커니즘이 필요합니다:

#include <list>
#include <mutex>

template <typename T>
class ThreadSafeList {
private:
    std::list<T> list;
    mutable std::mutex mtx;

public:
    void push_back(const T& value) {
        std::lock_guard<std::mutex> lock(mtx);
        list.push_back(value);
    }

    void pop_front() {
        std::lock_guard<std::mutex> lock(mtx);
        if (!list.empty()) {
            list.pop_front();
        }
    }

    T front() const {
        std::lock_guard<std::mutex> lock(mtx);
        return list.front();
    }

    bool empty() const {
        std::lock_guard<std::mutex> lock(mtx);
        return list.empty();
    }
};

2.13 결론

List는 STL에서 제공하는 강력한 컨테이너 중 하나입니다. 빠른 삽입과 삭제 연산을 제공하며, 요소들의 순서를 쉽게 변경할 수 있습니다. 그러나 임의 접근이 느리고 메모리 사용량이 많다는 단점도 있습니다.

List는 다음과 같은 상황에서 특히 유용합니다:

요소의 삽입과 삭제가 빈번한 경우
요소들의 순서를 자주 변경해야 하는 경우
임의 접근이 필요 없는 경우

하지만 각 상황에 맞는 적절한 컨테이너를 선택하는 것이 중요하며, list의 특성과 한계를 잘 이해하고 사용해야 합니다.

이제 list에 대해 깊이 있게 살펴보았습니다. 다음으로 map에 대해 알아보겠습니다.

3. Map: 키-값 쌍의 효율적인 관리 🗝️

Map은 STL에서 제공하는 연관 컨테이너(associative container)입니다. 키-값 쌍을 저장하고 관리하는 데 특화되어 있어, 데이터를 효율적으로 검색하고 관리할 수 있습니다. 마치 재능넷에서 각 사용자의 ID(키)와 그에 해당하는 프로필 정보(값)를 관리하는 것과 유사하죠! 😊

3.1 Map의 특징

키-값 쌍 저장: 각 요소는 키와 값의 쌍으로 구성됩니다.
자동 정렬: 요소들은 키를 기준으로 자동으로 정렬됩니다.
고유한 키: 각 키는 map 내에서 유일해야 합니다.
빠른 검색: 키를 이용한 검색이 매우 빠릅니다(일반적으로 O(log n) 시간 복잡도).
레드-블랙 트리: 대부분의 구현에서 레드-블랙 트리를 사용하여 구현됩니다.

3.2 Map 사용법

Map을 사용하기 위해서는 #include <map>를 통해 헤더 파일을 포함시켜야 합니다. 다음과 같이 map을 선언할 수 있습니다:

std::map<std::string, int> ages;  // 문자열 키와 정수 값을 가지는 map
std::map<int, std::string> names = {{1, "Alice"}, {2, "Bob"}};  // 초기값이 있는 map

Map의 주요 멤버 함수들은 다음과 같습니다:

insert(): 키-값 쌍을 삽입합니다.
erase(): 주어진 키에 해당하는 요소를 제거합니다.
find(): 주어진 키를 가진 요소를 찾습니다.
at(): 주어진 키에 해당하는 값에 접근합니다(범위 검사 포함).
operator[]: 주어진 키에 해당하는 값에 접근합니다(키가 없으면 새로 생성).
size(): map의 크기를 반환합니다.
empty(): map이 비어있는지 확인합니다.
clear(): map의 모든 요소를 제거합니다.

3.3 Map 사용 예제

간단한 예제를 통해 map의 사용법을 살펴보겠습니다:

#include <iostream>
#include <map>
#include <string>

int main() {
    std::map<std::string, int> ages;

    // 요소 삽입
    ages["Alice"] = 30;
    ages.insert({"Bob", 25});
    ages.insert(std::make_pair("Charlie", 35));

    // 요소 접근
    std::cout << "Alice's age: " << ages["Alice"] << std::endl;
    std::cout << "Bob's age: " << ages.at("Bob") << std::endl;

    // 요소 검색
    if (ages.find("David") != ages.end()) {
        std::cout << "David's age: " << ages["David"] << std::endl;
    } else {
        std::cout << "David not found" << std::endl;
    }

    // map 순회
    for (const auto& pair : ages) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    // 요소 제거
    ages.erase("Bob");

    // 크기 확인
    std::cout << "Size: " << ages.size() << std::endl;

    return 0;
}

이 예제에서는 문자열을 키로, 정수를 값으로 가지는 map을 생성하고, 요소를 추가, 접근, 검색, 제거하는 방법을 보여줍니다. 실행 결과는 다음과 같을 것입니다:

Alice's age: 30
Bob's age: 25
David not found
Alice: 30
Bob: 25
Charlie: 35
Size: 2

3.4 Map vs Unordered_map

C++에서는 std::map 외에도 std::unordered_map이라는 컨테이너를 제공합니다. 두 컨테이너의 주요 차이점은 다음과 같습니다:

내부 구현: map은 보통 레드-블랙 트리로 구현되고, unordered_map은 해시 테이블로 구현됩니다.
정렬: map은 키를 기준으로 자동 정렬되지만, unordered_map은 정렬되지 않습니다.
검색 시간: map은 O(log n), unordered_map은 평균적으로 O(1)의 검색 시간을 가집니다.
메모리 사용: unordered_map이 일반적으로 더 많은 메모리를 사용합니다.

상황에 따라 적절한 컨테이너를 선택해야 합니다:

키의 순서가 중요하거나, 정렬된 순서로 순회해야 할 경우: map
빠른 검색이 가장 중요한 경우: unordered_map

3.5 Map의 활용 예시

Map은 다양한 상황에서 유용하게 사용될 수 있습니다. 몇 가지 실제 활용 예시를 살펴보겠습니다:

3.5.1 단어 빈도수 계산

텍스트에서 각 단어의 등장 빈도를 계산하는 데 map을 사용할 수 있습니다:

#include <iostream>
#include <map>
#include <string>
#include <sstream>

int main() {
    std::string text = "the quick brown fox jumps over the lazy dog";
    std::map<std::string, int> wordFrequency;

    std::istringstream iss(text);
    std::string word;
    while (iss >> word) {
        ++wordFrequency[word];
    }

    for (const auto& pair : wordFrequency) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

3.5.2 캐시 구현

Map을 사용하여 간단한 캐시를 구현할 수 있습니다:

#include <iostream>
#include <map>
#include <string>

class Cache {
private:
    std::map<std::string, std::string> cache;
    size_t capacity;

public:
    Cache(size_t cap) : capacity(cap) {}

    void put(const std::string& key, const std::string& value) {
        if (cache.size() >= capacity && cache.find(key) == cache.end()) {
            // 가장 오래된 항목(첫 번째 항목) 제거
            cache.erase(cache.begin());
        }
        cache[key] = value;
    }

    std::string get(const std::string& key) {
        auto it = cache.find(key);
        if (it != cache.end()) {
            return it->second;
        }
        return "Not found";
    }
};

int main() {
    Cache cache(3);

    cache.put("key1", "value1");
    cache.put("key2", "value2");
    cache.put("key3", "value3");

    std::cout << cache.get("key1") << std::endl;  // value1

    cache.put("key4", "value4");  // key1 제거됨

    std::cout << cache.get("key1") << std::endl;  // Not found

    return 0;
}

3.6 Map의 고급 기능

Map은 몇 가지 고급 기능을 제공합니다. 이러한 기능들을 잘 활용하면 더욱 효율적인 프로그래밍이 가능합니다.

3.6.1 lower_bound()와 upper_bound()

이 함수들은 주어진 키에 대한 하한과 상한을 찾는 데 사용됩니다:

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> m = {{1, "one"}, {3, "three"}, {5, "five"}};

    auto lower = m.lower_bound(2);
    auto upper = m.upper_bound(3);

    std::cout << "lower_bound(2): " << lower->first << std::endl;  // 3
    std::cout << "upper_bound(3): " << upper->first << std::endl;  // 5

    return 0;
}

3.6.2 equal_range()

equal_range() 함수는 주어진 키에 대한 하한과 상한을 한 번에 반환합니다:

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> m = {{1, "one"}, {3, "three"}, {5, "five"}};

    auto range = m.equal_range(3);

    std::cout << "Lower bound: " << range.first->first << std::endl;
    std::cout << "Upper bound: " << range.second->first << std::endl;

    return 0;
}

3.6.3 emplace()

emplace() 함수를 사용하면 요소를 더 효율적으로 삽입할 수 있습니다:

#include <iostream>
#include <map>
#include <string>

int main() {
    std::map<int, std::string> m;

    // insert() 사용
    m.insert(std::make_pair(1, "one"));

    // emplace() 사용
    m.emplace(2, "two");

    for (const auto& pair : m) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

3.7 Map과 사용자 정의 타입

Map의 키로 사용자 정의 타입을 사용할 때는 주의가 필요합니다. 키 타입에 대해 "less than" 연산자(<)를 정의해야 합니다:

#include <iostream>
#include <map>
#include <string>

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

    bool operator<(const Person& other) const {
        return age < other.age;
    }
};

int main() {
    std::map<Person, std::string> personMap;

    personMap[{"Alice", 30}] = "Engineer";
    personMap[{"Bob", 25}] = "Designer";

    for (const auto& pair : personMap) {
        std::cout << pair.first.name << " (" << pair.first.age << "): " 
                  << pair.second << std::endl;
    }

    return 0;
}

3.8 Map의 성능 고려사항

Map을 사용할 때는 몇 가지 성능 관련 사항을 고려해야 합니다:

삽입과 검색 시간: Map의 삽입과 검색 연산은 O(log n) 시간 복잡도를 가집니다.
메모리 사용: Map은 각 노드에 대해 추가적인 메모리를 사용합니다(색상 정보, 부모/자식 포인터 등).
정렬 오버헤드: Map은 항상 정렬된 상태를 유지해야 하므로, 삽입 시 추가적인 오버헤드가 있습니다.

따라서 다음과 같은 상황에서 map 사용을 고려해볼 수 있습니다:

키-값 쌍을 효율적으로 저장하고 검색해야 하는 경우
요소들이 키를 기준으로 정렬되어 있어야 하는 경우
중복된 키를 허용하지 않아야 하는 경우

3.9 Map과 멀티스레딩

Map도 다른 STL 컨테이너와 마찬가지로 기본적으로 thread-safe하지 않습니다. 멀티스레드 환경에서 map을 안전하게 사용하려면 적절한 동기화 메커니즘이 필요합니다:

#include <map>
#include <mutex>
#include <shared_mutex>

template <typename Key, typename Value>
class ThreadSafeMap {
private:
    std::map<Key, Value> m;
    mutable std::shared_mutex mtx;

public:
    void insert(const Key& key, const Value& value) {
        std::unique_lock lock(mtx);
        m[key] = value;
    }

    bool find(const Key& key, Value& value) const {
        std::shared_lock lock(mtx);
        auto it = m.find(key);
        if (it != m.end()) {
            value = it->second;
            return true;
        }
        return false;
    }

    void erase(const Key& key) {
        std::unique_lock lock(mtx);
        m.erase(key);
    }
};

3.10 Map의 실제 응용 사례

Map은 다양한 실제 상황에서 유용하게 사용됩니다. 몇 가지 응용 사례를 더 살펴보겠습니다.

3.10.1 설정 관리

애플리케이션의 설정을 관리할 때 map을 사용할 수 있습니다:

#include <iostream>
#include <map>
#include <string>

class ConfigManager {
private:
    std::map<std::string, std::string> settings;

public:
    void setSetting(const std::string& key, const std::string& value) {
        settings[key] = value;
    }

    std::string getSetting(const std::string& key, const std::string& defaultValue = "") const {
        auto it = settings.find(key);
        if (it != settings.end()) {
            return it->second;
        }
        return defaultValue;
    }

    void loadFromFile(const std::string& filename) {
        // 파일에서 설정을 읽어 map에 저장하는 로직
    }

    void saveToFile(const std::string& filename) const {
        // map의 설정을 파일에 저장하는 로직
    }
};

int main() {
    ConfigManager config;
    config.setSetting("language", "ko");
    config.setSetting("theme", "dark");

    std::cout << "Language: " << config.getSetting("language") << std::endl;
    std::cout << "Font size: " << config.getSetting("font_size", "12") << std::endl;

    return 0;
}

3.10.2 그래프 표현

Map을 사용하여 그래프를 표현할 수 있습니다:

#include <iostream>
#include <map>
#include <vector>
#include <queue>

class Graph {
private:
    std::map<int, std::vector<int>> adjacencyList;

public:
    void addEdge(int from, int to) {
        adjacencyList[from].push_back(to);
    }

    void BFS(int start) {
        std::queue<int> q;
        std::map<int, bool> visited;

        q.push(start);
        visited[start] = true;

        while (!q.empty()) {
            int current = q.front();
            q.pop();

            std::cout << current << " ";

            for (int neighbor : adjacencyList[current]) {
                if (!visited[neighbor]) {
                    q.push(neighbor);
                    visited[neighbor] = true;
                }
            }
        }
    }
};

int main() {
    Graph g;
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 3);

    std::cout << "BFS starting from vertex 2: ";
    g.BFS(2);
    std::cout << std::endl;

    return 0;
}

3.11 Map의 최적화 기법

Map을 더욱 효율적으로 사용하기 위한 몇 가지 최적화 기법을 살펴보겠습니다.

3.11.1 reserve() 함수 사용

C++11부터 std::map에는 reserve() 함수가 없지만, 일부 구현에서는 이를 제공합니다. 이 함수를 사용하면 재할당 횟수를 줄일 수 있습니다:

#include <map>

int main() {
    std::map<int, std::string> m;
    
    // 일부 구현에서 지원
    // m.reserve(1000);

    // 대신 이렇게 할 수 있습니다
    for (int i = 0; i < 1000; ++i) {
        m.emplace_hint(m.end(), i, std::to_string(i));
    }

    return 0;
}

3.11.2 emplace_hint() 사용

emplace_hint() 함수를 사용하면 삽입 위치에 대한 힌트를 제공하여 삽입 성능을 향상시킬 수 있습니다:

#include <map>
#include <string>

int main() {
    std::map<int, std::string> m;

    auto hint = m.end();
    for (int i = 0; i < 1000; ++i) {
        hint = m.emplace_hint(hint, i, std::to_string(i));
    }

    return 0;
}

3.12 Map과 메모리 관리

Map은 동적으로 메모리를 할당하므로, 메모리 관리에 주의를 기울여야 합니다. 특히 map의 값으로 포인터를 저장하는 경우, 해당 포인터가 가리키는 객체의 수명 관리에 주의해야 합니다.

스마트 포인터를 사용하면 이러한 문제를 쉽게 해결할 수 있습니다:

#include <map>
#include <memory>
#include <string>

class Resource {
    // 리소스 클래스 정의
};

int main() {
    std::map<std::string, std::unique_ptr<Resource>> resourceMap;

    resourceMap["resource1"] = std::make_unique<Resource>();
    resourceMap["resource2"] = std::make_unique<Resource>();

    // map이 소멸될 때 자동으로 모든 Resource 객체들이 삭제됩니다.
    return 0;
}

3.13 결론

Map은 STL에서 제공하는 강력한 연관 컨테이너입니다. 키-값 쌍을 효율적으로 저장하고 검색할 수 있으며, 키를 기준으로 자동으로 정렬됩니다. 그러나 삽입과 검색 연산의 시간 복잡도가 O(log n)이라는 점과 추가적인 메모리 사용에 주의해야 합니다.

Map은 다음과 같은 상황에서 특히 유용합니다:

키-값 쌍을 저장하고 빠르게 검색해야 하는 경우
데이터가 키를 기준으로 정렬되어 있어야 하는 경우
중복된 키를 허용하지 않아야 하는 경우

하지만 각 상황에 맞는 적절한 컨테이너를 선택하는 것이 중요하며, map의 특성과 한계를 잘 이해하고 사용해야 합니다.

이제 우리는 STL의 주요 컨테이너인 vector, list, map에 대해 깊이 있 게 살펴보았습니다. 이 세 가지 컨테이너는 각각 고유한 특성과 장단점을 가지고 있으며, 적절한 상황에서 사용될 때 최고의 성능을 발휘합니다.

4. 컨테이너 선택 가이드

적절한 컨테이너를 선택하는 것은 효율적인 프로그램 설계의 핵심입니다. 다음은 각 컨테이너를 선택할 때 고려해야 할 주요 사항들입니다:

4.1 Vector를 선택해야 할 때

데이터의 빠른 순차적 접근이 필요할 때
데이터의 크기가 자주 변하지 않을 때
임의 접근(random access)이 필요할 때
메모리 효율성이 중요할 때

4.2 List를 선택해야 할 때

데이터의 삽입과 삭제가 빈번할 때
데이터의 순서를 자주 변경해야 할 때
임의 접근이 필요 없을 때

4.3 Map을 선택해야 할 때

키-값 쌍으로 데이터를 저장해야 할 때
키를 기준으로 빠른 검색이 필요할 때
데이터가 키를 기준으로 정렬되어 있어야 할 때

5. 성능 비교

세 컨테이너의 주요 연산에 대한 시간 복잡도를 비교해보겠습니다:

연산	Vector	List	Map
임의 접근	O(1)	O(n)	O(log n)
끝에 삽입	평균 O(1)	O(1)	O(log n)
중간에 삽입	O(n)	O(1)	O(log n)
검색	O(n)	O(n)	O(log n)

6. 실제 사용 시나리오

이제 실제 프로그래밍 시나리오에서 각 컨테이너를 어떻게 활용할 수 있는지 살펴보겠습니다.

6.1 재능넷 사용자 관리 시스템

재능넷과 같은 플랫폼에서 사용자 관리 시스템을 구현한다고 가정해봅시다.

#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <string>

struct User {
    int id;
    std::string name;
    std::string skill;
};

class TalentNetSystem {
private:
    std::vector<User> allUsers;  // 모든 사용자 정보
    std::list<int> activeUsers;  // 현재 활성 사용자 ID
    std::map<std::string, std::vector<int>> skillMap;  // 스킬별 사용자 ID

public:
    void addUser(const User& user) {
        allUsers.push_back(user);
        activeUsers.push_back(user.id);
        skillMap[user.skill].push_back(user.id);
    }

    void removeUser(int userId) {
        // vector에서 사용자 제거 (실제로는 더 효율적인 방법 사용 필요)
        allUsers.erase(std::remove_if(allUsers.begin(), allUsers.end(),
            [userId](const User& u) { return u.id == userId; }), allUsers.end());

        // list에서 활성 사용자 ID 제거
        activeUsers.remove(userId);

        // map에서 사용자 ID 제거 (실제로는 더 효율적인 방법 사용 필요)
        for (auto& pair : skillMap) {
            auto& vec = pair.second;
            vec.erase(std::remove(vec.begin(), vec.end(), userId), vec.end());
        }
    }

    std::vector<User> getUsersBySkill(const std::string& skill) {
        std::vector<User> result;
        auto it = skillMap.find(skill);
        if (it != skillMap.end()) {
            for (int id : it->second) {
                auto userIt = std::find_if(allUsers.begin(), allUsers.end(),
                    [id](const User& u) { return u.id == id; });
                if (userIt != allUsers.end()) {
                    result.push_back(*userIt);
                }
            }
        }
        return result;
    }

    void printActiveUsers() {
        for (int id : activeUsers) {
            auto it = std::find_if(allUsers.begin(), allUsers.end(),
                [id](const User& u) { return u.id == id; });
            if (it != allUsers.end()) {
                std::cout << it->name << " (" << it->skill << ")" << std::endl;
            }
        }
    }
};

int main() {
    TalentNetSystem system;

    system.addUser({1, "Alice", "Programming"});
    system.addUser({2, "Bob", "Design"});
    system.addUser({3, "Charlie", "Programming"});

    std::cout << "Active users:" << std::endl;
    system.printActiveUsers();

    std::cout << "\nProgrammers:" << std::endl;
    auto programmers = system.getUsersBySkill("Programming");
    for (const auto& user : programmers) {
        std::cout << user.name << std::endl;
    }

    system.removeUser(2);

    std::cout << "\nActive users after removing Bob:" << std::endl;
    system.printActiveUsers();

    return 0;
}

이 예제에서: