2

std::vector::size()每次调用向量时都会重新计算向量的大小，还是维护一个仅在向量被修改时才被修改的计数器？例如，如果我与std::vector<double>成员一起上课，在单独的柜台中跟踪其大小是否有任何速度优势？

4

5 回答 5

12

size()保证具有恒定的时间复杂度，并且在任何理智的实现中都将尽可能快地进行操作。

于 2012-04-18T23:37:49.943 回答
3 
this->_Mylast - this->_myFirst

通常涉及两次内存提取。如果您在寄存器中维护计数，它可能会更快。我说可能，因为在一个小循环中，被减去的两个值将在缓存中，这并不总是比寄存器慢很多 - 取决于机器。一个聪明的编译器，与一个紧密的循环一起工作，无论如何都可以在寄存器中维护它们，如果它的数据流分析正确的话。在一个不那么小的循环中，您永远不会注意到差异。将其保存在寄存器中意味着每次迭代都需要额外的操作来更新寄存器，如果可以与其他操作并行完成，这可能是免费的，或者可能会花费一个指令周期。所以很难衡量差异。

无论如何，您的里程会因处理器而异，即使 STL 的每个实现都有相同的代码size()。

于 2012-04-18T23:47:17.933 回答
2

无需在单独的计数器中跟踪其大小，因为它是在矢量内部完成的。这个函数的代码是这样的：

iterator begin() {return start;}
iterator end() {return finish;}
size_type size() const { return size_type(end() - begin());}

iterator start;
iterator finish;

一旦你 push 或 pop 元素，变量“start”、“finish”就会改变，所以函数 size() 只需要减的时间。如果使用单独的计数器，当你推送或弹出元素时，你也会有一个加号或减号。

于 2012-04-19T02:27:23.527 回答
1

不 - 只需使用std::vector::size()

在 MSVC 上，它被实现为this->_Mylast - this->_Myfirst- 你无法击败它。

于 2012-04-18T23:38:18.203 回答
1

正如其他人所说，它很难变得更快。只有在您的向量大小不变的情况下，您确实可以通过使用这个事实来节省一些 CPU 周期。实际上，您可以完全跳过查询大小。这对于渲染循环等中经常重复的可笑迭代可能很重要。想象一下以下之间的区别：

// reset vector of size=3 to value 10

for( size_t i=0; i < myvec.size(); ++i )
{
   myvec[i] = 10.0;
}

相对

 myvec[0] = myvec[1] = myvec[2] = 10.0;

一个典型的用例是一个 3d 坐标向量、一个 IP 地址等。但是要准备好用你自己的替换一些在内部查询 size() 的 std::vector 例程。所以要点是，为了节省 cpu 周期，size 运算符不是目标，寻找其他合乎逻辑的地方。当你的向量没有改变它的大小时，即使是暂时的，你有一只脚可以挤出一些 cpu 周期。

PS：Valgrind是您的朋友，可以告诉您首先优化哪里。事实上，尺寸运算符经常作为最佳候选者出现。至少对于某些算法。

祝你好运！

于 2012-04-19T08:43:51.817 回答