11

I have a 3D string vector in C++:

vector<vector<vector<string>>> some_vector

That I am trying is to find a fast method to allocate memory for it.

I tried to define it with two different methods as follow:

#include<vector> #include<iostream> #include<ctime> using namespace std; #define DIM1 100 #define DIM2 9 #define DIM3 120 int main() { clock_t t1_start = clock(); vector<vector<vector<string>>> vec1(DIM1, vector<vector<string>>(DIM2, vector<string>(DIM3))); clock_t t1_end = clock(); double diff1 = (t1_end - t1_start) / double(CLOCKS_PER_SEC); clock_t t2_start = clock(); vector<vector<vector<string>>> vec2; vec2.resize(DIM1); for(int i = 0; i < DIM1; i++) { vec2[i].resize(DIM2); for(int j = 0; j < DIM2; j++) vec2[i][j].resize(DIM3); } clock_t t2_end = clock(); double diff2 = (t2_end - t2_start) / double(CLOCKS_PER_SEC); cout<<"1st definition used time: "<<diff1<<"s"<<endl; cout<<"2nd definition used time: "<<diff2<<"s"<<endl; }

I expect that the first method (vec1) could be faster than the 2nd one (vec2).

But it turned out that the 1st method is much slower than the 2nd. On my machine, the 1st method used 0.245 seconds, while the 2nd method used 0.152 seconds.

Moreover, when I switch the data type to int, the 1st one took 0.058 second, and the 2nd took 0.004.

May I know what cause such difference? And is there better way to allocate memory for a 3D vector?

Many thanks in advance.

Improve this question
8
  • 2
    Are you using an optimized build? Commented Aug 5, 2013 at 16:02
  • What are you doing that requires such high performance for allocating your data structure? If you need something super-fast, three dimensional std::vector<>s may not be what you're looking for. Commented Aug 5, 2013 at 16:03
  • 3
    If the dimensions are constant, then why not std::array<std::array<std::array<std::string, DIM3>, DIM2>, DIM1> ? Commented Aug 5, 2013 at 16:08
  • It might be because there could be more copies made in the first call versus the second call Commented Aug 5, 2013 at 16:09
  • If you switch around the order of the tests, how does that affect the timing? (And make sure optimizations are enabled.) Consider using a better benchmarking tool that uses a high-precision timer and runs many iterations to smooth out various cache-related and external environment effects. Commented Aug 5, 2013 at 16:14

6 Answers 6

Reset to default
17

May I know what cause such difference?

The first version constructs a 2-d vector by copying a 1-d vector, and then constructs the 3-d vector by copying that. This might be slower than resizing the vectors without copying. However, I'd hope that the difference would be negligible if you're building with optimisation.

And is there better way to allocate memory for a 3D vector?

It might be better to use a single contiguous array, wrapped in a class that provides multi-dimensional accessors. This would make allocation much simpler, and would also avoid some pointer dereferencing when accessing elements (at the cost of a bit of arithmetic). Something like this:

template <typename T> class vector3d { public: vector3d(size_t d1=0, size_t d2=0, size_t d3=0, T const & t=T()) : d1(d1), d2(d2), d3(d3), data(d1*d2*d3, t) {} T & operator()(size_t i, size_t j, size_t k) { return data[i*d2*d3 + j*d3 + k]; } T const & operator()(size_t i, size_t j, size_t k) const { return data[i*d2*d3 + j*d3 + k]; } private: size_t d1,d2,d3; std::vector<T> data; };
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Bounds checking is often a reason that vectors are used. Adding asserts to your operators that each of the indices is below their dimension is a good idea.
@NeilKirk: Indeed, this could do with a range-checked at function, and various other bits and pieces, to be more than a sketch of how you'd implement your own container.
4

I think I'd optimize it by allocating one large block of memory instead of a lot of little ones. This one is only 2D instead of 3D, but gives the basic idea:

template <class T> class matrix { size_t columns_; std::vector<T> data; public: matrix(size_t columns, size_t rows) : columns_(columns), data(columns*rows) {} T &operator()(size_t column, size_t row) { return data[row*columns_+column]; } };

For 3D, you'll need to deal with "planes" (or something) along with rows and columns, but the basic idea is pretty much the same.

Improve this answer

Comments

4

I added several features to Mike Seymour's code such as dynamically resize the 3d vector and on access/assign bounds checking for data vector.

template <typename T> class vector3d { public: vector3d(size_t d1=0, size_t d2=0, size_t d3=0, T const & t=T()) : d1(d1), d2(d2), d3(d3), data(d1*d2*d3, t) {} T & operator()(size_t i, size_t j, size_t k) { return (i<=d1 && j<=d2 && k<=d3) ? data[i*d2*d3 + j*d3 + k] : data.at(i*d2*d3 + j*d3 + k); } T const & operator()(size_t i, size_t j, size_t k) const { return data[i*d2*d3 + j*d3 + k]; } void resize(const size_t _d1=0, const size_t _d2=0, const size_t _d3=0) { data.resize(_d1*_d2*_d3); d1=_d1; d2=_d2; d3=_d3; } void shrink_to_fit() { data.shrink_to_fit(); } const size_t length() const { return data.size(); } const size_t capacity() const { return data.capacity(); } const size_t x() const { return d1; } const size_t y() const { return d2; } const size_t z() const { return d3; } private: size_t d1,d2,d3; std::vector<T> data; };

Usage:

vector3d<int> vec3d(2,2,2,31); //create 2x2x2 3d vector and fill it with 31 vec3d(1,1,2)=45; //assign 45 at vec3d(1,1,2) vec3d.resize(2,2,1); //resize the vec3d to 2x2x1 vec3d(1,2,2)=67; //error (its out of bounds)
Improve this answer

Comments

2

To initialize a 3D string vector you shall initialize the vector structure for each dimension one at a time and for each index, for instance:

 vector<vector<vector<string> > > myvector; //declare the 3D vector for(k=0; k<3; k++) { myvector.push_back(vector<vector<string> >()); //initialize the first index with a 2D vector for(i=0; i<4; i++) { myvector[k].push_back(vector<string>()); //initialize the 2 index with a row of strings for(j=0; j<4; j++) { result = " whatever you want to insert in the vector element"; myvector[k][i].push_back(result); //fulfill the last index regularly } } }
Improve this answer

Comments

0

When you initialize a vector of vectors in the first method, a temporary vector is allocated and then copied into the outer vector the required number of times. This means you have an extra allocation that is unnecessary and the new elements are initialized by copying their value from another data structure, which uses more memory accesses.

Resizing the vectors as per the second method is more ugly but avoids the extra allocation. Furthermore the new elements are created by the default constructor and do not need to copy from other vectors. This will also be faster.

If speed matters (and maybe it doesn't, premature optimization and all that), then you must use the second method (OR a single-block allocation as suggested by the other answers). I don't have faith that a compiler can simply "optimize" away the inefficiency of the first method.

Improve this answer

Comments

0

Here is an example of various dimensions of vectors in case anyone out there cares. I know when I was starting out it was a pain to find how to give initial values to multidimension vectors as I couldn't find any examples;

// This simple project demonstrates a single vector, a 2D vector, a 3D vector and a 4D vector in C++ // #include <iostream> #include <vector> using namespace std; int main () { vector<int> myVector = { 0,1,2,3,4,5,6 }; vector<vector<int>> my2dVector = { {1,2,3,4,5},{6,7,8,9,10},{11,12,13,14,15},{16,17,18,19,20},{21,22,23,24,25},{0,-1,-2,-3,-4},{-6,7,22,-15,-25},{true,true,false,true,false} }; vector < vector < vector<int>>> my3dVector = { { {1,2,3}, {4,5,6}, // plane 0 {7,8,9} }, { {-1,-2,-3}, {-4,-5,-6}, // plane 1 {-10,-22,36} }, { {129,212,999}, {0,0,1}, // plane 2 {false,true,false} } }; vector<vector<vector<vector<int>>>> my4dVector = { { //Cube 0 { {1,2,3}, {4,5,6}, // plane 0 {7,8,9} }, { {-1,-2,-3}, {-4,-5,-6}, // plane 1 {-10,-22,36} }, { {129,212,999}, {0,0,1}, // plane 2 {false,true,false} } }, { //Cube 1 { {10,2,-9}, {44,55,60}, // plane 0 {71,85,99} }, { {-561,-6562,-453}, {-14,-55,-76}, // plane 1 {-110,-212,316} }, { {729,812,456}, {40,10,17}, // plane 2 {true,true,false} } } }; // 1D VECTOR.............. cout << "This is a 1D vector of size " << myVector.size () << "\n"; for (int i = 0; i < myVector.size (); i++) { cout << myVector[i] << "\t"; } cout << "\n\n"; // 2D VECTOR.............. cout << "This is a 2D vector of size " << my2dVector.size () << " X " << my2dVector[0].size () << "."; if (my2dVector.size () == my2dVector[0].size ()) cout << " This is a square matrix."; cout << "\n "; for (int i = 0; i < my2dVector[0].size (); i++) { cout << "C" << i << "\t"; } cout << endl; for (int i = 0; i < my2dVector.size (); i++) { cout << "Row: " << i << " -> "; for (int j = 0; j < my2dVector[i].size (); j++) { if (my2dVector[i][j] >= 0 && my2dVector[i][j] <= 9) cout << " "; cout << my2dVector[i][j] << "\t"; } cout << endl; } cout << "\n\n"; // 3D VECTOR................. cout << "This is a 3D vector of size " << my3dVector[0].size () << " X " << my3dVector[0][0].size () << " with " << my3dVector.size () << " planes.\n"; for (int i = 0; i < my3dVector.size (); i++) { cout << "Plane #" << i << "\n"; for (int j = 0; j < my3dVector[i].size (); j++) { for (int k = 0; k < my3dVector[i][j].size (); k++) { cout << my3dVector[i][j][k] << "\t"; } cout << "\n"; } } cout << "\n\n"; //4D VECTOR................. cout << "This is a 4D vector of size " << my4dVector[0][0].size () << " X " << my4dVector[0][0][0].size () << " with " << my4dVector[0].size () << " planes and " << my4dVector.size () << " cubes.\n"; for (int i = 0; i < my4dVector.size (); i++) { cout << "\nCUBE #"<< i<< " _________________\n"; for (int j = 0; j < my4dVector[i].size (); j++) { cout << "Plane #" << j << " |\n"; for (int k = 0; k < my4dVector[i][j].size (); k++) { for (int l = 0; l < my4dVector[i][j][k].size (); l++) { cout << my4dVector[i][j][k][l] << "\t"; } cout << "|\n"; } cout << "________________________|\n"; } cout << "\n"; } }
Improve this answer

2 Comments

Please provide additional details in your answer. As it's currently written, it's hard to understand your solution.
The listing is complete, copy and paste and trace it with a debugger to understand what it is doing. I just provided it as an example of how to create a 1d, 2d, 3d or 4d vector and how to assign the initial values in code (change values to whatever you want), then how to print out the values (stepping through using for loops). The main point here was simply to show how to assign the initial values to a 3d and 4d vector. I know on occasion people search for this... I did when starting out and it can be frustrating for beginners. So I figured I would just provide a simple example.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.