是std :: vector（InputIterator第一次，InputIterator最後一次）的線性時間複雜度？

我想用C++ std::vector輸入迭代器的構造函數建立連續整數的一個這樣的數組：是std :: vector（InputIterator第一次，InputIterator最後一次）的線性時間複雜度？

std::vector<unsigned> indexes(boost::counting_iterator<unsigned>(0U), 
           boost::counting_iterator<unsigned>(10000U));

不過，我想知道是否有時間成正比的迭代器之間的距離的複雜性或者是否由於反覆調整大小以增加矢量而可能具有額外的對數分量？換句話說，構造函數是否查看兩個迭代器之間的距離？由於構造函數的參數不是隨機訪問迭代器，我不確定可以計算距離嗎？

如果它會反覆調整，有沒有比這更好的解決辦法，以避免：

std::vector<unsigned> indexes; 

indexes.reserve(10000U); 

for (unsigned idx = 0; idx < 10000U; ++idx) { 
    indexes.push_back(idx); 
}

來源

2013-03-20 WilliamKF

是std::vector(InputIterator first, InputIterator last)線性時間複雜度？

簡而言之，是的。

標準保證了以下vector(InputIterator, InputIterator)在§23.3.6.2：

複雜性：使n只有調用T（其中，N是第一和最後一個之間的距離）和的拷貝構造如果迭代器首先和最後是前向，雙向或隨機訪問，則不重新分配類別。如果它們的僅僅是輸入迭代器，它將命令N調用T的拷貝構造函數並且命令日誌（N）重新分配。

基本上，向前，雙向或隨機訪問迭代器，你不應該希望看到使用reserve()在你的第二個例子任何性能增益;構造函數會自動爲你做這個。

對於普通輸入迭代器，reserve()會加快速度，但不會超過一個常數因子。 log(n)重新分配仍將在O(n)總時間內完成，因此構建向量的總時間也將爲O(n)。

來源

2013-03-20 17:26:51 NPE

至少在[libC++]（http://libcxx.llvm.org/）實現中，使用了「std :: distance」（如果迭代器是ForwardIterator或更好）並且只執行一次分配。對於隨機訪問迭代器，std :: distance是恆定的時間，否則是線性的。 – 2013-03-20 17:35:47

@JohnBartholomew'boost :: counting_iterator'是一個前向迭代器還是一個隨機訪問迭代器？ – WilliamKF 2013-03-20 17:42:23

@JohnBartholomew：你說的很對，謝謝指出。答案已展開。 – NPE 2013-03-20 17:44:26

是std :: vector（InputIterator第一次，InputIterator最後一次）的線性時間複雜度？

回答

相關問題