1

我需要一个排序和索引的容器。我想基于 std:set 或 std::vector 构建它。通过使用 set，我需要昂贵的 std::distance 来计算其元素的索引。通过使用向量，我知道添加或删除元素是昂贵的。假设我的元素是一个指针（小对象）。我知道两个操作的复杂性是相同的。但是哪个更快？谢谢。

4

3 回答 3

3

如果您需要一个支持排序顺序和按索引查找的数据结构，您绝对应该查看order statistic tree，它是专门为支持这些操作而设计的数据结构。它支持在 O(log n) 时间内插入和删除，在 O(log n) 时间内查找元素的索引，以及在 O(log n) 时间内按值或按索引查找，因此它应该比向量或集合方法。

不幸的是，STL 没有构建它的顺序统计树，因此您必须搜索第三方库（这个较早的问题和答案提供了一个示例）。也就是说，您应该期望从订单统计树中获得的加速应该值得投资。

希望这可以帮助！

于 2013-01-02T18:41:53.173 回答
2

根据你们的建议，我测量了它作为底部代码（添加了flat_set）。调试版本的结果是

设置：4.720976s 墙，4.711230s 用户 + 0.000000s 系统 = 4.711230s CPU（99.8%）（也测试了 set::insert，这需要很少的时间）

矢量：1.407571s 墙，1.404009s 用户 + 0.000000s 系统 = 1.404009s CPU (99.7%)

对于 flat_set：0.327714s 墙，0.327602s 用户 + 0.000000s 系统 = 0.327602s CPU (100.0%)

并且发布版本（我需要写出结果以让编译器优化不会过度杀伤我的代码）给每个版本大约 10 倍的加速。

我的结论是向量快 2-3 倍，而 boost flat_set 是最好的。对于少于数百个的条目数（例如 200 个），flat_set 插入并不比 std::set 慢（即无索引计算）。

int N = 10000;
{
    boost::timer::auto_cpu_timer t;
    std::set<int> s;
    for (int i = 0; i < N; ++i)
    {
        auto it = s.insert(i);
        int index = std::distance(s.begin(), it.first);
    }
}

{
    boost::timer::auto_cpu_timer t;
    std::vector<int> v;
    for (int i = 0; i < N; ++i)
    {
        v.insert(v.begin(), i);
    }
}

{
    boost::timer::auto_cpu_timer t;
    boost::container::flat_set<int> s;
    for (int i = 0; i < N; ++i)
    {
        auto it = s.insert(-i); // negative sign is used to make insertion
                                // (at the beginning) expensive
        int index = std::distance(s.begin(), it.first);
    }
}
于 2013-01-02T18:39:10.523 回答
0

分离存储和索引：

有一个整数向量 {I}，它索引你的对象类型的存储向量，{T}。

{I} 通过比较它在 {T} 中指向的对象进行排序。对 {I} 的插入/删除比对 {T} 的插入/删除便宜。

每当您将新项目添加到 {T} 向量时，都会将其索引插入到已排序的 {I} 中。

当您删除一个项目时，删除 {I} 中的索引，但您可以保持 {T} 中的对象不变，只需将刚刚删除的索引 push_back 到重用向量 {I'} 中。下次添加新项目时，可以将 {I'} 中的索引 pop_back 并重用存储。

如果您知道曾经使用过的项目数，您可以在启动时在 {T} 上调用 resize() 以避免在运行时（重新）分配。

这种方法类似于使用指针向量，优点是动态分配更少，缓存更友好，因为对象存储在连续内存中。

于 2013-01-02T19:13:03.247 回答