#include <iostream>
#include <vector>
#include <list>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>

using namespace std;

// 打印容器内容的通用函数（使用迭代器）
template<typename Container>
void printContainer(const string& name, const Container& c) {
    cout << name << ": ";
    for (auto it = c.begin(); it != c.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

// 针对map的打印特化版本
template<typename Key, typename Value>
void printContainer(const string& name, const map<Key, Value>& m) {
    cout << name << ": ";
    for (auto it = m.begin(); it != m.end(); ++it) {
        cout << "(" << it->first << ":" << it->second << ") ";
    }
    cout << endl;
}

// 针对unordered_map的打印特化版本
template<typename Key, typename Value>
void printContainer(const string& name, const unordered_map<Key, Value>& m) {
    cout << name << ": ";
    for (auto it = m.begin(); it != m.end(); ++it) {
        cout << "(" << it->first << ":" << it->second << ") ";
    }
    cout << endl;
}

int main() {
    cout << "=== STL 容器与迭代器示例 ===" << endl << endl;
    
    // 1. 序列容器示例
    cout << "1. 序列容器" << endl;
    
    // vector - 动态数组
    vector<int> vec = {5, 2, 8, 1, 9};
    vec.push_back(7); // 在末尾添加元素
    printContainer("vector", vec);
    cout << "vector 大小: " << vec.size() << ", 容量: " << vec.capacity() << endl;
    
    // list - 双向链表
    list<int> lst = {5, 2, 8, 1, 9};
    lst.push_front(0); // 在开头添加元素
    lst.sort(); // 链表有自己的sort方法
    printContainer("list", lst);
    
    // deque - 双端队列
    deque<int> dq = {5, 2, 8, 1, 9};
    dq.push_front(0);
    dq.push_back(7);
    printContainer("deque", dq);
    
    cout << endl;
    
    // 2. 关联容器示例
    cout << "2. 关联容器" << endl;
    
    // set - 有序唯一集合
    set<int> s = {5, 2, 8, 1, 9, 2, 5}; // 重复元素会被忽略
    s.insert(3);
    printContainer("set", s);
    
    // map - 键值对映射
    map<string, int> m = {
        {"Alice", 25},
        {"Bob", 30},
        {"Charlie", 35}
    };
    m["David"] = 28; // 添加新元素
    printContainer("map", m);
    
    // multiset - 允许重复键的集合
    multiset<int> ms = {5, 2, 8, 1, 9, 2, 5};
    printContainer("multiset", ms);
    
    cout << endl;
    
    // 3. 无序关联容器示例 (C++11)
    cout << "3. 无序关联容器 (哈希表)" << endl;
    
    // unordered_set - 哈希集合
    unordered_set<int> us = {5, 2, 8, 1, 9, 2, 5};
    printContainer("unordered_set", us);
    
    // unordered_map - 哈希映射
    unordered_map<string, int> um = {
        {"Alice", 25},
        {"Bob", 30},
        {"Charlie", 35}
    };
    printContainer("unordered_map", um);
    
    cout << endl;
    
    // 4. 容器适配器示例
    cout << "4. 容器适配器" << endl;
    
    // stack - 后进先出
    stack<int> st;
    for (int n : {1, 2, 3, 4, 5}) {
        st.push(n);
    }
    cout << "stack: ";
    while (!st.empty()) {
        cout << st.top() << " ";
        st.pop();
    }
    cout << endl;
    
    // queue - 先进先出
    queue<int> q;
    for (int n : {1, 2, 3, 4, 5}) {
        q.push(n);
    }
    cout << "queue: ";
    while (!q.empty()) {
        cout << q.front() << " ";
        q.pop();
    }
    cout << endl;
    
    // priority_queue - 优先级队列（默认最大堆）
    priority_queue<int> pq;
    for (int n : {5, 2, 8, 1, 9}) {
        pq.push(n);
    }
    cout << "priority_queue: ";
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << endl;
    
    cout << endl;
    
    // 5. 迭代器示例
    cout << "5. 迭代器使用示例" << endl;
    
    vector<int> numbers = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    
    // 使用迭代器遍历
    cout << "使用迭代器遍历: ";
    for (auto it = numbers.begin(); it != numbers.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
    
    // 使用反向迭代器
    cout << "使用反向迭代器: ";
    for (auto rit = numbers.rbegin(); rit != numbers.rend(); ++rit) {
        cout << *rit << " ";
    }
    cout << endl;
    
    // 使用迭代器和算法
    auto min_it = min_element(numbers.begin(), numbers.end());
    auto max_it = max_element(numbers.begin(), numbers.end());
    cout << "最小值: " << *min_it << ", 最大值: " << *max_it << endl;
    
    // 使用迭代器插入元素
    auto insert_it = numbers.begin();
    advance(insert_it, 3); // 将迭代器前进3个位置
    numbers.insert(insert_it, 99);
    cout << "在位置3插入99后: ";
    printContainer("numbers", numbers);
    
    // 使用迭代器删除元素
    auto remove_it = numbers.begin();
    advance(remove_it, 5); // 将迭代器前进5个位置
    numbers.erase(remove_it);
    cout << "删除位置5的元素后: ";
    printContainer("numbers", numbers);
    
    // 使用迭代器范围排序
    sort(numbers.begin(), numbers.end());
    cout << "排序后: ";
    printContainer("numbers", numbers);
    
    // 使用const迭代器（只读访问）
    cout << "使用const迭代器: ";
    for (auto cit = numbers.cbegin(); cit != numbers.cend(); ++cit) {
        // *cit = 10; // 错误：不能修改const迭代器指向的值
        cout << *cit << " ";
    }
    cout << endl;
    
    return 0;
}