c++ - 哪个 STL 类用于 Rand-In-First-Out 缓冲区

Question

我目前有一个大集群(50 多台计算机)处理工作包。然后，所有这些工作包结果都由 Controller 计算机收集。

因此，假设数据以半随机方式到达，并且逐渐增长:

0,2,3,8,7,1,4,9,10,11,6, ...

然后我必须按顺序将数据转储到文件中。由于工作包超过 100M，我会在缓冲区中准备好下一个后立即转储它们。

我实际上正在为这个“Random-Input-First-Output”使用 std::map，示例:

std::map<int, DataStruct> buffer;

long long next_work = 0;
while(next_work != 100000000){
    fill_buffer(buffer); //This method fills the buffer from the processing elements

    if(buffer.find(next_work) != buffer.end()){
        dump_to_file(buffer[next_work]); // Dumps it to file
        buffer.erase(next_work++);
    }
};

此缓冲区有时(由于网络延迟、PC 延迟、断开连接等原因)会增长到 100000 多个元素，这会减慢操作速度。所以，我想知道 STL 是否有更好的类来处理此类操作。

在这里使用 std::map 是否合适？

是否有更好的/CPU 效率更高的方法？(我真的不在乎它是否内存效率高)

Answer 1

由于缓冲区中没有小于 next_work 的作业，因此您的 map 只能包含这样的元素作为其第一个元素。您可以改为使用 begin() 来访问您的迭代器，在恒定时间内获取第一个元素(然后测试它是否是您想要的)。但是仍在减慢速度的是插入，它仍然是缓冲区当前大小的对数。

另一种关联数据结构是 HashMap 。它支持预期的恒定时间插入和查找。它不是按键排序，但由于您只需要查找确切的键，这不会成为问题。

如果您的编译器支持 C++11(并且您不需要支持 C++11 之前的编译器)，则有 std::unordered_map .可能只需更换类(class)即可解决所有问题。也许您需要调整对数据结构的其他访问，您没有在代码片段中显示，即我们不知道您如何在 fill_buffer 中填充您的数据结构。

对于 C++03，你可以试试 boost::unordered_map .