CODEWITHSUNDEEP
c++vector
user8060
user8060

Reputation: 63

A fast way to set values of a 2d vector to 0

Given the following example 

#include <iostream>
#include <vector>
#include <algorithm>
#include<iterator>

using namespace std;

template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v){
    copy(v.begin(), v.end(), ostream_iterator<T>(os, "  "));
    return os;
}


int main (){

vector<int>vec;
vector<vector<int>> x(10,vector<int>());
for(int i=0; i< x.size(); i++)
    x[i].resize((rand() % 100 + 1), 10);

for(int i=0; i< x.size(); i++)
    fill(x[i].begin(),x[i].end(),0);

return 0;
}

What would be the fastest way to set the values in the second vector to 0

thnx

Upvotes: 2

Views: 15069

Answers (4)

Joseph Mansfield
Joseph Mansfield

Reputation: 110698

It is completely unnecessary to fill the inner std::vectors with zeroes, because resize default-inserts new elements into the vectors which value-initializes them. In the case of ints, value-initialization means setting them to 0.

It can be a little difficult to determine this from the standard, so here's the trail (from N4296 - the C++14 draft):

From the definition of resize:

If size() < sz, appends sz - size() default-inserted elements to the sequence.

The definition of default-inserted:

An element of X is default-inserted if it is initialized by evaluation of the expression

allocator_traits<A>::construct(m, p)

where p is the address of the uninitialized storage for the element allocated within X [and m is an allocator of type A].

Definition of allocator_traits<A>::construct:

template <class T, class... Args>
static void construct(Alloc& a, T* p, Args&&... args);

Effects: calls a.construct(p, std::forward<Args>(args)...) if that call is well-formed; otherwise, [...].

From the definition of an allocator:

a.construct(c, args)

Effect: Constructs an object of type C at c

Default: ::new ((void*)c) C(forward<Args>(args)...)

From the definition of the new-expression:

  • If the new-initializer is omitted, [...]

  • Otherwise, the new-initializer is interpreted according to the initialization rules of 8.5 for direct-initialization.

From the definition of direct-initialization:

  • [...]

  • If the initializer is (), the object is value-initialized.

  • [..]

Value-initialization:

  • if T is a (possibly cv-qualified) class type with [...];
  • if T is a (possibly cv-qualified) class type with [...];
  • if T is an array type, then [...];
  • otherwise, the object is zero-initialized.

Zero-initialization:

  • if T is a scalar type (3.9), the object is initialized to the value obtained by converting the integer literal 0 (zero) to T;

  • if [...]

Upvotes: 7

eerorika
eerorika

Reputation: 238401

In your example it's simplest and fastest to initialize the vectors with zeroes initially. In the constructor of the parent vector if they are same length, or in the resize if the vectors are random lengths.

If you have an existing vector of vectors with old values and you want to set them all to zero, then memset is usually the fastest way. Since vector is guaranteed to have contiguous storage and your inner vectors don't contain complex (non-POD) objects, it's safe to use memset

for(auto& v : x)
    std::memset(&v[0], 0, sizeof(v[0]) * v.size());

That said, std::fill_n or std::fill is probably just as fast and is not limited to POD/builtin objects and is easier to read so I recommend using that instead. Benchmark your code if you have a bottleneck and see if you gain anything with memset on your targeted platform. Otherwise, stick with what you have.

Upvotes: 1

DeepN
DeepN

Reputation: 344

Use the vector::vector(count, value) constructor which accepts the initial value. In the below case, it will be set to zero.

vector< vector<int> > yourVector(value1, vector<int>(value2)); 

// initial value will be zero

Upvotes: 1

Peter
Peter

Reputation: 36617

In C++11

for (auto &i : x)
    std::fill(i.begin(), i.end(), 0);

or (before C++11)

for (std::vector<int>::iterator i=x.begin(), end = x.end(); i != end; ++i)
    std::fill(i.begin(), i.end(), 0);

will be hard to beat - and will probably beat a loop using an index (as in x[i]).

Upvotes: 1

Related Questions