How to reserve memory for 2D vectors?

[Grime]

I'm working on a problem I saw online to take information about jigsaw puzzle pieces and display the solution in matrix format.

Basically the four sides of the jigsaw pieces are represented by lowercase and uppercase letters which I need to match.

Below the code which matches all jigsaws linearly on one row. (not finished just matches the first row)

int main() {

	int N; // number of puzzle pieces
	cin >> N; 

	vector <piece> pieces(N); // pieces
	vector < vector<piece> > pieces_pos; // matrix holding solution

	for (int i = 0; i < N; i++) { // takes input
		cin >> pieces[i].ID;
		cin >> pieces[i].top;
		cin >> pieces[i].left;
		cin >> pieces[i].bottom;
		cin >> pieces[i].right;

		if (pieces[i].top == 'x' && pieces[i].left == 'x')
			pieces_pos[0][0] = pieces[i]; // top left part of solution matrix
	}

	for (int i = 0 ;; i++) { // matches puzzles linearly for first row
		bool exists = false;
		for (int j = 0; j < N; j++) { // check if any puzzle matches right part
			if (tolower(pieces_pos[0][0].right) == tolower(pieces[j].left)) {
				pieces_pos.reserve(/*????*/);
				pieces_pos[0][i] = pieces[j];
				exists = true;
			}
		}
		if (!exists)
			break; // no puzzle match the right part so break
		// match was found, check if another puzzle matches this new puzzle's right part
	}



	system("pause");
	return 0;
}

Problem is. How do I assign to the pieces_pos array? Because at the beginning no memory is allocated to this vector so it counts as reaching an index out of memory. How do I reserve memory for it, TWO DIMENSIONALLY?

(reserving memory for one dimensional vectors can be done using .reserve())

I do NOT know the size of the array at compile time. The exact dimensions of the array in fact, is known only after the program is finished.

In short the lines pieces_pos[0][0] = pieces[i]; and pieces_pos[0][i] = pieces[j]; are what I'm having a problem with. Because pieces_pos has NO indexes when those lines are read.

I need something like push_back for two dimensions.
Or is it possible to reserve memory two dimensionally with vectors?


Okay assuming this can't be done with vectors.. How should I solve this problem? And why don't vectors support this kind of functionality?

(edit(1): added comments to make program more clear)

[Ganado]

You probably want resize(), not reserve().

I don't quite understand your algorithm, so let me just say what I would do.

On line 5, you make a vector of vector of pieces. This has a 0 outer size, and each inner vector also has a size of 0 (all default initialized). So, when you try to access pieces_pos on line 10, you are going out of bounds immediately. This is the first thing you need to focus on.

What exactly should pieces_pos look like before the for loops are even run?

// Example program
#include <iostream>
#include <string>
#include <vector>

int main()
{
    using Piece = char;
    
    // outer array size is 1
    // inner array size is 1, and is initialized to 'k'
    std::vector<std::vector<Piece>> pieces_pos(1, std::vector<Piece>(1, 'k'));

    // example: change the size of the outer array
    pieces_pos.resize(5);
      // pieces_pos[0] still has a size of 1
      // pieces_pos[1] to [4] now are default initialized to 0-length vectors
      
    // example: change the size of an inner array
    pieces_pos[3].resize(10);

    // now we can access pieces_pos[2][9], for example.
    pieces_pos[2][9] = 'j';
    
    // push back an 11th element to pieces_pos[2]
    pieces_pos[2].push_back('i');
}

If you wrote what you want your algorithm to do in perhaps pseudo-code, and what you want the end result of your pieces_pos 2D vector to look like, I could probably fix your code.

Edit: I see you edited your post. I'm looking it over now to see if I understand it more now.
- On lines 17 and 23, you are trying to access the 2D vector at [0][0], but these elements do not exist. You must solve this first.
- In short: You must push_back or resize the outer dimension (outer array) before you push_back or resize the inner array.
[code]
outer_vec.push_back(std::vector<Piece>());

[Grime]

EDITED POST

But why is reserved unsuitable?

Code is faulty read below posts
Anyways edited code (faulty):

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
using namespace std;

struct piece {
	char ID;
	char top;
	char left;
	char bottom;
	char right;
};

int main() {

	int N; // number of puzzle pieces
	cin >> N; 

	vector <piece> pieces(N); // pieces
	vector < vector<piece> > pieces_pos(1); // matrix holding solution
	pieces_pos[0].resize(1);

	for (int i = 0; i < N; i++) { // takes input
		cin >> pieces[i].ID;
		cin >> pieces[i].top;
		cin >> pieces[i].left;
		cin >> pieces[i].bottom;
		cin >> pieces[i].right;

		if (pieces[i].top == 'x' && pieces[i].left == 'x')
			pieces_pos[0][0] = pieces[i]; // top left part of solution matrix
	}

	for (int i = 0 ;; i++) { // matches puzzles linearly for first row
		bool exists = false;
		for (int j = 0; j < N; j++) { // check if any puzzle matches right part
			if (tolower(pieces_pos[0][i].right) == tolower(pieces[j].left)) {
				pieces_pos[0].resize(i + 3);
				pieces_pos[0][i] = pieces[j]; // later realized it should be [i+1]
				exists = true;
			}
		}
		if (!exists)
			break; // no puzzle match the right part so break
		// match was found, check if another puzzle matches this new puzzle's right part
	}



	system("pause");
	return 0;
}

Ganado here's the explanation:

"Piece" is a structure holding all information related to given jigsaw puzzle.

After taking 'N' - number of jigsaw puzzles, we define vector pieces which will hold all the jigsaw
puzzles and we input to it.

Now we define another vector pieces_pos - this will be our finaly output matrix.

Example input for program:

4 
1 x x a b 
2 x B c x 
3 A x x d 
4 C D x x 

Output:

1 2 
3 4 

The output need not be a square matrix.

Now about the for loop.
for(int i = 0 ;; i++) would have been for(;;), we just
are using the for-loop to keep looping until we manually break out of it.
We declared i because we can use that.

The outer for-loop has no purpose it just loops and keeps track of number of iteration (thinking of it like this helped me, but actually it has a very important role than just iterating, by keeping track of i).

But also, now we are using i in if (tolower(pieces_pos[0][i].right) == tolower(pieces[j].left)) { so now we can continue comparing the right most element instead of just the top left element.

The inner for-loop compares the element in question which is the right most element of the first row's right jigsaw part with every single jigsaw's left part.

If a match is found, we add that to the matrix by making IT the rightmost part. And we continue looping to find a jigsaw puzzle who's left part may match with this new puzzke's right part.

When no match is found, we stop for this row. Because we have assumed that the solution matrix is a rectangle. So there cannot be missing jigsaw elements.

Now after doing this we would have solved the first row. Now we find the jigsaw which comes below the topleft most jigsaw puzzle and do the same as above solve for the second row.
This is repeated until the matrix has as many elements as the given no. of jigsaw pieces.

This is under assumption that only two parts form a match that means not more than two puzzles have the same name. So only two puzzles can match. I.e there can only be two puzzles with 'a' as jigsaw part.


What do you think about this? Do you think there is a better way?

[Ganado]

Because reserve does not change the size of your array.

If you have

std::vector<int> my_vec;
my_vec.reserve(10);
my_vec[0] = 42;

The above is undefined behavior because my_vec[0] does not exist.

Looking at your code now.

[Grime]

	for (int i = 0 ;; i++) { // matches puzzles linearly for first row
		bool exists = false;
		for (int j = 0; j < N; j++) { // check if any puzzle matches right part
			if (tolower(pieces_pos[0][i].right) == tolower(pieces[j].left)) {
				pieces_pos[0].resize(i + 3);
				pieces_pos[0][i+1] = pieces[j];
				exists = true;
			}
		}
		if (!exists)
			break; // no puzzle match the right part so break
		// match was found, check if another puzzle matches this new puzzle's right part
	}

Why is pieces_pos[0][i+1] out of index?
If it were pieces_pos[0][i] it would compile just fine. and resize(i+3) were resize(i+2)

I'm assuming it's out of index because my console freezes.

Here is entire program by the way, once again.

#include <iostream>
#include <vector>
#include <string>
using namespace std;

struct piece {
	char ID;
	char top;
	char left;
	char bottom;
	char right;
};

int main() {

	int N; // number of puzzle pieces
	cin >> N; 

	vector <piece> pieces(N); // pieces
	vector < vector<piece> > pieces_pos(1); // matrix holding solution
	pieces_pos[0].resize(1);

	for (int i = 0; i < N; i++) { // takes input
		cin >> pieces[i].ID;
		cin >> pieces[i].top;
		cin >> pieces[i].left;
		cin >> pieces[i].bottom;
		cin >> pieces[i].right;

		if ((pieces[i].top == 'x') && (pieces[i].left == 'x')) {
			pieces_pos[0][0] = pieces[i]; // top left part of solution matrix
		}
	}

	for (int i = 0 ;; i++) { // matches puzzles linearly for first row
		bool exists = false;
		for (int j = 0; j < N; j++) { // check if any puzzle matches right part
			if (tolower(pieces_pos[0][i].right) == tolower(pieces[j].left)) {
				pieces_pos[0].resize(i + 3);
				pieces_pos[0][i+1] = pieces[j];
				exists = true;
			}
		}
		if (!exists)
			break; // no puzzle match the right part so break
		// match was found, check if another puzzle matches this new puzzle's right part
	}

	cout << '\n' << pieces_pos[0][0].ID << '\n';
	for (auto i : pieces_pos[0])
		cout << i.ID << '\n';

		
	system("pause");
	return 0;
}

[Ganado]

Redoing my post... I shouldn't be doing this so haphazardly.

I really suggest using a debugger if you're not sure when or why it "crashes".

In your case, it isn't crashing; you're stuck in an infinite loop. Which means exists is always getting set to true.

I think.

None of your arrays *seem* to be going out of bounds in your latest code, it's just an issue with logic.
In other words, lines 39-41 in your code are always being reached at least once in your inner (j) for loop.

[Repeater]

What input are you feeding it?

[Ganado]

Repeater, Grime is using Example input for program:

4 
1 x x a b 
2 x B c x 
3 A x x d 
4 C D x x 

(Expected) Output:

1 2 
3 4 

[Repeater]

Never leaves the for loop of line 35.

Here's some debugging information when I interrupted it running:

#1  0x0000555555554fb4 in main () at 036.cpp:39
39				if (tolower(pieces_pos[0][i].right) == tolower(pieces[j].left)) {
(gdb) print i
$1 = 55335051
(gdb) print j
$2 = 2

i = 55335051

That sure seems odd.

[E0p9LyTq]

How to reserve memory for 2D vectors?

Easiest way to do that:

Specify the size of a vector when you create the vector. Of any dimension(s).

You can even specify a default value other than zero when creating a sized vector.

Create a couple of functions to chain up the << operator and printing out a vector is as easy as outputting any Plain Old Data variable.

One neat feature of STL containers is they "drag" their size along with them, so passing a vector into a function there is no need to specify the size as an additional parameter.

#include <iostream>
#include <vector>
#include <numeric>

template<typename T>
void Print1DArray(std::vector<T> const&);

template<typename T>
void Print2DArray(std::vector<std::vector<T>> const&);

template <typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v);

template <typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<std::vector<T>>& v);

int main()
{
   // creating a sized vector
   std::vector<int> a1DVector(5);

   std::cout << "Displaying a sized 1D vector:\n";
   std::cout << a1DVector.size() << '\n';

   for (size_t itr = 0; itr < a1DVector.size(); itr++)
   {
      std::cout << a1DVector[itr] << ' ';
   }
   std::cout << "\n\n";

   // creating a sized vector filled with a value other than zero
   std::vector<int> another1DVec(8, 100);

   std::cout << "Displaying a filled 1D vector:\n";
   std::cout << another1DVec.size() << '\n';

   for (auto& itr : another1DVec)
   {
      std::cout << itr << ' ';
   }
   std::cout << "\n\n";

   std::cout << "Let's display that 1D vector again:\n";
   std::cout << another1DVec.size() << '\n';
   Print1DArray(another1DVec);
   std::cout << "\n\n";

   std::cout << "Let's display that 1D vector yet again:\n";
   std::cout << another1DVec.size()  << '\n' << another1DVec<< "\n\n";

   std::cout << "Creating a 2-dimensional vector, enter row size: ";
   int row_size;
   std::cin >> row_size;

   std::cout << "Enter column size: ";
   int col_size;
   std::cin >> col_size;

   std::cout << "\n";

   // create a 2 dimensional int vector with known dimensions
   std::vector<std::vector<int>> a2DVector(row_size, std::vector<int>(col_size));

   // initialize the vector with some values other than zero
   int start  = 101;
   int offset = 100;

   // step through each row and fill the row vector with some values
   for (auto& itr : a2DVector)
   {
      std::iota(itr.begin(), itr.end(), start);
      start += offset;
   }

   // let's display the filled 2D vector
   std::cout << "Displaying the filled 2D vector:\n";
   Print2DArray(a2DVector);
   std::cout << '\n';

   std::cout << "Let's display that 2D vector again:\n";
   std::cout << a2DVector;
}

template<typename T>
void Print1DArray(std::vector<T> const& a1DVec)
{
   for (size_t itr = 0; itr < a1DVec.size(); itr++)
   {
      std::cout << a1DVec[itr] << ' ';
   }
}


template<typename T>
void Print2DArray(std::vector<std::vector<T>> const& a2DVec)
{
   for (const auto& row_itr : a2DVec)
   {
      for (const auto& col_itr : row_itr)
      {
         std::cout << col_itr << ' ';
      }
      std::cout << '\n';
   }
}


template <typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v)
{
   for (auto const& x : v)
   {
      std::cout << x << ' ';
   }

   return os;
}

template <typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<std::vector<T>>& v)
{
   for (auto const& x : v)
   {
      std::cout << x << '\n';
   }

   return os;
}

Displaying a sized 1D vector:
5
0 0 0 0 0

Displaying a filled 1D vector:
8
100 100 100 100 100 100 100 100

Let's display that 1D vector again:
8
100 100 100 100 100 100 100 100

Let's display that 1D vector yet again:
8
100 100 100 100 100 100 100 100

Creating a 2-dimensional vector, enter row size: 4
Enter column size: 5

Displaying the filled 2D vector:
101 102 103 104 105
201 202 203 204 205
301 302 303 304 305
401 402 403 404 405

Let's display that 2D vector again:
101 102 103 104 105
201 202 203 204 205
301 302 303 304 305
401 402 403 404 405

[Grime]

Can't use my compiler right now. Are you sure it's in an infinite loop? But that shouldn't be happening. Then the compiler would give me an assertion fire vector or if index becuz I and j keep increasing.

Can you please put a cout statement and verify it? The inner loop cannot possibly be going into infinite loop, is it the outer loop?

edit: But on the other hand pieces_pos[0].resize(i + 3); keeps increasing the size. It was indeed an infinite loop with the outer loop.

After a small edit, this seems to work:

for (int i = 1 ;; i++) { // matches puzzles linearly for first row
		bool exists = false;
		for (int j = 0; j < N; j++) { // check if any puzzle matches right part
			if (tolower(pieces_pos[0][i-1].right) == tolower(pieces[j].left)) {
				pieces_pos[0].resize(i + 2);
				pieces_pos[0][i+1] = pieces[j];
				//pieces_pos[0].push_back(pieces[j]); // EDITED LAST
				exists = true;
			}
		}
		if (!exists)
			break; // no puzzle match the right part so break
		// match was found, check if another puzzle matches this new puzzle's right part
	}

	for (auto i : pieces_pos[0])
		cout << i.ID << '\n';

Will print 1 2 which is the correct order for the first row.

Now just need to include the entire thing inside another for-loop and we're done. I'll do that later if I have time.

[Enoizat]

if (!exists)
    break; // no puzzle match the right part so break 

If I understand your code, I think the only way to discover if there’s any match is to wait for all the iterations to finish.

What about outputting what your code does while it works?

Grime.dat:

4 
1 x x a b
2 x B c x
3 A x x d
4 C D x x

#include <fstream>
#include <iomanip>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>


struct piece {
    char ID     {};
    char top    {};
    char left   {};
    char bottom {};
    char right  {};

    piece() = default;
    explicit piece(std::string);

// friend
    friend std::istream& operator >>(std::istream& is, piece& rhs);
    friend std::ostream& operator <<(std::ostream& os, const piece& rhs);
};


piece::piece(std::string s)
{
    std::istringstream iss { s };
    iss >> *this;
}


std::istream& operator >>(std::istream& is, piece& rhs)
{
    is >> rhs.ID
       >> rhs.top
       >> rhs.left
       >> rhs.bottom
       >> rhs.right;
    return is;
}


std::ostream& operator <<(std::ostream& os, const piece& rhs)
{
    os << rhs.ID     << ' '
       << rhs.top    << ' '
       << rhs.left   << ' '
       << rhs.bottom << ' '
       << rhs.right;
    return os;
}


int main()
{
    // Let's take input from a file to make testing faster
    const std::string fname { "Grime.dat" };
    std::ifstream inf(fname);
    if(!inf) {
        std::cout << "Cannnot open " << fname << '\n';
        return 0;
    }

    int Num_Pieces;                         // number of puzzle pieces
    inf >> Num_Pieces; 

    std::vector <piece> pieces(Num_Pieces);

    // Matrix holding solution:
    std::vector < std::vector<piece> > pieces_pos(1, std::vector<piece>(1));

    // ID  top left bottom right
    //  1   x    x     a     b
    //  2   x    B     c     x
    //  3   A    x     x     d
    //  4   C    D     x     x
    for (int i = 0; i < Num_Pieces; ++i) {
        // Takes input:
        inf >> pieces.at(i);

        if ((pieces.at(i).top == 'x') && (pieces.at(i).left == 'x')) {
            std::cout << "pieces.at(" << i << ").top: " << pieces.at(i).top
                      << "; pieces.at(" << i << ").left: " << pieces.at(i).left
                      << '\n';
            pieces_pos.at(0).at(0) = pieces.at(i); // top left part of solution matrix
            std::cout << "pieces_pos.at(0).at(0): " << pieces_pos.at(0).at(0) << '\n';
        }
    }

    // Matches puzzles linearly for first row:
    std::cout << "\nLoop for 'matching puzzles linearly for first row':\n";
    // Addedd ---------\/ (additional exit condition)
    for (int i = 0; i < Num_Pieces; ++i) {
        bool exists = false;

        // Check if any puzzle matches right part
        for (int j = 0; j < Num_Pieces; ++j) {
            std::cout << "std::tolower(pieces_pos.at(0).at(" << i <<").right): "
                      << static_cast<char>(std::tolower(pieces_pos.at(0).at(i).right))
                      << "; std::tolower(pieces.at(" << j << ").left): "
                      << static_cast<char>(std::tolower(pieces.at(j).left)) << '\n';
            if (    std::tolower(pieces_pos.at(0).at(i).right)
                 == std::tolower(pieces.at(j).left))
            {
                exists = true;
                std::cout << "--- They match (exists == "
                          << std::boolalpha << exists << ")!\n";
                pieces_pos.at(0).resize(i + 3);
                pieces_pos.at(0).at(i+1) = pieces.at(j);
                std::cout << "pieces_pos.at(0).at(" << i + 1 << ") = "
                          << pieces.at(j) << "\n\n";
            } else {
                std::cout << "--- They do not match (exists == "
                          << std::boolalpha << exists << ").\n\n";
            }
        }

        // No puzzle match the right part so break:
        if (!exists) {
            std::cout << "***\nI'm going to break...\n***\n";
            break;
        }
        // Match was found, check if another puzzle matches this new
        // puzzle's right part
    }

    std::cout << '\n';
    for (const auto& i : pieces_pos.at(0)) {
        std::cout << i << '\n';
    }

    return 0;
}

Output:

pieces.at(0).top: x; pieces.at(0).left: x
pieces_pos.at(0).at(0): 1 x x a b

Loop for 'matching puzzles linearly for first row':
std::tolower(pieces_pos.at(0).at(0).right): b; std::tolower(pieces.at(0).left): x
--- They do not match (exists == false).

std::tolower(pieces_pos.at(0).at(0).right): b; std::tolower(pieces.at(1).left): b
--- They match (exists == true)!
pieces_pos.at(0).at(1) = 2 x B c x

std::tolower(pieces_pos.at(0).at(0).right): b; std::tolower(pieces.at(2).left): x
--- They do not match (exists == true).

std::tolower(pieces_pos.at(0).at(0).right): b; std::tolower(pieces.at(3).left): d
--- They do not match (exists == true).

std::tolower(pieces_pos.at(0).at(1).right): x; std::tolower(pieces.at(0).left): x
--- They match (exists == true)!
pieces_pos.at(0).at(2) = 1 x x a b

std::tolower(pieces_pos.at(0).at(1).right): x; std::tolower(pieces.at(1).left): b
--- They do not match (exists == true).

std::tolower(pieces_pos.at(0).at(1).right): x; std::tolower(pieces.at(2).left): x
--- They match (exists == true)!
pieces_pos.at(0).at(2) = 3 A x x d

std::tolower(pieces_pos.at(0).at(1).right): x; std::tolower(pieces.at(3).left): d
--- They do not match (exists == true).

std::tolower(pieces_pos.at(0).at(2).right): d; std::tolower(pieces.at(0).left): x
--- They do not match (exists == false).

std::tolower(pieces_pos.at(0).at(2).right): d; std::tolower(pieces.at(1).left): b
--- They do not match (exists == false).

std::tolower(pieces_pos.at(0).at(2).right): d; std::tolower(pieces.at(2).left): x
--- They do not match (exists == false).

std::tolower(pieces_pos.at(0).at(2).right): d; std::tolower(pieces.at(3).left): d
--- They match (exists == true)!
pieces_pos.at(0).at(3) = 4 C D x x

std::tolower(pieces_pos.at(0).at(3).right): x; std::tolower(pieces.at(0).left): x
--- They match (exists == true)!
pieces_pos.at(0).at(4) = 1 x x a b

std::tolower(pieces_pos.at(0).at(3).right): x; std::tolower(pieces.at(1).left): b
--- They do not match (exists == true).

std::tolower(pieces_pos.at(0).at(3).right): x; std::tolower(pieces.at(2).left): x
--- They match (exists == true)!
pieces_pos.at(0).at(4) = 3 A x x d

std::tolower(pieces_pos.at(0).at(3).right): x; std::tolower(pieces.at(3).left): d
--- They do not match (exists == true).


1 x x a b
2 x B c x
3 A x x d
4 C D x x
3 A x x d