2

一个简单的问题，但答案对我来说并不明显：出于性能原因，从性能角度来看，我应该在以下场景中最好使用哪种地图类型（或者可能是非地图类型？）容器：

  • 键是无符号整数，
  • 插入频繁，
  • 读访问更加频繁和随机访问，
  • 使用升序键值插入项目（第一个插入的项目具有键 0，下一个键值为 1，依此类推），
  • 项目被随机删除（因此迟早键列表将有“漏洞”，因为相应的项目已被删除）。移除几乎与插入一样频繁。

我犹豫使用std::map，因为升序键顺序和频繁删除似乎意味着不断重新平衡搜索树，这对我来说似乎是对性能的浪费。

换句话说：我可以从我提前知道项目的键是什么，甚至键出现插入的顺序这一事实中获得性能吗？（不过，我不知道项目的总数。）

4

2 回答 2

4

如果您确实使用了stl::map- 即使只是为了进行分析以与哈希进行比较 - 您可以使用您的知识“项目以升序键值插入”，stl::map通过向插入提供提示来大大提高插入操作的效率称呼：

iterator insert ( iterator position_hint, const value_type& x );

...position_hint例如，其中将是插入的上一个项目的迭代器。

于 2012-10-27T08:28:30.500 回答
3

If memory is not a problem, why not use a std::vector of some custom type? You could have the fastest access times, since all elements are in order, and just save a flag if an element is removed. Consider this proxy class:

template<typename RealType>
class MyProxy {
public:
    RealType instance;
    bool isused;


    MyProxy(RealType) { /* TODO */ }
};

Which is then used within your std::vector:

std::vector<MyProxy<MyRealType> > vec;

For a lookup, you just have to check whether the index is within the bounds of the std::vector and that the isused flag is true. For removal just get the element of index i and set the flag to false. For insertion you have to push_back a new instance of MyProxy<MyType> instead of MyType.

The drawback of this approach is of course, that the std::vector is constantly growing, so you have to keep an eye on memory consumption and eventually freeing the vector, but this is possibly the fastest method for lookup, insertion and removal.

于 2012-10-27T08:23:38.500 回答