混合载体/列表容器？

Question

我需要一个具有向量和列表属性的容器.我需要快速随机访问容器中的元素,但我还需要能够删除容器中间的元素而不移动其他元素.我还需要能够迭代容器中的所有元素,并一目了然(没有迭代)容器中有多少元素.

经过一番思考,我已经想通了,我怎么可以创造这样的容器,使用载体为基础的容器,和包装一个结构中还包含域记录元素是否有效范围内的实际存储的数据,以及指针指向向量中的next/previous有效元素.结合一些超载等,听起来应该是相当透明的并满足我的要求.

但在我真正开始创建另一个容器之前,我很好奇是否有人知道实现这个问题的现有库？我宁愿使用一些有用的东西,而不是花时间调试自定义实现.我查看了Boost库(我已经在使用它),但是没有在那里找到它.

Answer 1

如果顺序无关紧要,我只会使用哈希表将整数映射到指针. std::tr1::unordered_map<int, T *>(或者std::unordered_map<int, unique_ptr<T>>如果C++ 0x没问题).

哈希表的元素可以移动,这就是你需要使用指针的原因,但它将支持非常快速的插入/查找/删除.迭代也很快,但元素将以不确定的顺序出现.

或者,我认为您可以将自己的想法实现为a std::vector和a 的非常简单的组合std::list.只需保持a list<T> my_list和a vector<list<T>::iterator> my_vector.要添加对象,请将其推到背面,my_list然后将其迭代器推到my_vector.(设置一个迭代器my_list.end()并递减它以获取最后一个元素的迭代器.)要查找,请在向量中查找并取消引用迭代器.要删除,请从列表中删除(您可以通过迭代器执行此操作)并将向量中的位置设置为my_list.end().

std::list 保证删除它们时不会移动元素.

[更新]

我感到很有动力.首先通过一个实现:

#include <vector>
#include <list>

template <typename T>
class NairouList {
public:
  typedef std::list<T> list_t;
  typedef typename list_t::iterator iterator;
  typedef std::vector<iterator> vector_t;

  NairouList() : my_size(0)
  { }

  void push_back(const T &elt) {
      my_list.push_back(elt);
      iterator i = my_list.end();
      --i;
      my_vector.push_back(i);
      ++my_size;
  }

  T &operator[](typename vector_t::size_type n) {
      if (my_vector[n] == my_list.end())
          throw "Dave's not here, man";
      return *(my_vector[n]);
  }

  void remove(typename vector_t::size_type n) {
      my_list.erase(my_vector[n]);
      my_vector[n] = my_list.end();
      --my_size;
  }

  size_t size() const {
      return my_size;
  }

  iterator begin() {
      return my_list.begin();
  }

  iterator end() {
      return my_list.end();
  }

private:
  list_t my_list;
  vector_t my_vector;
  size_t my_size;
};

它缺少执行触摸的一些品质...喜欢,你可能想要更多的错误检查(如果我删除的内容相同的元素两次？)也许有些const版本operator[],begin(),end().但这是一个开始.

也就是说,对于"几千个"元素,地图可能至少也会起作用.一个好的经验法则是"在你的探查器告诉你之前,不要优化任何东西".