ChatGPT解决这个技术问题 Extra ChatGPT

Fastest way to reset every value of std::vector<int> to 0

What's the fastest way to reset every value of a std::vector<int> to 0 and keeping the vectors initial size ?

A for loop with the [] operator ?

"Fastest" as in performance? Or as in easiest to implement/maintain?

Q
Qix - MONICA WAS MISTREATED
std::fill(v.begin(), v.end(), 0);

Looking at the assembly output, gcc actually unrolls this loop into using the mmx registers to dump in 16 bytes at a time until it gets close to the end. I'd say that's pretty fast. The memset version jumps to memset, which I'm guessing is about as fast. I'd use your method.
But, jumping to memset is a single instruction, so using it will result in a smaller binary size.
this is not exactly what OP asked for, but simply reassigning your vector to a new one of the same size (v = std::vector<int>(vec_size,0)) seems slightly faster than fill on my machine
This is the most idiomatic way of doing it, more idiomatic than using assign.
does assigning it to a new vector do heap allocation ? and then discard the allocation of the existing vector ? I could see that being slower than memset et al
F
Fabio Fracassi

As always when you ask about fastest: Measure! Using the Methods above (on a Mac using Clang):

Method      |  executable size  |  Time Taken (in sec) |
            |  -O0    |  -O3    |  -O0      |  -O3     |  
------------|---------|---------|-----------|----------|
1. memset   | 17 kB   | 8.6 kB  | 0.125     | 0.124    |
2. fill     | 19 kB   | 8.6 kB  | 13.4      | 0.124    |
3. manual   | 19 kB   | 8.6 kB  | 14.5      | 0.124    |
4. assign   | 24 kB   | 9.0 kB  | 1.9       | 0.591    |

using 100000 iterations on an vector of 10000 ints.

Edit: If changeing this numbers plausibly changes the resulting times you can have some confidence (not as good as inspecting the final assembly code) that the artificial benchmark has not been optimized away entirely. Of course it is best to messure the performance under real conditions. end Edit

for reference the used code:

#include <vector>

#define TEST_METHOD 1
const size_t TEST_ITERATIONS = 100000;
const size_t TEST_ARRAY_SIZE = 10000;

int main(int argc, char** argv) {

   std::vector<int> v(TEST_ARRAY_SIZE, 0);

   for(size_t i = 0; i < TEST_ITERATIONS; ++i) {
   #if TEST_METHOD == 1 
      memset(&v[0], 0, v.size() * sizeof v[0]);
   #elif TEST_METHOD == 2
      std::fill(v.begin(), v.end(), 0);
   #elif TEST_METHOD == 3
      for (std::vector<int>::iterator it=v.begin(), end=v.end(); it!=end; ++it) {
         *it = 0;
      }
   #elif TEST_METHOD == 4
      v.assign(v.size(),0);
   #endif
   }

   return EXIT_SUCCESS;
}

Conclusion: use std::fill (because, as others have said its most idiomatic)!


+1. This particular benchmark isn't conclusive, but the point is absolutely correct, you should write a performance test of the alternatives as they will actually be used. If there's no performance difference then use whichever is the simplest source.
"... not conclusive ..." IMO this inconclusiveness in itself is already a good point for doing benchmarks, more often than not the Optimizer already does a very good job for the kind of situations the OP asked about. And I'd modify your last sentence to read "If there's no significant performance difference ..."
UPDATE Using Nonius for benchmarks: clang3.6-libc++-c++1y-O3, gcc4.9-c++1y-O3 and gcc5-c++1y-O3 - TL;DR: assign is slower, except for small capacities on libc++. CODE coliru/paste
Also, wow, if you care about speed without optimizations (which might be plausible if you are deploying in 'debug' mode, which some teams do), fill looks terrible. It is two orders of magnitude slower in this test.
@KyleStrand: It's not that fill is terrible, it is a template and the code is generated with -O0 inside your translation unit. When you use memset, you are using the libc code which was compiled with -O3 (even when you compile your code with -O0). If you care about speed in debug and you use templates, you will have to use explicit template instantiation in a separate file which you compile with -O3
f
fredoverflow

How about the assign member function?

some_vector.assign(some_vector.size(), 0);

The OP wanted to reset existing values, but your answer is better when wanting to resize and reset the values. Thanks!
u
unwind

If it's just a vector of integers, I'd first try:

memset(&my_vector[0], 0, my_vector.size() * sizeof my_vector[0]);

It's not very C++, so I'm sure someone will provide the proper way of doing this. :)


Since the standard (2003 TC1) guarantees that a std::vector is contiguous in memory, this should be fine. If your c++ library does not conform to the 2003 TC1, then don't use this.
@Mario: I wouldn't have posted this unless that was true and assumed to be well-known, of course. :) But thanks.
I checked the assembly. The ::std::fill method expands to something that's pretty darned fast, though a bit on the code-bloaty side since it's all inline. I'd still use it though because it's much nicer to read.
You'd better to add check if vector is empty and do nothing in this case. Calculating &buf[0] for empty vector can generate assertions in STL code.
n
nttstar

try

std::fill

and also

std::size siz = vec.size();
//no memory allocating
vec.resize(0);
vec.resize(siz, 0);

resize is very nice
I timed vec.resize(0); vec.resize(siz); and found that with -O3 it performs the same as memset.
Y
Yauhen Yakimenka

I had the same question but about rather short vector<bool> (afaik the standard allows to implement it internally differently than just a continuous array of boolean elements). Hence I repeated the slightly modified tests by Fabio Fracassi. The results are as follows (times, in seconds):

            -O0       -O3
         --------  --------
memset     0.666     1.045
fill      19.357     1.066
iterator  67.368     1.043
assign    17.975     0.530
for i     22.610     1.004

So apparently for these sizes, vector<bool>::assign() is faster. The code used for tests:

#include <vector>
#include <cstring>
#include <cstdlib>

#define TEST_METHOD 5
const size_t TEST_ITERATIONS = 34359738;
const size_t TEST_ARRAY_SIZE = 200;

using namespace std;

int main(int argc, char** argv) {

    std::vector<int> v(TEST_ARRAY_SIZE, 0);

    for(size_t i = 0; i < TEST_ITERATIONS; ++i) {
#if TEST_METHOD == 1
        memset(&v[0], false, v.size() * sizeof v[0]);
#elif TEST_METHOD == 2
        std::fill(v.begin(), v.end(), false);
   #elif TEST_METHOD == 3
        for (std::vector<int>::iterator it=v.begin(), end=v.end(); it!=end; ++it) {
            *it = 0;
        }
   #elif TEST_METHOD == 4
      v.assign(v.size(),false);
   #elif TEST_METHOD == 5
      for (size_t i = 0; i < TEST_ARRAY_SIZE; i++) {
          v[i] = false;
      }
#endif
    }

    return EXIT_SUCCESS;
}

I used GCC 7.2.0 compiler on Ubuntu 17.10. The command line for compiling:

g++ -std=c++11 -O0 main.cpp
g++ -std=c++11 -O3 main.cpp