C++STL常用数据结构及操作

前言

本文的整理针对平常做算法题比较常用的数据结构和操作，并不适用于平常工程或项目。
大部分算法题涉及到的数据结构并不复杂，所以本文整理的数据结构都是比较基础的操作，适合忘记怎么操作的时候看一眼。

根据做题情况持续更新中…

vector-动态数组

定义在头文件 vector 中

初始化：

• vector<type> vec：无元素，此时访问会越界
• vector<type> vec(n)：创建 n 个默认初始化的元素
• vector<type> vec(n, val)：创建 n 个值为 val 的元素

常用操作：

• vec.size()：返回数组大小
• vec.clear()：清空数组
• vec.push_back(val)：在数组最后插入一个元素 val
• vec.pop_back()：删除最后一个元素
• vec[index]：通过下标访问元素
• vec.front()：第一个元素
• vec.back()：最后一个元素（常用于模拟栈）

其他操作：i 从0开始

• vec.insert(vec.begin() + i, val)：在第 i 个元素前插入 val
• vec.erase(vec.begin() + i)：删除第 i 个元素

map-哈希表

map 和 unordered_map 分别定义在头文件 map 和 unordered_map 中，其中又细分出 multimap 和 unordered_multimap。

区别如下：

• map：底层存储是有序的，维护有序需要一定的性能开销
• unordered_map：底层存储无序
• multimap：可以出现重复关键字的 map
• unordered_multimap：可以出现重复关键字的 unordered_map

操作几乎没有区别，以下以 map 举例。

初始化：

• map<type1, type2> hashTable：通过 hashTable[type1Val] 访问到type2Val

常用操作：

• hashTable.find(key)：如果没有键 key，返回 hashTable.end()，否则返回其迭代器
• hashTable[key] = val：如果存在 key 为 val 的元素，修改其值，否则创建一个 key 为 key 值为 val 的元素
• hashTable.erase(key)：移除键为 key 的元素

遍历：

//e 类型为 pair<type1, type2>&
for(auto& e : hashTable){
	//e.first为 key，e.second 为其值
	e.second = val;
}

set-集合

set 和 unordered_set 分别定义在头文件 set 和 unordered_set 中，其中又细分出 multiset 和 unordered_multiset。

区别如下：

• set：底层存储是有序的，维护有序需要一定的性能开销
• unordered_set：底层存储无序
• multiset：可以出现重复关键字的 set
• unordered_multiset：可以出现重复关键字的 unordered_set

操作几乎没有区别，以下以 set 举例。

初始化：

• set<type> s：创建一个集合s

常用操作：

• s.insert(val)：插入一个值为 val 的元素
• s.count(val)：返回值 val 的计数
• s.erase(val)：删除元素 val

stack-栈

stack定义在头文件stack中。

初始化：

• stack<type> s：创建一个空栈 s

常用操作：

• s.empty()：栈空返回真
• s.push(val)：将 val 压入栈
• s.top()：返回栈顶元素，不删除
• s.pop()：弹出栈顶元素，没有返回值
• s.size()：返回栈大小
• s = stack<type>()：通常用于清空栈

queue-队列

queue 定义在头文件 queue 中，deque 定义在头文件 deque 中。

queue 为一般队列，一边进另一边出。
deque 为双端队列，两边都可进或出。
priority_queue 为优先队列，是有序的。

初始化：

• queue<type> q：创建一个空队列 q
• deque<type> dq：创建一个空双端队列 dq
• priority_queue<type>：默认是大顶堆，队首元素最大。
• priority_queue<type, vector<type>, greater<int>>：小顶堆，队首元素最小。其中第二个参数 vector<type> 代表底层存储容器，greater<int> 为比较器，可以自定义。

queue操作：

• q.front()：返回第一个元素（最早插入的），不删除
• q.back()：返回最后一个元素（最近插入的），不删除
• q.push(val)：压入一个元素 val
• q.pop()：弹出第一个元素

deque操作：

• dq.push_back(val)：在后端压入一个元素 val
• dq.push_front(val)：在前端压入一个元素 val
• dq.pop_back()：弹出最后端的元素
• dq.pop_front()：弹出最前端的元素
• dq.front()：返回最前端的元素，不删除
• dq.back()：返回最后端的元素，不删除

priority_queue 操作：同上，只不过不同的是 push 后，元素的位置是不确定的，根据大小会自己找到一个合适的位置。而 pop 只会弹出堆顶元素。

自定义排序：通过重载 () 运算符

template <typename T>
struct Compare {
    bool operator()(T a, T b) {
        return a < b; // 大顶堆
        return a > b; // 小顶堆
    }
};

// 声明
std::priority_queue<int, std::vector<int>, Compare<int>> pq;

// 也可以通过 lambda 表达式
auto compare = [](int a, int b) {
	return a < b; // 大顶堆
	return a > b; // 小顶堆
};

// 声明
std::priority_queue<int, std::vector<int>, decltype(compare)> pq(compare);

sort

对于自定义的比较器，当比较器返回 true 时，第一个参数放在前面，第二个参数放在后面，即位置不变，当比较器返回 false 时，为两元素交换位置。

自定义比较器：

vector<int> vec{1, 2, 3, 5, 4};
std::sort(vec.begin(), vec.end(), [](int a, int b) {
	return a < b; // 按升序排序
	return a > b; // 按降序排序
});

字符串

字符判断：参数为 char

• isdigit()：判断是否为数字
• isalpha()：判断是否为字母（不区分大小写）
• isupper()：判断是否为大写字母
• islower()：判断是否为小写字母
• isalnum()：判断是否为字母和数字
• toupper()：将字母转化为大写
• tolower()：将字母转化为小写

查找子串：str.find("something", idx)：返回子串第一个字符的下标，idx 为开始寻找的起始下标

替代子串：str.replace(idx, len, str2)：从 idx 开始，替换成 str2，长度为 len，如果 len 短于 str2.size()，则取 str2 的部分，过长则可能溢出

获取子串：str.substr(idx, len)：从 idx 开始获取长度为 len 的子串

数字转化：

• stoi(str)、stol(str)、stoll(str)：将字符串转化为整数（int、long、long long）
• stof(str)、stod(str)：将字符串转化为浮点数（float、double）
• to_string(num)：将数字转化为字符串

字符串分割：

// 根据 delimiter 将字符串分为多个子串
std::vector<std::string> split(const std::string &s, char delimiter) {
    std::vector<std::string> tokens;
    std::string token;
    std::istringstream tokenStream(s);
    while (std::getline(tokenStream, token, delimiter)) {
        tokens.push_back(token);
    }
    return tokens;
}

---