如何高效填充二维std::vector首列？能否替代循环或实现更快填充？

问题背景 #

经查询，std::fill针对std::vector的复杂度情况如下（引自cppreference）：

复杂度：线性。
但若InputIt满足LegacyRandomAccessIterator要求，则复杂度为常数。

基于此，我曾以为可通过以下代码以常数时间填充二维std::vector的首行：

std::fill(mat[0].begin(), mat[0].end(), 0)

现咨询：是否存在无需如下循环的方式来填充首列？

for(size_t i = 0; i < m; i++) mat[i][0] = 0;

能否使用memset等方法实现比线性时间更快的填充？

解答 #

首先纠正一个关键误解：你对std::fill的复杂度理解有误。cppreference里的描述，LegacyRandomAccessIterator仅允许常数时间计算迭代器的距离，但填充操作本身依然是线性时间——因为std::fill需要遍历区间内每一个元素并赋值，操作次数等于元素数量，复杂度始终是O(n)（n为元素个数）。所以你用std::fill填充首行的操作，本质还是线性时间，并非常数时间。

回到你的问题：

• 不存在无需遍历的首列填充方式，也不可能实现比线性时间更快的填充：二维std::vector的每一行都是独立的vector对象，它们的内存块在堆上分散存储，首列元素并不连续。要修改首列的m个元素，必须逐个访问并赋值，无论用哪种写法，本质都要执行m次操作，复杂度必然是O(m)线性时间。

• 替代循环的写法（无性能提升）：可以用标准库算法代替手动循环，写法更简洁，但底层逻辑和循环完全一致，性能没有区别：

  std::for_each(mat.begin(), mat.end(), [](auto& row) { row[0] = 0; });
  

• memset无法用于此场景：memset要求操作连续的内存块，而二维vector首列元素的内存不连续；此外memset是按字节赋值，即便元素类型是可被字节填充为0的类型（如int、char），也无法跨分散的内存块完成批量操作，因此完全不适用。

内容的提问来源于stack exchange，提问作者g zero