1
2
3
4
5
6
7
8
9
10
11
12
// 创建空deque
deque<int> dq;

// 使用初始化列表
deque<int> dq = {1, 2, 3, 4, 5};

// 指定大小和初始值
deque<int> dq(5, 10);  // 5个元素，每个都是10

// 从其他容器复制
vector<int> vec = {1, 2, 3, 4, 5};
deque<int> dq(vec.begin(), vec.end());

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 访问元素
deque<int> dq = {1, 2, 3, 4, 5};
cout << dq[0] << endl;        // 使用下标访问
cout << dq.at(1) << endl;     // 使用at()访问，带边界检查
cout << dq.front() << endl;   // 访问第一个元素
cout << dq.back() << endl;    // 访问最后一个元素

// 添加元素
dq.push_front(0);    // 在头部添加元素
dq.push_back(6);     // 在尾部添加元素
dq.emplace_front(0); // 在头部构造并添加元素
dq.emplace_back(6);  // 在尾部构造并添加元素

// 删除元素
dq.pop_front();      // 删除头部元素
dq.pop_back();       // 删除尾部元素
dq.erase(dq.begin() + 2);  // 删除指定位置的元素
dq.erase(dq.begin(), dq.begin() + 2);  // 删除一个范围的元素

// 大小操作
cout << dq.size() << endl;     // 获取元素个数
cout << dq.empty() << endl;    // 检查是否为空
dq.resize(10);                 // 调整大小
dq.resize(10, 0);             // 调整大小并用0填充

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 使用迭代器遍历
deque<int> dq = {1, 2, 3, 4, 5};
for (auto it = dq.begin(); it != dq.end(); ++it) {
    cout << *it << " ";
}

// 使用反向迭代器
for (auto it = dq.rbegin(); it != dq.rend(); ++it) {
    cout << *it << " ";
}

// 使用范围for循环
for (const auto& elem : dq) {
    cout << elem << " ";
}

1
2
3
4
5
6
7
8
9
// 预分配空间（注意：deque没有reserve方法）
// 但可以通过resize预分配空间
deque<int> dq;
dq.resize(1000);  // 预分配1000个元素的空间

// 使用emplace代替push
deque<pair<int, string>> dq;
dq.emplace_back(1, "hello");  // 直接构造，避免拷贝
dq.emplace_front(0, "world"); // 在头部直接构造

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
// 1. 实现滑动窗口
void slidingWindow(const vector<int>& nums, int k) {
    deque<int> dq;  // 存储下标
    for (int i = 0; i < nums.size(); ++i) {
        // 移除超出窗口范围的元素
        while (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();
        }
        // 移除小于当前元素的元素
        while (!dq.empty() && nums[dq.back()] < nums[i]) {
            dq.pop_back();
        }
        dq.push_back(i);
        if (i >= k - 1) {
            cout << nums[dq.front()] << " ";  // 输出窗口最大值
        }
    }
}

// 2. 实现双端队列
class MyCircularDeque {
private:
    deque<int> dq;
    int capacity;
public:
    MyCircularDeque(int k) : capacity(k) {}
    
    bool insertFront(int value) {
        if (dq.size() >= capacity) return false;
        dq.push_front(value);
        return true;
    }
    
    bool insertLast(int value) {
        if (dq.size() >= capacity) return false;
        dq.push_back(value);
        return true;
    }
    
    bool deleteFront() {
        if (dq.empty()) return false;
        dq.pop_front();
        return true;
    }
    
    bool deleteLast() {
        if (dq.empty()) return false;
        dq.pop_back();
        return true;
    }
    
    int getFront() {
        return dq.empty() ? -1 : dq.front();
    }
    
    int getRear() {
        return dq.empty() ? -1 : dq.back();
    }
    
    bool isEmpty() {
        return dq.empty();
    }
    
    bool isFull() {
        return dq.size() == capacity;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 使用emplace代替insert
set<int> s;
s.emplace(1);  // 直接构造，避免拷贝

// 使用extract（C++17）
auto node = s.extract(1);  // 提取节点而不删除
if (!node.empty()) {
    node.value() = 2;  // 修改值
    s.insert(std::move(node));  // 重新插入
}

// 使用merge（C++17）
set<int> s1{1, 2, 3};
set<int> s2{4, 5, 6};
s1.merge(s2);  // 合并两个set

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 查找函数 find() 通过给定主键查找元素，返回第一个匹配的迭代器
unordered_multiset<int>::iterator find_iter = c1.find(1);

// value出现的次数 count() 返回匹配给定主键的元素的个数
size_t count = c1.count(1);

// 返回元素在哪个区域 equal_range() 返回值匹配给定搜索值的元素组成的范围
pair<unordered_multiset<int>::iterator, unordered_multiset<int>::iterator> pair_equal_range = c1.equal_range(1);

// 插入函数 emplace()
c1.emplace(1);

// 插入函数 emplace_hint() 使用迭代器
c1.emplace_hint(ite_begin, 1);

// 插入函数 insert()
c1.insert(1);

// 删除 erase()
c1.erase(1); // 1.迭代器 value 区域

// 清空 clear()
c1.clear();

// 交换 swap()
c1.swap(c2);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <unordered_set>
#include <iostream>

int main() {
    unordered_multiset<int> ums = {1, 2, 2, 3, 3, 3};
    
    // 插入元素
    ums.insert(4);
    ums.emplace(4);
    
    // 查找元素
    auto it = ums.find(2);
    if (it != ums.end()) {
        cout << "Found: " << *it << endl;
    }
    
    // 计数
    cout << "Count of 3: " << ums.count(3) << endl;
    
    // 范围
    auto range = ums.equal_range(3);
    for (auto i = range.first; i != range.second; ++i) {
        cout << *i << " ";
    }
    cout << endl;
    
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 使用emplace代替insert
map<string, int> m;
m.emplace("key", 1);  // 直接构造，避免拷贝

// 使用try_emplace（C++17）
m.try_emplace("key", 1);  // 只在key不存在时插入

// 使用insert_or_assign（C++17）
m.insert_or_assign("key", 2);  // 插入或更新

// 使用结构化绑定（C++17）
for (const auto& [key, value] : m) {
    cout << key << ": " << value << endl;
}

// 使用contains（C++20）
if (m.contains("key")) {
    // key存在
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 自定义哈希函数
struct MyHash {
    size_t operator()(const string& s) const {
        return hash<string>()(s);
    }
};
unordered_map<string, int, MyHash> um;

// 自定义相等比较函数
struct MyEqual {
    bool operator()(const string& a, const string& b) const {
        return a.length() == b.length();
    }
};
unordered_map<string, int, MyHash, MyEqual> um;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 访问元素
unordered_multimap<string, int> umm;
umm.emplace("apple", 1);
umm.emplace("banana", 2); // unordered_multimap 不支持 operator[]

// 查找函数 find() 通过给定主键查找元素，返回第一个匹配的迭代器
auto find_iter = umm.find("apple");

// value出现的次数 count() 返回匹配给定主键的元素的个数
size_t count = umm.count("apple");

// 返回元素在哪个区域 equal_range() 返回键匹配给定搜索值的元素组成的范围
auto pair_equal_range = umm.equal_range("apple");

// 插入函数 emplace()
umm.emplace("cherry", 3);

// 插入函数 emplace_hint() 使用迭代器
umm.emplace_hint(umm.begin(), "date", 4);

// 插入函数 insert()
umm.insert({"elderberry", 5});

// 删除 erase()
umm.erase("banana"); // 1.键 value 区域

// 清空 clear()
umm.clear();

// 交换 swap()
umm.swap(umm2);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <unordered_map>
#include <iostream>

int main() {
    unordered_multimap<string, int> umm = {{"apple", 1}, {"banana", 2}, {"banana", 3}, {"cherry", 4}};
    
    // 插入元素
    umm.emplace("date", 5);
    umm.insert({"elderberry", 6});
    
    // 查找元素
    auto it = umm.find("banana");
    if (it != umm.end()) {
        cout << "Found: " << it->first << " -> " << it->second << endl;
    }
    
    // 计数
    cout << "Count of banana: " << umm.count("banana") << endl;
    
    // 范围
    auto range = umm.equal_range("banana");
    for (auto i = range.first; i != range.second; ++i) {
        cout << i->first << " -> " << i->second << endl;
    }
    
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
int findKthLargest(std::vector<int>& nums, int k) {
    std::priority_queue<int, std::vector<int>, std::greater<int> > q;
    for (auto &num : nums){
      if (q.size() < k) {
        q.push(num);
      } else if (num > q.top()) {
        q.pop();
        q.push(num);
      }
    }
    return q.top();
  }

1
#include <algorithm>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// for_each: 对区间内每个元素执行操作
//todo

// count, count_if：统计元素出现次数
// count: 计数
int n = count(vec.begin(), vec.end(), value);
// count_if: 条件计数
int n = count_if(vec.begin(), vec.end(), [](int x) { return x > 5; });


// all_of/any_of/none_of: 条件检查
bool all_positive = all_of(vec.begin(), vec.end(), [](int x) { return x > 0; });
bool any_positive = any_of(vec.begin(), vec.end(), [](int x) { return x > 0; });
bool none_positive = none_of(vec.begin(), vec.end(), [](int x) { return x > 0; });

1
2
3
4
5
6
7
8
9
10
11
// sort: 排序
sort(vec.begin(), vec.end());

// stable_sort: 稳定排序
stable_sort(vec.begin(), vec.end());

// partial_sort: 部分排序
partial_sort(vec.begin(), vec.begin() + 5, vec.end());  // 只排序前5个元素

// nth_element: 将第n个元素放到正确位置
nth_element(vec.begin(), vec.begin() + n, vec.end());

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// find: 查找元素
auto it = find(vec.begin(), vec.end(), value);

if (std::find(myvec.begin(), myvec.end(), num) == myvec.end()) {
// 没找到
}

// find_if: 使用谓词查找元素
auto it = find_if(vec.begin(), vec.end(), [](int x) { return x > 5; });

// binary_search: 二分查找（要求容器已排序）
bool exists = binary_search(vec.begin(), vec.end(), value);

// 二分查找
// lower_bound: 返回第一个不小于value的元素位置
int value = 5;
auto it = lower_bound(vec.begin(), vec.end(), value);
if (it != vec.end()) {
    cout << "Found 5 at position " << (it - vec.begin()) << endl;
}

// upper_bound: 返回第一个大于value的元素位置
auto it = upper_bound(vec.begin(), vec.end(), value);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// copy: 复制元素
copy(source.begin(), source.end(), dest.begin());

// move: 移动元素
move(source.begin(), source.end(), dest.begin());

// replace: 替换元素
replace(vec.begin(), vec.end(), old_value, new_value);

// fill: 填充元素
fill(vec.begin(), vec.end(), value);

// generate: 生成元素
generate(vec.begin(), vec.end(), []() { return rand(); });

// transform: 转换元素
transform(vec.begin(), vec.end(), result.begin(), [](int x) { return x * 2; });

1
2
3
4
5
6
7
8
9
10
11
12
// remove
// 移除元素（不改变容器大小）
auto new_end = remove(vec.begin(), vec.end(), value);
vec.erase(new_end, vec.end());  // 实际删除元素

// unique
// 移除相邻重复元素
//unique将相邻的重复元素移动到末尾,并不是直接删除,
//注意"相邻的",所以要先进行排序，保证重复元素相邻
//unique() 的返回值就是被后置元素的"首地址"(迭代器)
auto new_end = unique(vec.begin(), vec.end());
vec.erase(new_end, vec.end());  // 实际删除元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// accumulate: 累加
int sum = accumulate(vec.begin(), vec.end(), 0);
int product = accumulate(vec.begin(), vec.end(), 1, multiplies<int>());

// max_element/min_element: 找最大/最小元素
auto max_it = max_element(vec.begin(), vec.end());
auto min_it = min_element(vec.begin(), vec.end());

// inner_product: 内积
int result = inner_product(vec1.begin(), vec1.end(), vec2.begin(), 0);

// partial_sum: 部分和
partial_sum(vec.begin(), vec.end(), result.begin());

// adjacent_difference: 相邻差
adjacent_difference(vec.begin(), vec.end(), result.begin());

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 双向迭代器
std::list<int>::iterator list_it;
std::set<int>::iterator set_it;

// 反向迭代器
std::vector<int> v = {1, 2, 3, 4, 5};
std::vector<int>::reverse_iterator rit = v.rbegin();

// 常量迭代器
std::vector<int> v = {1, 2, 3};
std::vector<int>::const_iterator cit = v.cbegin();
// *cit = 10; // 错误：不能修改值


// 移动迭代器
std::vector<std::string> source = {"hello", "world"};
std::vector<std::string> dest(std::make_move_iterator(source.begin()),
                            std::make_move_iterator(source.end()));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 插入迭代器
std::back_inserter(container);    // 尾部插入
std::front_inserter(container);   // 头部插入
std::inserter(container, pos);    // 指定位置插入

// 流迭代器
// 输入流迭代器
std::istream_iterator<int> input_iter(std::cin);
// 输出流迭代器
std::ostream_iterator<int> output_iter(std::cout, " ");

// 反向迭代器适配器
std::vector<int> v = {1, 2, 3};
auto rit = std::make_reverse_iterator(v.end());

1
2
3
4
5
6
7
8
std::list<int>::iterator it = lst.begin();
std::advance(it, 5); // 前进5个位置

auto dist = std::distance(begin, end); // 计算迭代器间距离

auto next_it = std::next(it);      // 下一个位置
auto prev_it = std::prev(it);      // 前一个位置
auto next_5 = std::next(it, 5);    // 前进5个位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 使用auto简化迭代器声明
for (auto it = vec.begin(); it != vec.end(); ++it) {
    // 使用迭代器
}

// 使用范围for循环
for (const auto& element : vec) {
    // 使用元素
}

// 使用反向迭代器
for (auto it = vec.rbegin(); it != vec.rend(); ++it) {
    // 反向遍历
}

// 使用const迭代器
for (const auto it = vec.cbegin(); it != vec.cend(); ++it) {
    // 只读访问
}

1
2
3
4
5
template <class... Args>
iterator emplace(Args&&... args) {
    // 在容器内部分配空间，并用参数 args... 原地构造对象
    return insert_internal(std::forward<Args>(args)...);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 快排的三路分割优化
template<typename Iterator>
void quicksort(Iterator first, Iterator last) {
    if (first >= last) return;
    
    // 选择pivot（通常使用三数取中法）
    auto pivot = median_of_three(first, first + (last - first)/2, last - 1);
    
    // 分割（C++14 不支持结构化绑定，这里用 pair 接收）
    auto range = partition(first, last, pivot);
    auto lt = range.first;
    auto gt = range.second;
    
    // 递归排序
    quicksort(first, lt);
    quicksort(gt, last);
}

1
2
3
4
5
6
7
8
9
10
template<typename Iterator>
void heapsort(Iterator first, Iterator last) {
    // 建堆
    make_heap(first, last);
    
    // 依次取出最大元素
    while (last > first) {
        pop_heap(first, last--);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
template<typename Iterator>
void insertion_sort(Iterator first, Iterator last) {
    for (auto it = first + 1; it != last; ++it) {
        auto key = *it;
        auto j = it - 1;
        
        while (j >= first && *j > key) {
            *(j + 1) = *j;
            --j;
        }
        *(j + 1) = key;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
std::vector<int> vec{1, 2, 3, 4, 5};
auto it = vec.begin();

// ❌ 插入导致扩容，迭代器失效
vec.push_back(6);  // 可能扩容
std::cout << *it;  // 未定义行为！

// ✅ 重新获取迭代器
vec.push_back(6);
it = vec.begin();
std::cout << *it;  // OK

// ✅ 使用索引代替迭代器
size_t index = 0;
vec.push_back(6);
std::cout << vec[index];  // OK

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
std::vector<int> vec{1, 2, 3, 4, 5};

// ❌ 错误：删除后继续使用迭代器
for (auto it = vec.begin(); it != vec.end(); ++it) {
    if (*it % 2 == 0) {
        vec.erase(it);  // it失效！
    }
}

// ✅ 正确：使用erase的返回值
for (auto it = vec.begin(); it != vec.end(); ) {
    if (*it % 2 == 0) {
        it = vec.erase(it);  // erase返回下一个有效迭代器
    } else {
        ++it;
    }
}

// ✅ 更好：使用std::remove_if（C++20前）
vec.erase(
    std::remove_if(vec.begin(), vec.end(), [](int x) { return x % 2 == 0; }),
    vec.end()
);

// ✅ 最佳：std::erase_if（C++20）
std::erase_if(vec, [](int x) { return x % 2 == 0; });