为什么std :: list支持在O（1）中删除？ [英] Why doesn't std::list support remove in O(1)?

问题描述

嗨！

我想知道为什么C ++ 0x11中的默认std :: list不支持在O（1）时间内删除节点有什么特别的原因。我可以使用一个哈希集来实现O（1）删除时间，但是然后添加一个哈希函数的常量，这实际上是不必要的。



当前删除函数需要O（n），我理解它是如何实现的，但不是为什么人们无法访问节点并直接删除它们，因为你已经有了指向节点的指针（因此也是下一个节点）。但是我自己可以实现它，但发现在我看来，标准库中缺少这样一个基本功能，这很奇怪。我怀疑它与内存管理原则有关，我是对的。



感谢所有帮助，如果我是，请随时纠正我错了，我不会宣称我是C ++专家，但我有很多Java和C＃的经验。

解决方案

如果可以使用hashset，它不再是一个列表了。哈希集不允许重复，但列表允许它们;另外，list支持某些项目顺序和索引访问，这是O（1）是最快的。 （你可以通过使用列表的哈希集来组合这两个功能，其中每个列表代表所有重复项，但它几乎没有实际意义:-)。）



现在，你不清楚时间计算复杂度你的意思是什么问题。如果要按值删除元素，操作首先需要按值搜索项目;搜索本身将是O（N）。这是因为首先要找到节点;并且找到它的唯一方法是按顺序测试项目，直到找到项目。



但是如果你已经拥有该项目索引的预先存在的知识要删除，这是不同的故事，将取决于具体的实现。根据 此规范 ，这应该是双向链表的。在这种情况下，删除时间复杂度应为O（1）。



如果列表实现基于数组，则删除仍将取决于大小列表中的元素，因为被删除后的元素应该全部重新定位以填补产生的空白。

-SA

Hi!
I wonder if there is any particular reason for why the default std::list in C++0x11 doesn''t support removal of a node in O(1) time. I could just use a hashset and achieve O(1) removal time but then a constant for the hash function is added which isn''t really necessary.

The current remove function requires O(n) and I understand how it''s implemented but not why one can''t access the nodes and just remove them directly since you then already would have the pointer to the node (and therefore also to previous and next node). However I can implement it myself but find it rather strange that such a basic function in my opinion, is missing from the standard library. I suspect it has to do with the memory management principles, I''m I right.

Thankful for all help, feel free to correct me if I''m wrong and I don''t proclaim I''m an expert in C++ but I have a lot of experience from Java and C#.

解决方案

If it could use a hashset, it would not be a list anymore. A hashset does not allow duplicates, but the list does allow them; also, list supports certain item order and access by index, which is O(1) is is the fastest. (You can combine those two features by, say, using a hashset of lists, where each list represents all duplicates, but it hardly makes much practical sense :-).)

Now, it''s not clear the time computational complexity of what problem do you mean. If you want to remove the element by its value, the operation will first need the search of the item by its value; and the search itself will be of O(N). This is because the node should first be found; and the only way to find it is the test the items sequentially, until the item is found.

But if you already have the preexisting knowledge of the index of the item to be removed, this is the different story, and will depend on a particular implementation. According to this specification, this should be a doubly-linked list. In this case, the removal time complexity should be of O(1).

If the list implementation is based on the array, the removal will still depend on the size of the list, because the elements following the one being removed should be all relocated to fill the gap produced.

—SA

这篇关于为什么std :: list支持在O（1）中删除？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！