Fastest way to reset every value of std::vector to 0

Question

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 ?

Answer 1

std::fill(v.begin(), v.end(), 0);

Answer 2

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)!

Answer 3

How about the assign member function?

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

Answer 4

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. :)

Answer 5

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

Answer 6

try

std::fill

and also

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

Answer 7

Have a vector of zeroes ready, then switch it with current vector when you need zeroes:

std::vector<int> zeroes(N,0);
std::vector<int> currentVec(N);
...
currentVec.swap(zeroes);

this effectively zeroes the currentVec in O(1) complexity. But until next time you need zeroing, you have to fill the other (zeroes) with zeroes, asynchronously. You can use a dedicated thread for this. Then during swapping, just an overhead of "mutex" will be there.

std::lock_guard<std::mutex> lg(mut);
currentVec.swap(zeroes);

while in another thread:

std::lock_guard<std::mutex> lg(mut);
std::fill(zeroes.begin(),zeroes.end(),0);