STL 算法和 back_inserter 可以预分配 space 吗？

Question

如果我有类似的东西：

vector<int> longVector = { ... };
vector<int> newVector;
transform(longVector.begin(), longVector.end(), back_inserter(newVector),
          [] (int i) { return i * i; });

STL 能否在处理和添加新元素之前在 newVector 中预分配 space？我知道这不是算法的要求，但是 "good" 实现能够优化它吗？或者，对于这种情况，我应该更喜欢在之前添加 newVector.reserve(longVector.size()); 吗？我不一定要问每个 stdlib 实现是否存在（尽管如果有人知道具体的例子会很棒），但更多的是考虑到算法的接口和要求，是否有可能（和预期）。

该问题适用于多种 STL 算法，transform、copy、move、fill_n，...而不仅仅是 back_inserter，我想还有 front_inserter 和 inserter。

编辑：为清楚起见，我的意思是，对于输出迭代器是 back_inserter 的 transform，stdlib 是否可以提供特定的实现24=]，在这种情况下，它将访问向量对象并保留足够的 space 以在实际运行转换之前在给定的迭代器对之间存储 distance。

Answer 1

使用 boost::transform_iterator 而不是 std::transform 和 std::back_inserter 几乎可以达到 1 内存分配的预期效果。

但问题是因为 boost::transform_iterator 不能 return 对元素的引用，它被标记为 std::input_iterator_tag。输入迭代器是单遍迭代器，与其他迭代器类别不同，当传递给 std::vector 范围构造函数时，它使用 push_back 来填充向量。

您可以强制恢复原始迭代器类别并实现 1 内存分配的预期效果，但需要注意的是，此类迭代器违反了双向或随机访问迭代器必须 return 引用的标准要求元素：

#include <boost/iterator/transform_iterator.hpp>
#include <algorithm>
#include <vector>

template<class I>
struct original_category_iterator : I {
    using iterator_category = typename std::iterator_traits<typename I::base_type>::iterator_category;
    using I::I;
};

template<class I>
inline original_category_iterator<I> original_category(I i) {
    return {i};
}

int main() {
    std::vector<int> longVector = {1,2,3};
    auto f = [](auto i) { return i * i; };
    std::vector<int> newVector(original_category(boost::make_transform_iterator(longVector.begin(), f)),
                               original_category(boost::make_transform_iterator(longVector.end(), f)));
}

Answer 2

库中需要大量特殊外壳，但收效甚微。

将算法与集合分开的全部意义在于，两者都不需要了解对方，用户可以添加自己的算法来处理标准集合，或者添加新的集合来处理现有算法。

因为唯一的好处就是奖励那些懒得调用的程序员reserve()，我觉得任何实现者都不太可能实现这样的东西。特别是因为它可能需要 std::distance() 输入迭代器才能工作，进一步限制了它的使用。

另请注意，这样的实现需要在其迭代器中保留对所属向量的引用，并且无法使用 std::vector<T>::iterator 的最常见表示形式，即 T*。这是所有用户都必须承担的成本，无论是否使用此新功能。

技术上可行吗？也许，在某些情况下。允许吗？我认同。物有所值？编号

Answer 3

好消息是范围库 does 为随机访问迭代器容器保留，因此如果您愿意，可以使用它。

现在回到问题：

循环保留有问题

如果不阅读 code 很难解释，但是如果在循环中调用 STL 算法并且它正在做储备，它可能会触发二次复杂度。问题是某些 STL 容器会保留所请求的确切内存量（对于小尺寸来说这是可以理解的，但对于大尺寸 IMAO 这是错误的行为），例如，如果当前容量为 1000 并且您调用 reserve(1005)、reserve(1010) ), reserve(1010) 它将导致 3 次重新分配（这意味着您每次复制 ~1000 个元素以获得 5 个额外的位置）。这是代码，有点长，但希望你明白：

#include<vector>
    #include<iostream>
    #include<chrono>
    int main(){
         std::vector<float> vec(10000,1.0f);
         std::vector<std::vector<float>> small_vecs(5000, std::vector<float>(50,2.0f));
         const auto t_start = std::chrono::high_resolution_clock::now();
         for(size_t i = 0; i < small_vecs.size(); i++) {
             // uncomment next line for quadratic complexity
             //vec.reserve(vec.size()+small_vecs[i].size());
             for (size_t j=0; j< small_vecs[i].size(); ++j){
                 vec.push_back(small_vecs[i][j]);
             }
         }
         const auto t_end = std::chrono::high_resolution_clock::now();
         std::cout << "runtime:" <<
             std::chrono::duration_cast<std::chrono::milliseconds>(t_end - t_start).count()
             << "ms\n";
    }

奖金：

上次我对它进行基准测试 back_iterator 即使有保留也慢得可怜（减速以 x 衡量，而不是 %），所以如果你关心性能，请确保当你使用 back_inserter 你的代码它以手动循环为基准。

Answer 4

我不认为这是可能的。在迭代器类别上工作的容器和算法有明显的区别。

与clear() 和erase() 一样，reserve() 修改容器。引入 reserve()，使算法具有容器意识，这违背了那种明显分离的简洁设计。

你也可以

deque<int> longDeque = { ... };
deque<int> newDeque;
transform(longDeque.begin(), longDeque.end(), back_inserter(newDeque),
          [] (int i) { return i * i; });

或

list<int> longList = { ... };
list<int> newList;
transform(longList.begin(), longList.end(), back_inserter(newList),
          [] (int i) { return i * i; });

和std::deque & std::list不支持reserve()，但是代码是一样的。

最后一点： vector 没有 push_front() 所以不需要支持 front_inserter()。

STL 算法和 back_inserter 可以预分配 space 吗？

Can STL algorithms and back_inserter preallocate space?

c++

memory

stl

stdvector

stl-algorithm