c++ - 在c++中搜索合适的数据结构

Question

建议一个合适的数据结构(在 C++ 中)，以便解决以下提到的目的:

1. 在末尾插入一个元素。
2. 从末尾读取并删除一个元素。
3. 从头开始读取并删除一个元素。
4. 找出特定元素是否存在。

现在我正在使用 vector ..但是查找特定元素是否存在在 vector 中具有很大的时间复杂度，因为我的元素没有排序。

是否有比 vector 更好的数据结构来完成此任务..如果是..那么是哪一个，请举个例子。

Answer 1

一种可能是使用 std::set或 std::unordered_set这基本上是一个哈希表，并自己维护元素之间的顺序。这将为您提供 O(log(n)) 或分摊的 O(1) 查找复杂性和在开始/结束时不断插入/删除。在 Java 中，这称为 LinkedHashSet。不幸的是，STL 不提供这种开箱即用的数据结构，但它应该很容易在 set/unordered_set 或 map/unordered_map 之上实现。

这里有一段代码可以说明这个想法:

template <typename T>
class linked_set {
 private:
  // Comparator of values with dereferencing.
  struct value_deref_less {
    bool operator()(const T *lhs, const T *rhs) const {
      return *lhs < *rhs;
    }
  };

  typedef std::set<const T*, value_deref_less> Set;
  Set set_;              // Used for quick lookup
  std::deque<T> store_;  // Used for ordered storage. deque is used instead of
                         // vector because the former doesn't invalidate
                         // pointers/iterators when elements are pushed.

 public:
  void push_back(const T& value) {
    store_.push_back(value);
    set_.insert(&store_.back());
    // TODO: handle the case of duplicate elements.
  }

  // TODO: better provide your own iterator.
  typedef typename Set::iterator iterator;

  iterator find(const T& value) { return set_.find(&value); }

  // ...
};