对std::vector进行排序的更快替代方案

Question

我有一个hash_map，其中未singnedint(用户id)作为键，日期向量作为值。例如

// key - user id, value - vector of dates from 2020
hash_map<unsigned, vector<unsigned short>>;
[1] = { 14 }            // 2020/1/14
[2] = { 18, 25, 32 }    // 2020/01/18, 2020/01/25, 2020/02/01

这些向量中的值表示用户将被通知的时间，但有一个规则:你不能在一周内通知同一用户两次以上(可以在配置中更改)。为了检查是否可以向用户添加新的通知日期，我搜索与插入日期相差小于7天的第一个日期，然后检查向量中的下一个日期是否相差大于7天，如果为真，则插入一个新元素。插入之后，我对向量进行排序。每隔24小时我清除所有元素直到今天()。

问题是:我需要对值类型做一些事情，因为它使一切工作缓慢(平均而言，每天有300.000.000次更改，即相同数量的线性搜索和大约25M排序)。你知道用什么结构、数据类型或算法来摆脱sort()吗?

使用<<p> strong> unordered_set 这是个坏主意。

1. 与unordered_set相比，如果向量中的线性搜索少于100个元素，则速度更快，并且通常每个人的日期不超过5个。
2. 我不能允许浪费3倍的RAM来存储这样的结构。
3. 我不能对齐unordered_set的64Bytes L1处理器缓存

注。我的哈希映射占用470mb内存用于映射和键，加上304mb用于值。

Answer 1

您可以使用滑动窗口来跟踪过去7天的通知。可以使用"unsigned char"作为位向量，位0是今天，位1是昨天，以此类推。

unsigned char last7Days= 0;
// if 0 or 1 notification in the last week, add one today
if (count_bits(last7Days) < 2) last7Days |=1;
// update notifications each day
last7Days = (last7Days << 1) & 0x7F; // shift and mask 7 days