CODEWITHSUNDEEP
c++optimizationvector
memo
memo

Reputation: 3714

quick way of resizing vector of vectors to correct size (c++)

I'd like to resize a std::vector< std::vector< T > > to a known size (m, n) as efficiently as possible, ideally without any memory copying (T is float or double). 

class Foo {
    std::vector< std::vector< T > > data;
    std::vector< std::vector< T > > data_norm;

    std::vector< T > min_values;
    std::vector< T > max_values;

    void normalize();
}

data is filled dynamically, pushing_back new data one 'row' at a time. Each 'row' is guaranteed to have the same number of elements. So it is effectively an m x n table.

Then at one point I call the normalize() method which:

Currently I'm doing data_norm = data at the start of my normalize() method just to make sure data_norm is allocated to the right size and there are no further re-allocations. But that involves copying all of the memory. Is there a way to do it without this memory copy?

I've seen this post which suggests

std::vector<std::vector<T>> my_vec(m, std::vector<T>(n))

However in my situation my_vec already exists. I could create and assign a new_vec:

std::vector<std::vector<T>> new_vec(m, std::vector<T>(n));
data_norm = new_vec;

But I guess that's still going to have the memory copy, in fact it'll be slower than data_norm = data because a whole new vector (new_vec) is initialized and allocated, and I already have a source vector of the right size.

I was hoping there is a way of doing it with a resize-like method? But without iterating through and doing resize on each sub-vector - which would create crazy reallocations I guess.

Upvotes: 1

Views: 2104

Answers (2)

bames53
bames53

Reputation: 88155

Currently I'm doing data_norm = data at the start of my normalize() method just to make sure data_norm is allocated to the right size and there are no further re-allocations.

First, you should simply design your program such that nobody can resize the vectors and ensure that you're not resizing them and then you can avoid this work entirely. You could put some asserts in your code to make sure the size never changes in debug mode if you want to be extra safe.

Also, if you want to do the work 'as efficiently as possible', then you should avoid using a vector of vectors, since for a rectangular matrix that's more allocations than necessary.

There's currently no standard container that provides an efficient multi-dimensional array with runtime bounds, but you can pretty easily define one. Here's a pretty minimal example.

template<typename T>
class vector2d {
  std::vector<T> data;
  int columns;

public:
  struct index { int r, c; };

  vector2d(index i) : data(i.r * i.c), columns(i.c) {}
  T &operator[] (index i) { return data[i.r*columns + i.c]; }
}

And then you can write:

class Foo {
    vector2d<T> data;
    vector2d<T> data_norm;

    std::vector<T> min_values;
    std::vector<T> max_values;

    void normalize();

    Foo(int n, int m) : data({n, m}), data_norm({n, m}) {}
}

And if you want to do the same thing for an arbitrary number of dimensions that can be done as well.

Upvotes: 1

Captain Wise
Captain Wise

Reputation: 480

You can use vector::resize(), it does it without creating a temporary vector

http://www.cplusplus.com/reference/vector/vector/resize/ 

// resizing vector
#include <iostream>
#include <vector>

int main ()
{
  std::vector<int> myvector;

  // set some initial content:
  for (int i=1;i<10;i++) myvector.push_back(i);

  myvector.resize(5);
  myvector.resize(8,100);
  myvector.resize(12);

  std::cout << "myvector contains:";
  for (int i=0;i<myvector.size();i++)
    std::cout << ' ' << myvector[i];
  std::cout << '\n';

  return 0;
}

Output:

myvector contains: 1 2 3 4 5 100 100 100 0 0 0 0

Upvotes: 2

Related Questions