该文件说std::list效率低下:
std :: list是一个非常低效的类,很少有用.它为插入其中的每个元素执行堆分配,因此具有极高的常数因子,特别是对于小数据类型.
评论:这让我感到惊讶.std::list是一个双向链表,所以尽管它的元件结构效率低下,它支持插入/删除在O(1)的时间复杂度,但这种功能在此引用的段落完全忽略.
我的问题:说我需要一个连续的小尺寸均匀元素的容器,这种容器应支持元素插入/为O删除(1)复杂性和不并不需要随机存取(虽然支持随机访问是好的,它不是必须的这里).我也不希望堆分配为每个元素的构造引入高常量因子,至少当元素的数量很小时.最后,只有在删除相应的元素时,迭代器才会失效.显然我需要一个自定义容器类,它可能(或可能不)是双向链表的变体.我该如何设计这个容器？
如果无法实现上述规范,那么也许我应该有一个自定义内存分配器,比如说,指针分配器？我知道std::list将分配器作为其第二个模板参数.
编辑:我知道从工程的角度来看,我不应该太关心这个问题 - 足够快就足够了.这只是一个假设的问题,所以我没有更详细的用例.随意放松一些要求!
编辑2:据我所知,O(1)复杂度的两种算法由于其常数因子的不同而具有完全不同的性能.
c++ stl linked-list abstract-data-type dynamic-memory-allocation
我只是好奇Haskell中列表的一些确切的实现细节(GHC特定的答案很好) - 他们是天真的链接列表,还是他们有任何特殊的优化？进一步来说:
length和(!!)(例如)必须遍历列表？length两次,它是否必须迭代两次)？fib = 1:1:zipWith (+) fib (tail fib),是否会递归计算每个值,还是依赖于先前的计算值？)任何其他有趣的实施细节将不胜感激.提前致谢!
为什么我们需要一个"循环链接列表"(单一或双重)数据结构？
通过简单的链接列表(单独或双重)可以解决哪些问题？
当我们可用的唯一信息是指向要删除的节点的指针而不是指向前一节点的指针时,是否可以删除单个链表中的中间节点？删除后,前一节点应指向旁边的节点删除节点.
我开始在我的一些C#算法中使用一些LinkedList而不是Lists来希望加速它们.但是,我注意到他们感觉速度慢了.像任何优秀的开发者一样,我认为我应该尽职尽责并验证我的感受.所以我决定测试一些简单的循环.
我认为用一些随机整数填充集合应该就足够了.我在调试模式下运行此代码以避免任何编译器优化.这是我使用的代码:
var rand = new Random(Environment.TickCount);
var ll = new LinkedList<int>();
var list = new List<int>();
int count = 20000000;
BenchmarkTimer.Start("Linked List Insert");
for (int x = 0; x < count; ++x)
ll.AddFirst(rand.Next(int.MaxValue));
BenchmarkTimer.StopAndOutput();
BenchmarkTimer.Start("List Insert");
for (int x = 0; x < count; ++x)
list.Add(rand.Next(int.MaxValue));
BenchmarkTimer.StopAndOutput();
int y = 0;
BenchmarkTimer.Start("Linked List Iterate");
foreach (var i in ll)
++y; //some atomic operation;
BenchmarkTimer.StopAndOutput();
int z = 0;
BenchmarkTimer.Start("List Iterate");
foreach (var i in list)
++z; //some atomic operation; …在今天的一次采访中,我被问到了这个问题.
除了回答清单以及向前和向后遍历之外,还有一些"基本面",面试官一直在强调.我放弃了,当然在采访后做了一些研究.似乎插入和删除在双链表中比单链表更有效.我不太确定如何对双链表更有效,因为很明显需要更多的引用才能改变.任何人都可以解释背后的秘密吗？我老老实实地进行了相当多的研究,并且无法理解我的主要麻烦是双链表仍然需要进行O(n)搜索.
链接列表和BinarySearchTree之间的主要区别是什么？BST只是维护LinkedList的一种方式吗？我的导师谈到了LinkedList,然后讨论了BST,但没有比较它们或者没有说何时更喜欢一个而不是另一个.这可能是一个愚蠢的问题,但我真的很困惑.如果有人能够以简单的方式澄清这一点,我将不胜感激.
language-agnostic linked-list binary-search-tree data-structures
如何查找单链表是循环/循环还是循环？我试图搜索但找不到满意的解决方案.如果可能,您能提供伪代码或Java实现吗？
例如:
1→交通3→交通5→交通71→交通45→交通7→交通5,其中第二个5实际上是列表的第三个元素.
我们被赋予了从头开始创建LinkedList的任务,并且绝对没有给出读数来指导我们这个由migrane引起的任务.此外,所有在线似乎只使用Java内置的LinkedList方法和东西.无论如何,链接列表在使用Java的默认内容时非常有意义,但是从头开始创建它没有任何意义.可以说我有
public class LinkedList {
private LinkedList next;
private final String word;
// constructor
public LinkedList(String word, LinkedList next) {
this.word = word;
this.next = next;
}
因此神奇地我们有一个链表.到底是怎么回事？我是如何创建这样的链接列表的？这是如何运作的？我应该编写一个append方法,将给定的String word参数添加到thislinkedlist的末尾.我试着看看内置java链接列表类的addLast内置方法,但它对我没有帮助,因为我真的不明白发生了什么.任何人都在乎帮助我:)
我正在尝试打印链接文本中提到的单链表的列表.它工作,但我得到编译器警告:
Initialization discards qualifiers from pointer target type
(关于start = head的声明)和
return discards qualifiers from pointer target type
(在返回语句中)在此代码中:
/* Prints singly linked list and returns head pointer */
LIST *PrintList(const LIST *head)
{
LIST *start = head;
for (; start != NULL; start = start->next)
printf("%15s %d ea\n", head->str, head->count);
return head;
}
我正在使用XCode.有什么想法吗？