检查stl容器中是否已存在值的最快方法

Question

我持有一个非常大的内存地址列表(周围400.000),需要检查一个地址是否已经存在400.000次.

一个代码示例来说明我的设置:

std::set<uintptr_t> existingAddresses; // this one contains 400.000 entries

while (true) {
    // a new list with possible new addresses
    std::set<uintptr_t> newAddresses; // also contains about ~400.000 entries

    // in my own code, these represent a new address list
    for (auto newAddress : newAddresses) {

        // already processed this address, skip it
        if (existingAddresses.find(newAddress) != existingAddresses.end()) {
          continue;
        }

        // we didn't have this address yet, so process it.
        SomeHeavyTask(newAddress);

        // so we don't process it again
        existingAddresses.emplace(newAddress);
    }

    Sleep(1000);
}

这是我提出的第一个实现,我认为它可以大大改进.

接下来我想出了一些自定义索引策略,也用于数据库.我们的想法是获取值的一部分,并使用它将其索引到自己的组集中.如果我将例如地址的最后两个数字,我将有16^2 = 256组来放置地址.

所以我最终得到这样的地图:

[FF] -> all address ending with `FF`
[EF] -> all addresses ending with `EF`
[00] -> all addresses ending with `00`
// etc...

有了这个,我只需要360在相应的集合中查找〜条目.导致〜360查找每秒完成400,000次.好多了!

我想知道是否有其他技巧或更好的方法来做到这一点？我的目标是尽可能快地将此地址查找.

Answer 1

std::set<uintptr_t>使用平衡树,所以查找时间O(log N).

std::unordered_set<uintptr_t>另一方面,它是基于散列的,查找时间为O(1).

虽然这只是一种asymptotic complexity衡量标准,意味着由于涉及的因素不一致而无法保证改进,但当集合包含400,000个元素时,差异可能会很明显.