矢量与动态数组相比，速度有很大差异吗？

现在我正在编写解决车辆路径问题的一些代码。为此，一个重要的决定是选择如何对解决方案进行编码。一个解决方案包含几条路线，每个车辆一个。每条路线都有客户访问顺序，路线负载和路线长度。要对解决方案信息进行修改，我还需要快速找到一些信息。例如，
哪条路线是客户所在？
路线有哪些客户？
路线中有多少个节点？
节点前面或后面有什么节点？矢量与动态数组相比，速度有很大差异吗？

现在，我想使用以下结构来保持解决方案。

struct Sol 
{ 
    vector<short> nextNode; // show what is the next node of each node; 
    vector<short> preNode; //show what is the preceding node 
    vector<short> startNode; 
    vector<short> rutNum; 
    vector<short> rutLoad; 
    vector<float> rutLength; 
    vector<short> rutSize; 
};

每个向量的通用大小是实例相关的，在200-2000之间。

我听说有可能使用动态数组来完成这项工作。但在我看来，动态数组更复杂。必须找到内存并释放内存。这里我的问题是双重的。

如何使用动态数组来实现相同的目的？如何定义结构或类，以便内存位置和发布可以轻松处理？

使用动态数组会比使用矢量更快吗？假设解决方案结构需要被访问百万次。

来源

2011-10-07 Jackie

为什么你有一个成员数组的结构，而不是一个具有成员的结构数组？后者不那么容易混淆，不易出错并且速度更快。 –

每个阵列中的信息是不同的，而不是相同的项目 – Jackie

由于后者基本上是前者的一个非常薄的包装，因此很难在动态数组和矢量之间看到可观的性能差异。另外请记住，使用vector将显着减少错误。然而，可能存在的情况是一些信息被更好地存储在不同类型的容器中，例如，在std::map。以下内容可能会引起您的兴趣：What are the complexity guarantees of the standard containers?

重要的是对使用的容器类型进行一些思考。然而，当谈到微型优化（例如向量与动态数组）时，最好的策略是首先对代码进行剖析，然后只关注代码中证明是真实的部分 - 而不是假设 - 的瓶颈。

来源

2011-10-07 16:48:08 NPE

感谢您的答案。我喜欢使用矢量，但如果使用动态数组可以使代码更快，那么我会选择它。这是我主要希望知道的。有没有我们用于比较的开源代码？ – Jackie

它不会更快...... – DanDan

向量的代码很可能比你自己写的动态数组代码更好，更高效。只有在分析显示在vector上花费了大量时间时，我才会考虑编写自己的容易出错的替换。另请参见Dynamically allocated arrays or std::vector

来源

2011-10-07 16:54:21

我正在使用MSVC，并且实现看起来尽可能快。

访问通过操作[]数组是：

return (*(this->_Myfirst + _Pos));

，你会得到与动态内存这是一样快。

您将得到的唯一开销是在内存中使用一个向量，它似乎创建了一个指向该向量开始，向量结束和当前序列结束的指针。如果您使用的是动态数组，那么这只是比您需要的更多的两个指针。你只是创造了200-2000个，我怀疑记忆会变得那么紧张。

我相信其他stl实现非常相似。我会吸收矢量存储的次要成本，并将其用于您的项目中。

来源

2011-10-07 17:02:27 DanDan

内存使用不是我最关心的问题。速度是。 – Jackie

矢量与动态数组相比，速度有很大差异吗？

回答

相关问题