STL
约 1276 字大约 4 分钟
2025-03-13
1 set
s.earse(it1,it2); 删除 [it1,it2) 这个区间（迭代器）对应位置的元素
iterator lower_bound( const key_type &key ); 返回一个迭代器，指向键值 >= key 的第一个元素。
iterator upper_bound( const key_type &key ); 返回一个迭代器，指向键值 > key 的第一个元素
Set 的定义：
struct T1{
int key,value;
bool operator < (const T1 &a) const {
return key<a.key;//按照升序排列
}
};
struct T2{
int key,value;
};
struct T2cmp{
bool operator () (const int &a,const int &b){
if(abs(a-b)<=k)
return false;
return a<b;
}
};
int main(){
int i,j;
set<T1> s1;
set<T2,T2cmp> s2;
set<string> ss1;//等于 set<string,less<int> > ss1; 从小到大
set<string,greater<string> > ss2;//从大到小
set<string,greater<string> > ::iterator itsey;
//set 的遍历
set<string> :: iterator it;
for(it = ss1.begin();it!=ss1.end();it++){
cout<<*it<<endl;
}
return 0;
}
Multiset
c.erase(elem) 删除与 elem 相等的所有元素，返回被移除的元素个数。
c.erase(pos) 移除迭代器 pos 所指位置元素，无返回值。2 map
mp.find(key): 在 map 中查找 key 并返回其 iterator, 找不到的话返回 mp.end() O(logn)
mp.count(key): 在 map 中找 key 的数量，由于每个 key 都是唯一的，只会返回 0 或 1
mp[key] 可以直接访问到键值队 key---value 中的 value，如果不存在，则 mp[key] 返回的是 value 类型默认构造器所构造的值，并将该键值对插入到 map 中
哈希表：
#include <unordered_map>
unordered_map3 pair
#include <utility>头文件中
pair<T1, T2> p1; //创建一个空的 pair 对象（使用默认构造），它的两个元素分别是 T1 和 T2 类型，采用值初始化。
pair<T1, T2> p1(v1, v2); //创建一个 pair 对象，它的两个元素分别是 T1 和 T2 类型，其中 first 成员初始化为 v1，second 成员初始化为 v2。
make_pair(v1, v2); // 以 v1 和 v2 的值创建一个新的 pair 对象，其元素类型分别是 v1 和 v2 的类型。
p1 < p2; // 两个 pair 对象间的小于运算，其定义遵循字典次序
// 如 p1.first < p2.first 或者 !(p2.first < p1.first) && (p1.second < p2.second) 则返回 true。
p1 == p2// 如果两个对象的 first 和 second 依次相等，则这两个对象相等；该运算使用元素的==操作符。4 vector
v.resize(n); // 把 v 的长度重新设定为 n 个元素
v.erase(unique(v.begin(), v.end()), v.end()); // 去重5 priority_queue
pq.top(): 获取优先级最高的元素 O(1)
优先队列的定义：
priority_queue<int> q1; //默认从大到小，大顶堆
priority_queue<int ,vector<int>,less<int> > q2; //降序队列，大顶堆
priority_queue<int ,vector<int>,greater<int> > q3; //升序队列，小顶堆
对于结构体定义：
struct T1{//法一 强烈推荐
int x,y;
friend bool operator < (T1 a,T1 b){
return a.x<b.x;
}
};
priority_queue<T1> q1;
struct T1{//法二
int x,y;
bool operator < (const T1 &a) const{
return x<a.x; //大顶堆
}
};
priority_queue<T1> q1;6 tuple
#include <tuple>
auto t = std::make_tuple(1, 2.5, "Hello");
// get 获取元素
auto t = std::make_tuple(1, 2.5, "Hello");
int i = std::get<0>(t); // 1
double d = std::get<1>(t); // 2.5
const char* s = std::get<2>(t); // "Hello"
// tie 解包获取元素
int i;
double d;
const char* s;
auto t = std::make_tuple(1, 2.5, "Hello");
std::tie(i, d, s) = t;
// size 获取size
auto t = std::make_tuple(1, 2.5, "Hello");
constexpr size_t size = std::tuple_size<decltype(t)>::value; // 3
// tuple_element 获取某个元素的类型
auto t = std::make_tuple(1, 2.5, "Hello");
using FirstType = std::tuple_element<0, decltype(t)>::type; // int
using SecondType = std::tuple_element<1, decltype(t)>::type; // double
// tuple_cat 连接多个tuple
auto t1 = std::make_tuple(1, 2.5);
auto t2 = std::make_tuple("Hello", 'a');
auto t3 = std::tuple_cat(t1, t2); // t3 is std::tuple<int, double, const char*, char>
// apply 将tuple中的元素作为参数传递给一个函数
void print(int i, double d, const char* s) {
std::cout << i << ", " << d << ", " << s << std::endl;
}
auto t = std::make_tuple(1, 2.5, "Hello");
std::apply(print, t); // 1, 2.5, Hello
// for_each + index_sequence 遍历并使用元素
template<typename Tuple, std::size_t... I>
void print_tuple(const Tuple& t, std::index_sequence<I...>) {
((std::cout << (I == 0 ? "" : ", ") << std::get<I>(t)), ...);
std::cout << std::endl;
}
template<typename... Args>
void print_tuple(const std::tuple<Args...>& t) {
print_tuple(t, std::index_sequence_for<Args...>{});
}
int main() {
auto t = std::make_tuple(1, 2.5, "Hello");
print_tuple(t); // 1, 2.5, Hello
return 0;
}二分
由于 set 迭代器是单向的，所以一般情况下 std::set.lower_bound() 的性能要优于 std::lower_bound()
lower_bound(begin,end,num)：二分查找第一个大于或等于 num 的数字，找到返回该数字的地址，不存在则返回 end
upper_bound(begin,end,num)：二分查找第一个大于 num 的数字
在从大到小的排序数组中，重载 lower_bound() 和 upper_bound()
lower_bound(begin,end,num,greater()): 二分查找第一个小于或等于 num 的数字
upper_bound(begin,end,num,greater()): 二分查找第一个小于 num 的数字extract (C++17)
extract 复杂度 log(size())
set::extract 可以移除某个元素
std::set<int> cont{1, 2, 3};
// Extract node handle and change key
auto nh = cont.extract(1);
nh.value() = 4;
print("After extract and before insert:", cont); // 2 3
// Insert node handle back
cont.insert(std::move(nh));
print("End:", cont); // 2 3 4map::extract 能够修改一组 <key, value> 中的 key
extract is the only way to change a key of a map element without reallocation
std::map<int, char> cont{{1, 'a'}, {2, 'b'}, {3, 'c'}};
// Extract node handle and change key
auto nh = cont.extract(1);
nh.key() = 4;
print("After extract and before insert:", cont); // 2(b) 3(c)
// Insert node handle back
cont.insert(std::move(nh));
print("End:", cont); // 2(b) 3(c) 4(a)