vector

头文件#include <vector>

定义一个vector

//初始化定义，一个动态数组a
vector<int> a;
//定义一个长度10的vector
vector<int> a(10);
//全部初始化为3
vector<int> a(10, 3);
//定义一个vector数组，里面包含10个动态数组，初始长度为0
vector<int> a[10];
//二维vector相当于矩阵
vector<vector<int>> t;
//按每行遍历
for(auto &t : t)
  t[0] ~ t[n];

函数

返回数组大小a.size();

判断数组是否为空a.enpty();

清空clear()

返回vector的第一个数/最后一个数front()/back()

向vector最后插入一个元素push_back()

在vector末尾插入一个元素emplace_back()

它会直接在容器中构造该元素。相较于 push_back，emplace_back 可以避免不必要的拷贝或移动，因为它直接在 vector 内部构造对象。

把vector最后一个数删掉pop_back()

unique

erase

• 来源：erase 是所有标准序列容器（如 std::vector、std::list、std::deque、std::set 等）的一部分。
• 功能：erase 用于删除容器中的元素，可以接受一个迭代器作为参数，用来指定要删除的元素或元素范围。

// 使用 std::vector
    vector<int> vec = {1, 2, 2, 3, 4, 4, 5};
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    
    cout << "Unique elements in vector: ";
    for (int val : vec) {
        cout << val << " ";
    }

assign：用于初始化

语法

void assign(size_type count, const T& value);

• count: 需要容器分配的元素数量。
• value: 每个元素的初始值。

解释

在这段代码中：

vector<vector<int>> memo;
memo.assign(m, vector<int>(n, -1));

• m: 二维向量的行数。
• vector<int>(n, -1): 每一行是一个长度为 n 的向量，初始化为 -1。
• assign() 会清空原内容，然后重新分配内存并填充新值。

迭代器

返回第0个数指针 begin()

最后一个数的后面一个数end()

遍历方式

for(inr i = 0; i < n; i++) cout<<a[i]<<endl;
//迭代器遍历,也可以使用auto
for(vector<int>::iterator i = a.begin(); i != a.end(); i++) cout<<*i<<endl;
//c++范围遍历
for(auto x : a) cout<<x<<endl;

支持比较运算

可以按照字典序进行比较

vector<int> a(4, 3), b(3, 4);
if(a < b) puts("a < b");

pair

初始化

两个键值可以任意

pair<int, string> p;
//赋值
p = make_pair(10, "abc");
p = {10, "abc"};

//如果需要表示三种属性
pair<int , pair<int, int>>

获取关键词

p.first; p.second:

支持比较运算，优先比较first的值，其次比较second

string

初始化

string a = "abc";
a += "def";
a += 'a';

函数

substr() 返回子串，第一个参数是起始下标从0开始，第二个参数是子串长度，如果超出数组长度就输出到最后一个字母为止，第二个参数可以省略返回从第一个参数开始的整个字符串

c_str()返回数组的起始地址

queue

函数

push() 队尾插入一个元素

pop() 从队头弹出一个元素

front() 返回队头元素

back() 返回队尾元素

size()

empty()

队列没有clear()函数，一般通过重新构造队列清空元素

q = queue<int>()

Priority_queue

优先队列基本原理是堆，默认大根堆

头文件#include

初始化

priority_queue<int> heap;
//定义小根堆，想要插入的时候插入负数
heap.push(-1);
//直接定义小根堆
priority_queue<int, vector<int>, greater<int>> heap;

函数

pop() 弹出堆顶元素

push() 插入一个元素

top() 返回堆顶元素

在 C++ 的 priority_queue 模板中，前三个参数分别是：

1. T (第一个参数):
   这是 priority_queue 中存储元素的类型。在你的例子中，int 表示堆中存储的元素是整数。
2. Container (第二个参数):
   这是用来存储数据的底层容器类型，通常是一个顺序容器，比如 vector 或 deque。默认情况下，priority_queue 使用 vector<T> 作为底层容器。在你的例子中，vector<int> 表示用 std::vector 来存储整数。
3. Compare (第三个参数):
   这是一个比较函数，用来决定堆的顺序（大根堆还是小根堆）。默认是 less<T>，也就是大根堆。如果你希望实现小根堆，可以使用 greater<T>。在你的例子中，greater<int> 表示使用小根堆排序，即较小的元素在堆顶。

完整解释：

priority_queue<int, vector<int>, greater<int>>

• int: 堆中存储的是 int 类型的元素。
• vector<int>: 使用 std::vector<int> 作为底层存储容器。
• greater<int>: 使用 std::greater<int> 作为比较函数，实现小根堆。

默认值：

如果你省略第二和第三个参数，priority_queue 默认使用 vector<T> 作为容器，less<T> 作为比较器（大根堆）。

priority_queue<int> maxHeap;  // 大根堆，默认使用 vector<int> 和 less<int>

stack

函数

pop() 弹出栈顶元素

push() 向栈顶插入一个元素

top() 返回栈顶元素

empty()

size()

deque

双端队列

初始化

deque<int> q

函数

empty()

size()

clear()

front() /back() 返回队首/队尾元素

push_back()/pop_back() 弹出/插入队尾元素

push_front()/pop_front() 弹出/插入队首元素

支持随机寻址

也支持迭代器begin()/end()

set

头文件#include <set>

与map不同

unordered_set：存储的是有序，唯一的元素，即集合中的每个元素只能出现一次。它不存储元素的索引或其他信息。

unordered_map：存储的是键值对（key-value pairs）。每个键（key）对应一个值（value），一个键只能出现一次，但多个键可以有不同的值。

基于平衡二叉树（红黑数），动态维护有序序列

所有操作i/f的时间复杂度是O(logn)

包含两个用法初始化

#include <set>

//不允许包含重复元素，插入重复元素的操作会被忽略掉
set<int> S;
//可以有重复元素
mutiset<int> MS;

函数

insert() 插入一个数

s.insert(5);
s.insert(2);
s.insert(2); // 无效，因为 2 已存在

删除元素

erase() 1、输入是一个数x，删除所有数x 复杂度O(K + logn) k是x的个数

​ 2、输入是一个迭代器，删除迭代器

s.erase(2);         // 删除值为 2 的元素
s.erase(s.begin()); // 删除第一个元素（最小的）
s.clear();          // 清空所有元素

find() 查找一个数,不存在会返回end迭代器

auto it = s.find(3); // 找到返回迭代器，找不到返回 s.end()
if (it != s.end()) {
    std::cout << "Found 3";
}

count() 返回某个数的个数，用于mutiset，对于普通的set可以判断是否存在某个元素

if (s.count(3) > 0) {
    std::cout << "3 exists!";
}

lower_bound()/ upper_bound()

lower_bound()返回大于等于x最小的数

upper_bound()返回大于x的最小的数，如果不存在返回end()

begin()/end() 支持++/--

map

也是两种map/mutimap

map存的是一个映射

insert() 插入一个pair logn

erase() 参数是pair或者迭代器 logn

find() logn

lower_bound()/ upper_bound() logn

begin()/end() 支持++/-- logn

map可以当数组用

#include<iostream>
#include<map>
using namespace std;

int main()
{
  map<string, int> a;
  a["adc"] = 2;
  //时间复杂度logn
  cout<<a["abd"]<<endl;
  return 0;
}

map和set一样除了size，insert， count的其他操作复杂度都是logn

unordered_set, unordered_map, unordered_mutiset, unordered_mutimap 操作和set，map一样

但是绝大数操作增删改查复杂度是O(1)的，不支持lower_bound()/ upper_bound()，因为内部无序、

迭代器的++/--不支持，和排序有关的操作不支持

区分键和值的方法是看它们在映射中的位置：在 unordered_map 的定义中，左侧的元素是键，右侧的元素是对应的值。

Unordered_map

键值对概念

unordered_map<char, char> pairs = {
    {')', '('},
    {']', '['},
    {'}', '{'}
};

这表示：

• 键 ')' 的值是 '('。
• 键 ']' 的值是 '['。
• 键 '}' 的值是 '{'。

函数

元素插入

map.insert({"key", value});         // 插入一个键值对
map["key"] = value;                 // 使用 [] 插入或修改元素
map.emplace("key", value);         // 就地构造，避免拷贝，提高效率

查找

auto it = map.find("key");         // 返回迭代器，如果没找到则为 map.end()
if (it != map.end()) {
    std::cout << it->second;
}
//查找是否存在
if (map.count("key") > 0) {
    // 存在该 key
}

大小相关

map.size();                        // 当前元素数量
map.empty();                       // 是否为空

count函数

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> fruitCount = {
        {"apple", 3},
        {"banana", 5},
        {"orange", 2}
    };

    string fruit = "banana";
    
    // 使用 count 检查键是否存在
    if (fruitCount.count(fruit)) {
        cout << fruit << " is in the map." << endl;
    } else {
        cout << fruit << " is not in the map." << endl;
    }

    return 0;
}

在这个例子中，count 检查键 "banana" 是否存在于 fruitCount 中。如果存在，输出结果将是 "banana is in the map."。如果你检查一个不存在的键，如 "grape"，则会输出 "grape is not in the map."。

count函数和find函数区别

#include <iostream>
#include <map>
using namespace std;

int main() {
    map<string, int> myMap = {{"apple", 1}, {"banana", 2}};

    // 使用 count
    cout << "Count for 'banana': " << myMap.count("banana") << endl; // 输出 1

    // 使用 find
    auto it = myMap.find("banana");
    if (it != myMap.end()) {
        cout << "Found 'banana' with value: " << it->second << endl; // 输出 2
    } else {
        cout << "'banana' not found." << endl;
    }

    return 0;
}

• count(key)：用于检查指定的键在映射中出现的次数。在 std::map 中，返回值通常是 0 或 1，因为键是唯一的。返回 0 表示键不存在，返回 1 表示键存在。
• find(key)：用于查找指定键并返回一个迭代器。如果键存在，返回指向该键值对的迭代器；如果键不存在，返回 end() 迭代器。

压位

初始化

#include<bitset>

int main()
{
  //中括号里存的是个数
  bitset<10000> S；
  //支持各种位运算操作
  ~S;//取反，&与, |或, ^异或, <</>>移位, []取出某一位， !=/==
  
  count();//返回有多少个1
  any();//返回是否至少有一个1
  none();//判断是否全为0
  set();//所以位置全置1
  set(k, v);//将第k位置v
  reset();//所以位置0
  flip();//所以位取反
  flip(k);//第k位取反
  
}

c++函数

lower_bound

lower_bound 是 C++ 标准库中 <algorithm> 头文件提供的一个函数，用来在一个 已排序 的区间内查找第一个 不小于 给定值的元素的位置。它返回一个迭代器，指向该位置的元素。如果找到了这样的元素，返回该元素的迭代器；如果没有找到，返回指向区间末尾的迭代器。

左闭右开区间：lower_bound 查找的是左闭右开区间 [first, last)，即包含 first 但不包含 last。需要包含last则需要输入last+1

int main() {
    vector<int> vec = {1, 2, 4, 6, 8, 10};

    // 查找第一个不小于 5 的元素
    auto it = lower_bound(vec.begin(), vec.end(), 5);
    int j = lower_bound(left.begin() + 2, left.begin() + 6, 4) - left.begin();

    if (it != vec.end()) {
        cout << "First element not less than 5: " << *it << endl;
          cout << "偏移量是" << j <<endl;
    } else {
        cout << "No element not less than 5." << endl;
    }

    return 0;
}//First element not less than 5: 6
//偏移量是2

sort

是的，C++ 标准库中的 std::sort 函数的排序范围是左闭右开（即 [start, end)）的区间，这意味着：

• 包含起始指针 start 指向的元素；
• 不包含结束指针 end 指向的元素。

---

具体解释

假设有一个数组 arr，长度为 n，其元素索引为 0 到 n-1：

int arr[] = {1, 3, 2, 5, 4};
int n = 5;

正确排序整个数组的方式：

std::sort(arr, arr + n); // 排序范围是 [arr, arr + n)

• arr 是数组的起始地址（包含）；
• arr + n 是数组末尾的后一个地址（不包含）；
• 实际排序的元素是 arr[0] 到 arr[n-1]。

如果写成：

std::sort(arr, arr + n - 1); // 错误！只排序了 [arr, arr + n - 1)

• 只会排序 arr[0] 到 arr[n-2]，最后一个元素 arr[n-1] 被遗漏。

---

应用到你的代码中

你的代码中，城市数组 cities 的有效索引是 1 到 n（从 1 开始），因此正确排序整个数组的方式应为：

sort(cities + 1, cities + n + 1, cmp); 
// 或者：sort(&cities[1], &cities[n] + 1, cmp);

• cities + 1 是第一个有效元素（cities[1]）；
• cities + n + 1 是最后一个有效元素的后一个位置（cities[n] 的后一个位置）；
• 实际排序的范围是 cities[1] 到 cities[n]。

---

常见错误示例

错误写法：

sort(cities + 1, cities + n, cmp); 

• 排序范围是 [cities + 1, cities + n)；
• 实际只排序了 cities[1] 到 cities[n-1]，遗漏了 cities[n]。

正确写法：

sort(cities + 1, cities + n + 1, cmp); 

• 排序范围是 [cities + 1, cities + n + 1)；
• 实际排序了 cities[1] 到 cities[n]，覆盖所有有效元素。

---

总结

• std::sort 的区间是左闭右开的（[start, end)）；
• 如果数组索引从 1 开始，排序整个数组的正确写法是 sort(start, start + n)；
• 在你的代码中，需将 sort(cities + 1, cities + n, cmp) 改为 sort(cities + 1, cities + n + 1, cmp)，以确保所有 n 个元素都被正确排序。

通过这种方式，可以避免因区间错误导致的遗漏元素问题。