1

我正在尝试找到一种快速的输入方式，但我了解到将 STL 用于此类目的可能会很慢。

每当我收到键盘输入时，我都会触发一个回调。它创建一个对象(int _key, int _state, int _life)

每次我收到此回调时，我都会push_back将对象指向我的 std::vector;

每一帧我都会检查这个向量的顶部并删除“死”输入。

可以轮询该向量以获取当时有效的任何输入，这意味着它将被频繁搜索。

优化：

-所有内存都应该是连续的，所以虽然链接列表更适合动态分配，但我应该坚持使用 STL 的向量吗？我总是在顶部添加并从底部删除，那么我应该使用什么数据结构？

-我正在考虑有一个缓冲区（第二个向量），它不断地从回调接收新输入，然后每一帧将数据从该向量复制到我的活动输入向量的顶部。由于将轮询活动向量，这是否会提高性能，因为在循环期间添加它不会浪费时间？

基本上我试图从这个向量中尽可能多地压缩性能，我可以使用一些帮助。

4

4 回答 4

3

std::deque做最好的容器。它保证 O(1) pop_front 和 push_back()并且具有随机访问和良好程度（尽管不完全）的缓存行为。

但是，如果您绝对必须具有完全的连续性，那么您需要研究一个自定义的循环缓冲区容器（Boost IIRC 中有一个），因为 a 上的 pop_front()vector相当昂贵。

编辑：正如另一位海报所指出的，即使对于非常快速的打字员来说，键盘输入也很少见，以至于我很难相信这是您系统的瓶颈。

于 2012-12-12T13:05:27.470 回答
3

您所描述的，在一端添加数据，在另一端删除，是队列的原型描述。这是在带有类的标准库中实现的std::queue。

这个队列类是所谓的容器适配器，这意味着它使用另一个容器进行实际存储。默认情况下它使用std::deque，但该容器不会将其数据保存在连续的内存区域中。但是，您可以std::queue使用几乎任何其他标准容器声明 a ，例如std::vector（这是唯一保证将数据存储在连续内存区域中的容器）：

std::queue<int, std::vector> my_queue_with_vector;
my_queue_with_vector.push(1);
my_queue_with_vector.push(2);
my_queue_with_vector.push(3);

while (!my_queue_with_vector.empty())
{
    std::cout << my_queue_with_vector.top() << '\n';
    my_queue_with_vector.pop();  // Remove top element in the queue
}
于 2012-12-12T13:09:22.357 回答
1

听起来你想要一个std::deque. 相邻元素几乎总是在内存中连续分配，并且在开始和结束时具有恒定的时间插入和删除。

于 2012-12-12T13:00:51.350 回答
0

简短的回答：没关系。std::vector 和 std::list 可以轻松处理每秒数百万次插入操作，但大多数打字员在键盘上的输入速度不会超过每秒 10 个字符。

长答案：如果向量很小（< 100）并且存储在向量上的对象的复制/交换操作很便宜，则 push_back 和擦除通常在向量上非常便宜。用于插入 std:list 或从中删除的分配通常更昂贵。如果它成为一个问题，衡量成本。

std::deque 也有分配，如果我假设你的向量很少包含超过 10 个项目 - 所有这些项目都很便宜 - 是正确的，那么在你的情况下，根据实现可能比你的向量更昂贵。

于 2012-12-12T13:03:51.323 回答