How to initialize a 2d vector (after declaration)

cpit · #1 30-Oct-2009, 05:38

Hi all,

I would like to initialize a 2d vector in the class Graph.cpp according to an input "numNodes". Each element in the 2d vector must be an Arc object, which have attributes like "adj" and "weight".

I dont know which is the better way to initialize that 2d vector. Please, could you help me?

Here is my code and what I have tried.

CPP / C++ / C Code:

//Graph.cpp
#include "Graph.h"

void Graph::initGraph(int numNodes){
	vector< vector<Arc> > arcsTemp(numNodes, vector<Arc>(numNodes,Arc()));
	this->arcs = arcsTemp;

	
// ---- I tried this way but it didn't work as well :(
//	for(int i=0; i<numNodes;i++){
//		this->arcs[i] = vector<Arc>(numNodes,Arc());
//	}   

}

CPP / C++ / C Code:

//Graph.h
#include "Arc.h"
#include <vector>

class Graph {

	public:		
	vector< vector<Arc> > arcs; //<-- how to initialize this on Graph.cpp?
	
	public:
	void initGraph(int);

};

CPP / C++ / C Code:

//Arc.h
class Arc{
	public:
		bool adj;
		int weight;
};

In the main.cpp, I would like to call like:

Graph *graph;
graph->initGraph(4);
graph->arcs[0][1].adj = true;
graph->arcs[0][1].weight = 10;

Thanks in advance for your help.

cpit · #2 30-Oct-2009, 09:24

Hi all,

Actually I got what I wanted.

Just in case to help someone else. Here is the code!

obs.: There is also question in the bottom!

CPP / C++ / C Code:

//Graph.cpp
// -----GRAPH CONSTRUCTOR ------
   Graph::Graph(int numNodes){	
	for(int i=0; i<numNodes; i++){		
		this->arcs.push_back(vector<Arc>(numNodes,Arc())); 		
	}	
}

CPP / C++ / C Code:

//Graph.h
class Graph {

	public:		
	vector< vector<Arc> > arcs;
	
	public:
	Graph(int numNodes); //Constructor

}; //endclass Graph

CPP / C++ / C Code:

//Arc.h
class Arc{

	public:
		bool adj;
		int weight;
		int demands;

	public:		
	Arc(); //Constructor
		
}; //endClass Arc

In the main.cpp, we can use something like this:

Graph *graph(4);
graph->arcs[0][1].adj = true;
graph->arcs[0][1].weight = 10;

or
Graph graph(4);
graph.arcs[0][1].adj = true;
graph.arcs[0][1].weight = 10;

The question now is, Is there some performance difference in using a graph pointer or a graph object?

Kimmo · #3 01-Nov-2009, 04:57

CPP / C++ / C Code:

Graph *graph(4);
graph->arcs[0][1].adj = true;
graph->arcs[0][1].weight = 10;

Did you actually try out what happens when you compile this? What you probably mean is

CPP / C++ / C Code:

Graph* graph = new Graph(4);

Quote:

Originally Posted by cpit

The question now is, Is there some performance difference in using a graph pointer or a graph object?

Probably not, and even if there is, it's most probably so minor you'd never know the difference.

Then again, somehow I feel like you're actually talking about the allocation part of the process. I used a really crude timer to 'benchmark' your code. What I did was this:

CPP / C++ / C Code:

{
    Timer timer;
    for (int i = 0; i < 1000000; i++)
    {
        Graph *graph = new Graph(4);
        graph->arcs[0][1].adj = true;
        graph->arcs[0][1].weight = 10;
        delete graph;
    }
}
{
    Timer timer;
    for (int i = 0; i < 1000000; i++)
    {
        Graph graph(4);
        graph.arcs[0][1].adj = true;
        graph.arcs[0][1].weight = 10;
    }
}

The result for the above block was on average 12 seconds while for the below block it was on average 11.6-11.7 seconds. So yeah, there's a difference apparently. There's no reason to be concerned about such a thing, though, seeing your constructor do this:

CPP / C++ / C Code:

for(int i=0; i<numNodes; i++){		
		this->arcs.push_back(std::vector<Arc>(numNodes,Arc())); 		
	}

push_back allocates new memory each time you call it if there isn't enough memory to hold more values.

Just for the heck of it I passed 20 instead of 4 to the Graph constructor and the blocks then took about 2 minutes both. Next I rewrote the constructor as

CPP / C++ / C Code:

Graph::Graph(int numNodes){
    arcs.reserve(numNodes);
	for(int i=0; i<numNodes; i++){		
		this->arcs.push_back(std::vector<Arc>(numNodes,Arc())); 		
	}	
}

and behold, it only took a little less than a minute! The power of foresight is simply amazing!

I further changed the constructor into

CPP / C++ / C Code:

Graph::Graph(int numNodes){
    arcs.reserve(numNodes);
    std::vector<Arc> anArc(numNodes, Arc());
    for(int i=0; i<numNodes; i++){		
        this->arcs.push_back(anArc);
    }	
}

and got only about 35 seconds as the result. Amazing I tell you. I ran the test again with the original argument value of 4 and got a little over 5 seconds as the result.

You could probably go even further. So, yes, new seems expensive, but if you really want to save, you need to consider how much you're actually saving with for example using

CPP / C++ / C Code:

Graph graph(4);
            graph.arcs[0][1].adj = true;
            graph.arcs[0][1].weight = 10;

instead of

CPP / C++ / C Code:

Graph *graph = new Graph(4);
            graph->arcs[0][1].adj = true;
            graph->arcs[0][1].weight = 10;
            delete graph;

With a dummy constructor (and of course no member accessing) the whole deal was 0.5 seconds for the above and 0.1 for the below block.

Ps. I'd recommend ticking the "convert tabs into spaces" option in your editor if you haven't already.

Pps. In C++ there's also a struct data type. It is equal to a class in every way expect the data is public by default. Seeing as you insist on using public data you might as well use a struct.

cpit · #4 02-Nov-2009, 07:03

Hi Kimmo,

I really appreciate your effort and explanation on the performance.

A big thank.

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
run script command on ns2.26	newbie06	Computer Software Forum - Linux	66	16-Jan-2010 10:53
Error C2374	lolp1	C++ Forum	3	25-May-2008 16:40
Multiple questions for C++ project	devster420	C++ Forum	1	20-Apr-2007 21:26
The application failed to initialize properly (0xc0000005)	telstar2626436	Computer Software Forum - Windows	5	20-Dec-2005 01:01

How to initialize a 2d vector (after declaration)

Re: How to initialize a 2d vector (after declaration)

Re: How to initialize a 2d vector (after declaration)

Re: How to initialize a 2d vector (after declaration)