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?
The comment for std::fill (https://en.cppreference.com/w/cpp/algorithm/fill) says:
Complexity
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.