英文:
Efficient way to fill column of a 2D vector
问题
如果发现使用std::vector的std::fill函数的复杂度是constant
复杂度
线性。但是，如果
InputIt还满足LegacyRandomAccessIterator的要求，复杂度是常数。
所以，我有一个二维向量，我可以在常数时间内填充第一行
std::fill(mat[0].begin(), mat[0].end(), 0)
是否可以在不使用循环的情况下对第一列进行相同的操作？
for(size_t i = 0; i < m; i++) mat[i][0] = 0;
是否可以用memset来实现比线性时间更快的填充？
英文:
If found that complexity of std::fill for std::vector is constant
> Complexity
> Linear.
>
> However, if InputIt additionally meets the requirements of LegacyRandomAccessIterator, complexity is constant.
so I have a 2D vector and i can fill first row with constant time
std::fill(mat[0].begin(), mat[0].end(), 0)
is it possible to do the same for the first column without a loop like this?
for(size_t i = 0; i < m; i++) mat[i][0] = 0;
can i fill faster than linear time maybe with memset?
答案1
得分: 0
std::fill的注释（https://en.cppreference.com/w/cpp/algorithm/fill）说：
复杂度
恰好是std::distance(first, last)次赋值操作。
这并不意味着std::fill和std::distance的复杂性相同，正如您似乎认为的那样。这意味着std::fill的复杂性与范围[first, last)中的元素数量成正比，对于每个这样的元素，都会执行一个赋值操作符。因此，std::fill的时间复杂性与赋值操作的数量成线性关系。然而，该算法是通用的，因此您不知道它所处理的迭代器（例如first）实际表示什么，以及赋值操作符（可能是已重载的用户定义的操作符）是否真的将任何值分配给任何东西。例如，它可能将值打印到std::cout。这就是为什么我认为参考文本中的描述并不是指修改某个容器中的元素数量（这可能根本不存在），而是指赋值的次数。
英文:
The comment for std::fill (https://en.cppreference.com/w/cpp/algorithm/fill) says:
> Complexity <br/>
> Exactly std::distance(first, last) assignments.
This does not mean that complexities of std::fill and std::distance are the same, as you seem to believe. It means that the complexity of std::fill is proportional to the number of elements in the range [first, last) and for each such element an assignment operator is executed. Consequently, the time complexity of std::fill is linear in the number of assignments. However, the algorithm is generic so you do not know what the iterators it works on (e.g., first) actually represents and if the assignment operator (which may be an overloaded, user-defined one) really assigns any value to anything. It might, for example, print the value to std::cout. That's why, I believe, the description in the reference text does not refer to the number of elements being modified in some container (which need not exist at all), but to the number of assignments.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论