1

I am looking for the best data structure for C++ in which insertion and deletion can take place very efficiently and fast.

Traversal should also be very easy for this data structure. Which one should i go with? What about SET in C++??

4

4 回答 4

5

链表提供了任意元素的有效插入和删除。这里的删除是迭代器的删除，而不是值的删除。遍历速度相当快。

出队仅在末端提供有效的插入和删除，但它们比链表更快，并且遍历也更快。

仅当您想按元素的值查找元素（例如删除它们）时，集合才有意义。否则检查重复的开销以及保持排序的开销将被浪费。

于 2012-07-04T10:01:28.867 回答
1

这取决于您要放入此数据结构中的内容。如果项目是无序的或者你关心它们的顺序，可以使用 list<>。如果您希望它们按排序顺序排列，则 set<> 或 multiset<> （后者允许多个相同的元素）可能是另一种选择。

list<> 通常是一个双链表，所以插入和删除可以在恒定时间内完成，只要你知道位置。遍历所有元素也很快，但访问指定元素（按值或按位置）可能会变慢。

set<> 及其家族通常是二叉树，因此插入、删除和搜索元素大多是在对数时间内（当您知道在哪里插入/删除时，它是常数时间）。遍历所有元素也很快。

（注意：boost 和 C++11 都有基于哈希表的数据结构，这也是一个选项）

于 2012-07-04T10:00:58.553 回答
1

我会说一个链接列表，具体取决于您的删除是否是具体的和经常的。关于它的迭代器。

于 2012-07-04T10:36:37.510 回答
0

我突然想到，你需要一棵树。

我不确定确切的结构（因为您没有提供详细信息），但是如果您可以将数据放入二叉树中，则可以在搜索、删除和插入元素时达到不错的速度（平均O(logn)和O(n)最坏情况）。

请注意，我在这里谈论的是数据结构，您可以通过不同的方式实现它。

于 2012-07-04T10:01:42.273 回答