cpp数据结构

删除方法

vector<int> v = {1,2,3,4,5}; 1、删除一个元素 v.erase(v.begin()+2); // 删除3 2、删除一段 v.erase(v.begin()+1, v.begin()+4); //删除2 3 4 3、删除最后一个 v.pop_back(); 4、删除所有 v.clear(); 6、按条件删除 v.erase(remove_if(v.begin(),v.end(), [](int x){ return x%2==0; }),v.end()); string 字符串本质类似于 vector<char> string s="abcdef"; s.erase(2,1); // abdef 删除后半段 s.erase(3); abc

set / multiset set<int> s={1,2,3,4}; 删除值 s.erase(2); // 结果1 3 4 删除迭代器 auto it=s.find(3); s.erase(it); 删除区间 s.erase(s.begin(),s.find(4)); map / multimap map<string,int> mp; 删除键 mp.erase("Tom"); 删除迭代器 mp.erase(mp.begin()); 删除范围 mp.erase(it1,it2);

复合类型

pair p = {"a",10}; p.first p.second tuple t = {"a",10,20}; get<0>(t) get<1>(t) get<2>(t) structs = {"a",10,20}; s.name s.hot s.price

tuple

头文件：<tuple>可以存N 个值访问用：get<下标>()下标从 0 开始

按“索引”访问

#include <tuple> #include <iostream> using namespace std; int main() { tuple<int, double, string> t = {1, 3.14, "hello"}; cout << get<0>(t) << endl; // 1 cout << get<1>(t) << endl; // 3.14 cout << get<2>(t) << endl; // hello }

按“类型”访问（有条件） 限制：类型必须唯一！

tuple<int, double, string> t = {1, 3.14, "hi"}; cout << get<int>(t) << endl; // 1 cout << get<double>(t) << endl; // 3.14

访问 tuple 大小

tuple<int, double, string> t; cout << tuple_size<decltype(t)>::value << endl; // 3

pair

头文件：<utility>只能存2 个值 访问用：.first .second

#include <iostream> #include <utility> // pair using namespace std; int main() { pair<string, int> p = {"apple", 10}; // 访问方式 cout << p.first << endl; // apple cout << p.second << endl; // 10 }

struct 访问

自己定义成员名 访问用：.自定义名字

#include <iostream> #include <string> using namespace std; // 定义结构体 struct Item { string name; int hot; int price; }; int main() { Item item = {"apple", 10, 100}; // 访问方式 cout << item.name << endl; // apple cout << item.hot << endl; // 10 cout << item.price << endl; // 100 }

排序

pair 排序 自带字典序自动比较，从左到右逐元素比

sort(v.begin(), v.end()); // 先比 first，再比 second

tuple 排序 自带字典序自动比较，从左到右逐元素比

sort(v.begin(), v.end()); // 自动字典序：get<0> → get<1> → get<2>

struct 排序 （必须自己写规则）

sort(v.begin(), v.end(), [](const Item& a, const Item& b) { return a.name < b.name; });

二、顺序容器（线性数组类）

1.array静态数组

头文件：<array>固定长度、栈上分配

array<int, 5> arr = {1,2,3,4,5};

访问接口

arr[i] 下标访问 .front() 首元素 .back() 尾元素 .size() 元素个数

2.vector动态数组

自动扩容，连续内存

vector<string> v{"app", "apple", "banana"};

访问接口

v[i] 下标随机访问 .front() 第一个 .back() 最后一个 .size() 大小 .begin() 起始迭代器 .end() 末尾迭代器

3.string字符串（本质字符容器）

头文件：<string>

访问接口

s[i] 按下标取字符 .size()/.length() 长度 支持字典序直接 < > == 比较

4.list双向链表

头文件：<list>不支持下标[]，只能迭代器遍历访问：只能用迭代器for (auto &x : lst)

5. string访问接口

一、基础信息接口（最常用） 1. size() / length()完全等价 2. empty() 3. s.clear(); // 变成 "" 二、访问字符接口 1. operator[] 不检查越界（危险⚠️） 2. at()（安全版）会检查越界,越界抛异常 3. front() / back() string s = "hello"; cout << s.front(); // h cout << s.back(); // o 三、修改字符串 s[0] = 'H'; s.append(" world"); 等价于 s += " world"; s.push_back('!'); s.pop_back(); （删除最后一个字符） 四、查找接口（非常重要⭐） 1. find() 返回： 找到：位置 找不到：string::npos 2. rfind() 从右往左找： 3. find_first_of() 找任意字符： 4. find_last_of() 最后出现的字符位置 五、截取子串（核心⭐） substr() string s = "hello world"; string t = s.substr(6, 5); // t = world 八、转换接口（高频⭐） 1. string -> int stoi("123"); 2. string -> long long stoll("123456789"); 3. int -> string to_string(123);

三、关联容器（键值 / 有序查找）

map

map取值

• []如果 key 不存在，自动插入 key，value 用默认值初始化
• at()key 不存在会抛异常
• find() *************取值之前最好先find一下，返回迭代器

auto it = mp.find("apple"); // 找到 if (it != mp.end()) { cout << it->second; } //没找到 if (it == mp.end())

• count()if (mp.count("apple"))map 中：存在返回 1 不存在返回 0 因为 map 不允许重复 key。
• contains()（C++20）

if (mp.contains("apple")) 等价于 if (mp.find("apple") != mp.end())

map遍历方法

int main() { map<string, int> mp; mp["apple"] = 3; mp["banana"] = 5; mp["orange"] = 2; }

1. ******迭代器遍历（最经典）

for (map<string, int>::iterator it = mp.begin(); it != mp.end(); ++it) { cout << it->first << " " << it->second << endl; }

2. auto 简化（实际开发最常用）

for (auto it = mp.begin(); it != mp.end(); ++it) { cout << it->first << " " << it->second << endl; }

3.********** 范围 for 遍历（C++11）

方法1：直接取 pair

for (auto p : mp) { cout << p.first << " " << p.second << endl; }

方法2：引用（推荐）

for (auto& p : mp) { cout << p.first << " " << p.second << endl; } for (pair<const string, int>& p : mp) { cout << p.first << " " << p.second << endl; }

4. 结构化绑定（C++17，非常高级）

for (auto& [key, value] : mp) { cout << key << " " << value << endl; }

5. 遍历时删除元素（重点面试）

//错误写法： for (auto it = mp.begin(); it != mp.end(); ++it) { if (it->second == 5) mp.erase(it); // 错误 } // 因为 erase 后迭代器失效。 //正确写法： for (auto it = mp.begin(); it != mp.end(); ) { if (it->second == 5) it = mp.erase(it); // // 返回下一个有效迭代器 else ++it; }

map常用容量接口

mp.size() 元素数量。 mp.empty() 是否为空。 mp.clear() 清空。 map插入元素 mp.insert(pair<string, int>("apple", 10)); mp.insert(make_pair("banana", 20)); mp.insert({"orange", 30}); auto result = mp.insert({"apple", 100}); cout << *result .first << endl; 输出apple 这个result 类型为pair<iterator, bool> 12. 哈希表特有接口（高级） mp.bucket_count() 桶数量 rehash() 重新分桶 mp.load_factor() 负载因子 reserve() 预留空间

set

set特有接口

s.lower_bound(5) 第一个 >= 5 的元素 s.upper_bound(5) 第一个 > 5 的元素 auto p = s.equal_range(5); 返回[lower_bound, upper_bound)

set遍历

set<int> s = {1, 3, 5, 7}; for (set<int>::iterator it = s.begin(); it != s.end(); ++it) { cout << *it << endl; }