我有一个容器需要保存一个 ID(ID 是唯一的)和一个数据值。我还需要按顺序保存这些 ID。这些变量的元组将通过 ID 查找，然后按顺序处理直到找到元素，即我并不总是想处理整个容器。为此，我有一个简单的解决方案
// ordinal, { ID, data }
std::map<int64, pair<int64, data_t> >
我将首先通过遍历并将搜索值与该对的第一个字段进行比较来搜索 ID，然后我将处理所有元素直到该位置。有没有更好的方法(根据我的计算，这是 O(2n))？
最佳答案
你可以交换ordinal和 ID并将它们存储在 map 的 map 中:
// ID ordinal data
std::unordered_map<int64, std::map<int64, data_t>> container;
这将允许您找到带有 ID 的元素给定和最小可能 ordinal在 O(log N)时间:
container[ID].begin(); // Has ID given, smallest possible ordinal and corresponding data
// Equal to container[ID].end() if not found
之后，你可以比较ordinal找到的对象达到给定的阈值。
UP:当然，如果你的ID s 是唯一的，嵌套的 map 中不需要: 你可以只使用 std::unordered_map<int64, std::pair<int64, data_t>> .
关于C++:具有两个相关键的快速结构，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40997659/