c++ - 挿入と削除に最適なC++のデータ構造/コンテナ

Question

挿入と削除を非常に効率的かつ高速に実行できるC++に最適なデータ構造を探しています。

このデータ構造では、トラバーサルも非常に簡単である必要があります。どちらを使うべきですか？C ++のSETはどうですか？

Answer 1

A linked list provides efficient insertion and deletion of arbitrary elements. Deletion here is deletion by iterator, not by value. Traversal is quite fast.

A dequeue provides efficient insertion and deletion only at the ends, but those are faster than for a linked list, and traversal is faster as well.

A set only makes sense if you want to find elements by their value, e.g. to remove them. Otherwise the overhead of checking for duplicate as well as that of keeping things sorted will be wasted.

Answer 2

あなたが削除しているのかどうかに応じて、リンクリストは具体的で頻繁にあると言えます。それについてのイテレータ。

Answer 3

It depends on what you want to put into this data structure. If the items are unordered or you care about their order, list<> could be used. If you want them in a sorted order, set<> or multiset<> (the later allows multiple identical elements) could be an alternative.

list<> is typically a double-linked list, so insertion and deletion can be done in constant time, provided you know the position. traversal over all elements is also fast, but accessing a specified element (either by value or by position) could become slow.

set<> and its family are typically binary trees, so insertion, deletion and searching for elements are mostly in logarithmic time (when you know where to insert/delete, it's constant time). Traversal over all elements is also fast.

(Note: boost and C++11 both have data structures based on hash-tables, which could also be an option)

Answer 4

It occurs to me, that you need a tree.

I'm not sure about the exact structure (since you didnt provide in-detail info), but if you can put your data into a binary tree, you can achieve decent speed at searching, deleting and inserting elements ( O(logn) average and O(n) worst case).

Note that I'm talking about the data structure here, you can implement it in different ways.