STL常用组件
[toc]
函数
fill
需要 algorithm fill速度和手动for赋值基本相同
1
2
3
4
// 将a在[2,5)区间赋值为3
fill(a+2,a+5,3);
// 相比于memset, 它可以赋值任何数, 也可以对容器使用.
fill(v.begin(),v.end(),5);
黑科技
自定义hash
网上流行的一个简单实现如下
1
2
3
4
5
6
7
8
9
10
11
12
struct pair_hash
{
template<class T1, class T2>
std::size_t operator() (const std::pair<T1, T2>& p) const
{
auto h1 = std::hash<T1>{}(p.first);
auto h2 = std::hash<T2>{}(p.second);
return h1 ^ h2;
}
};
unordered_map<pair<int, bool>, int, pair_hash> Map;
但是根据 这个博客 , 发现这个方法碰撞的很频繁, 不合理
所以就有如下的方案(但是太臃肿了)
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
// from boost (functional/hash):
// see http://www.boost.org/doc/libs/1_35_0/doc/html/hash/combine.html template
template <typename T>
inline void hash_combine(std::size_t &seed, const T &val) {
seed ^= std::hash<T>()(val) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
// auxiliary generic functions to create a hash value using a seed
template <typename T> inline void hash_val(std::size_t &seed, const T &val) {
hash_combine(seed, val);
}
template <typename T, typename... Types>
inline void hash_val(std::size_t &seed, const T &val, const Types &... args) {
hash_combine(seed, val);
hash_val(seed, args...);
}
template <typename... Types>
inline std::size_t hash_val(const Types &... args) {
std::size_t seed = 0;
hash_val(seed, args...);
return seed;
}
struct pair_hash {
template <class T1, class T2>
std::size_t operator()(const std::pair<T1, T2> &p) const {
return hash_val(p.first, p.second);
}
};
using namespace std;
using ll = long long;
int main() {
unordered_map<pair<ll, ll>, ll, pair_hash> slopeCount;
unordered_set<pair<ll, ll>, pair_hash> seen;
return 0;
}
优先队列重载
在优先队列的声明中, 传入一个结构体, 可以理解为重载小于号. 而优先队列默认是从大到小的. 所以
1
2
3
4
5
6
7
8
9
10
11
// 最大值优先 等价于 递减 等价于 less<T> 等价于 a < b
struct cmp1{
bool operator ()(int &a,int &b){
return a>b;//最小值优先
}
};
struct cmp2{
bool operator ()(int &a,int &b){
return a<b;//最大值优先
}
};
