2

建议一个合适的数据结构（在 C++ 中），以便解决下面提到的目的：

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

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

有没有比向量更好的数据结构来完成这个..如果是..那么是哪一个，请举个例子。

4

6 回答 6

3

一种可能性是使用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); }

  // ...
};
于 2012-07-03T21:47:00.053 回答
2

You won't be able to have both fast insertions at the two sides AND fast searches with the same container, at least if you restrict the possibilities to the STL. More exotic non-standard containers may help.

But the approach I generally choose in these cases is to use two containers. For storing the elements, the obvious option is std::deque. For searches, make a std::map<K,V> in which V is an iterator for the deque. Since insert/delete in deques does not invalidate iterators that are not involved, it should be OK IF you always remember to synchronize the map and the deque (i.e. when you do an insert or delete on the deque, do that also on the map). Another simpler/safer option, instead of using iterators - if after a search in the map you just need the element found (you don't need to visit nearby elements, etc.) - is to have in both the deque and the map smart pointers to the actual objects (more specifically, shared_ptr). Again, you have to be careful to keep both in sync; although it won't be as catastrophic if they loose sync, probably the consistency of your program will be compromised, of course.

struct MyItem
{
    std::string name;
    int something;
    int another;
    MyItem(const std::string &name_, int something_, int another_)
        :name(name_), something(something_), another(another_) {}
};

class MyContainer
{
    public:
        typedef std::shared_ptr<MyItem> MyItemPtr;

        void push_front(MyItemPtr item)
        {
            deque.push_front(item);
            assert(map.find(item->name) == map.end());
            map[item->name] = item;
        }
        void push_back(MyItemPtr item)
        {
            deque.push_back(item);
            assert(map.find(item->name) == map.end());
            map[item->name] = item;
        }
        MyItemPtr pop_front()
        {
            item = deque.front();
            deque.pop_front();
            map.erase(item->name);
            return item;
        }
        MyItemPtr pop_back()
        {
            item = deque.back();
            deque.pop_back();
            map.erase(item->name);
            return item;
        }
        MyItemPtr find(const std::string &name)
        {
            std::map<std::string, MyItemPtr>::iterator iter = map.find(name);
            if (iter == map.end())
                return MyItemPtr();
            else
                return iter->second;
        }

    private:
        std::deque<MyItemPtr> deque;
        std::map<std::string, MyItemPtr> map;
};

To use it:

MyContainer container;

MyContainer::MyItemPtr a(new MyItem("blah", 1, 2));
container.push_back(a);
MyContainer::MyItemPtr b(new MyItem("foo", 5, 6));
container.push_front(b);

MyContainer::MyItemPtr f = container.find("blah");
if (f)
    cout << f->name << ", " << f->something << ", " << f->another;
于 2012-07-03T21:59:29.483 回答
1

您应该从 a 开始，std::map看看对数复杂度是否合适。

B+Tree 会稍微复杂一些，需要您自己的实现或研究才能找到开源实现。但考虑到您引用（搜索）的要求和痛点，如果std::map仍然证明不足，这是一个合理的选择。

例如，您可以将一个元素的值映射到它的迭代器 astd::list中。所有操作都是 O(lg n) 和std::map.

于 2012-07-03T21:37:29.170 回答
1

您可以保留vector，也可以使用 astd::set进行快速查询。

该集合不足以从开头/结尾删除元素，因为您并不真正知道您插入的第一个/最后一个元素。您可以保留对这些元素的引用，但为了支持删除，您将需要下一个元素，依此类推，这会降级为使用更多容器。

于 2012-07-03T21:45:52.543 回答
0

If there is a lot of insert/delete a linked list would be more appropriate.
Beware that a linked list (single or double) will have quite an overhead (usually the size of a pointer, but implementation vary).

The standard template library offers you std::list.

于 2012-07-03T22:00:01.113 回答
0

使用std::deque. 这是一个双端队列，它也用作标准接口的容器，例如std::stack.

它通常使用准链表实现，并且在边缘处的插入和删除具有分摊的 O(1) 时间复杂度。

于 2012-07-03T21:36:38.433 回答