C++中最快的动态数据结构

-2

我有一个任务，主要是在C++中增加或删除数组中的元素。由于数组不是动态的，但对它们的操作速度非常快，所以我一直在寻找一种动态数据结构，它几乎和运行速度一样快。我一直在考虑std::vector，但由于它是预定义的，而且非常庞大，所以我担心对我而言至关重要的操作时间。任何人都可以向我提供一些关于您的观点的信息吗？我会很高兴得到您的帮助！C++中最快的动态数据结构

编辑：

我真的很抱歉，我没有列入我的问题的所有重要的一点;下面我想尝试添加更多的信息：

我会遍历结构多次的元素和访问它们以随机的方式使操作上的元素在每一个可能的位置是可能的
我认为，将会（取决于测试提供的）在数据结构中的元素以及其“边缘”附近进行许多操作。

我相信这将有助于我的帖子更清晰，更具体，因此对他人更有用。

谢谢你所有的答案！

来源

2014-03-26 musztard2000

向量通常速度一样快，但问题是，您在哪里插入/删除这些元素？ – chris

从数组末尾添加或删除数据非常缓慢，矢量只是使用数组作为基础结构。 – Dukeling

+1 @chris，你需要提供更多信息。另外，基准测试可能是可以选择的。 –

参见Mikael Persson的‘容器选择’图：在STL执行了将被用于不同的原因

http://www.cim.mcgill.ca/~mpersson/pics/STLcontainerChoices.png

来源

2014-03-26 19:01:35

@JodyHagins：我在你的回答中提到你最后一段。 –

[这里]（http://www.cim.mcgill.ca/~mpersson/pics/STLcontainerChoices.png）是我制作的另一个类似的流程图。我不认为这是无可争议的..这只是我的承担。 –

@MikaelPersson：这很好，我可以开始使用它吗？ –

的不同的数据结构。因此，结构在结构的开始，中间或结束或者结构元素的随机访问时的插入/删除速度不同。

来源

2014-03-26 19:04:02 Veritas

一个很好的STL容器的简短的对比：

http://john-ahlgren.blogspot.com/2013/10/stl-container-performance.html

如果可以让你使用一个关联数组，地图至少保证的O插入/查找时间（log n）的其对于大量的数据/大量的插入和删除，比非向后插入的向量对O（n）的保证要快得多。

不知道他们将在这里还是不行，这个环节也说明基准的一些图表使用几个不同的容器随机插入/删除/搜索/填充/排序等：

http://www.baptiste-wicht.com/2012/12/cpp-benchmark-vector-list-deque/

最后，从一个流程图，这样可以帮助你的容器上决定：

In which scenario do I use a particular STL container?

虽然并不完美，但它仍然可能会变成一个向量是你最好的选择。

来源

2014-03-26 19:07:38 Instinct

使用数组实现的链表是否满足您的需求？

class AList 
{ 
    public: 

     AList() 
     { 
     for (int = 0; i != 256; ++i) 
     { 
      nodes[i].prev = (i-1+256)%256; 
      nodes[i].next = (i+1)%256; 
     } 
     } 

     int const& operator[](int index) 
     { 
     // Deal with the case where nodes[index].isSet == false 
     return nodes[index].data; 
     } 

     // Not sure what the requirements are for adding 
     // and removing items from the list. 
     // 
     // add(); 
     // remove(); 

    private: 

     struct Node 
     { 
     Node() : data(0), prev(0), next(0), isSet(false) {} 

     int data; 
     unsigned char prev; 
     unsigned char next; 
     bool isSet; 
     }; 

     Node nodes[256]; 
};

来源

2014-03-26 20:17:20

C++中最快的动态数据结构

回答

相关问题