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를 사용할 때는 몇 가지 성능 관련 사항을 고려해야 합니다:

1. 용량 증가: Vector는 용량이 부족할 때마다 새로운 메모리를 할당하고 모든 요소를 복사합니다. 이는 비용이 큰 작업입니다.
2. 중간 삽입/삭제: Vector의 중간에 요소를 삽입하거나 삭제하면 그 뒤의 모든 요소를 이동시켜야 하므로 비효율적입니다.
3. 메모리 사용: 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를 사용할 때는 몇 가지 성능 관련 사항을 고려해야 합니다:

1. 메모리 사용: List는 각 요소마다 두 개의 포인터(이전 노드와 다음 노드를 가리키는)를 추가로 저장해야 하므로, vector에 비해 더 많은 메모리를 사용합니다.
2. 캐시 효율성: List의 요소들은 메모리상에 연속적으로 저장되지 않기 때문에, 캐시 효율성이 떨어질 수 있습니다.
3. 순회 성능: 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에 대해 알아보겠습니다.