Thread: dynamic array/vector help

  1. #1
    Registered User Cpro's Avatar
    Join Date
    Oct 2006
    Posts
    149

    dynamic array/vector help

    I'm creating a graph from vertices and edges read in from a file. The vertices and edges are stored in a hash-table structure, where the vetices are stored in an array, and each vertex points to a linked list of edges. Currently, everything works great. However, i need to make the array of vertices dynamic (i don't know how many vertices will be in the file). So, every time a vertex is read in from the file, a new position in the array is made for that vertex. So, I've heard vectors are used to make dynamic arrays. However, i'm running into some trouble with them (first time i've used vectors), and i need some help. Here is what my working program looks like:
    Code:
    struct edge
    {	
    	int source;
    	int target;
    	string label;
    	
    	edge *nextEdge;
    };
    struct vertex
    {
    	int id;
    	string label;
    	string color;	
    	int distance;	
    
    	edge *next;
    };
    
    int EndChain(edge *&currentEdge);
    int InsertEdge(edge *currentEdge, vertex *array1[], int tempSource, int tempTarget, string tempLabel2, string firstChar);
    int InsertVertex(vertex *array1[], int tempId, string tempLabel);
    
    //table size must me 1 more than the number of vertices.
    #define tableSize 100
    
    int main(int argc, char* argv[])
    {
    	ifstream inFile ( argv[1] );
    
    	if ( !inFile.is_open() )
    	{
    		cout << "Could not open file." << endl;
    	}
    	else
    	{		
    		string firstChar;	
    		vertex *array1[tableSize] = {NULL};
    		edge *currentEdge;
    		currentEdge = NULL;		
    		
    		//Temp variables for vertex.
    		int tempId;
    		string tempLabel;
    
    		//Temp variables for edge.
    		int tempSource;
    		int tempTarget;
    		string tempLabel2;		
    		
    		while(!inFile.eof())
    		{		
    			inFile >> firstChar;			
    
    			//If the first character is %, ignore the rest of the line.
    			if(firstChar == "%")
    			{				
    				inFile.ignore(10000, '\n');
    			}
    			//If the first character is a v, create a vertex.
    			else if(firstChar == "v")
    			{
    				inFile >> tempId >> tempLabel;	
    				InsertVertex(array1, tempId, tempLabel);
    			}			
    			//Create a directed edge.
    			else if(firstChar == "d")
    			{
    				inFile >> tempSource >> tempTarget >> tempLabel2;
    				InsertEdge(currentEdge, array1, tempSource, tempTarget, tempLabel2, firstChar);
    			}
    			//Create an undirected edge.
    			else if(firstChar == "u")
    			{	
    				inFile >> tempSource >> tempTarget >> tempLabel2;
    				InsertEdge(currentEdge, array1, tempSource, tempTarget, tempLabel2, firstChar);
    				InsertEdge(currentEdge, array1, tempTarget, tempSource, tempLabel2, firstChar);
    			}			
    			else
    			{				
    			}			
    		}		
    		
    	}
    	
    	cout << endl; 
    	cin.get();
    	return 0;
    }
    //Go to the end of edge chain to insert.
    int EndChain(edge *&currentEdge)
    {
    	while(currentEdge->nextEdge != NULL)
    	{
    		currentEdge = currentEdge->nextEdge;
    	}
    	return 0;
    }
    int InsertEdge(edge *currentEdge, vertex *array1[], int tempSource, int tempTarget, string tempLabel2, string firstChar)
    {	
    	//If no edge exists for current vertex.
    	if(array1[tempSource]->next == NULL)
    	{
    		array1[tempSource]->next = new edge;
    		currentEdge = array1[tempSource]->next;
    		currentEdge->source = tempSource;
    		currentEdge->target = tempTarget;
    		currentEdge->label = tempLabel2;
    		currentEdge->nextEdge = NULL;						
    	}
    	//If an edge already exists for current vertex.
    	else
    	{
    		currentEdge = array1[tempSource]->next;
    		//Go to end of chain of edges to insert new edge.
    		EndChain(currentEdge);
    
    		currentEdge->nextEdge = new edge;
    		currentEdge = currentEdge->nextEdge;
    		currentEdge->source = tempSource;
    		currentEdge->target = tempTarget;
    		currentEdge->label = tempLabel2;
    		currentEdge->nextEdge = NULL;						
    	}	
    
    	return 0;
    }
    int InsertVertex(vertex *array1[], int tempId, string tempLabel)
    {
    	array1[tempId] = new vertex;
    	array1[tempId]->id = tempId;
    	array1[tempId]->label = tempLabel;
    	array1[tempId]->next = NULL;
    
    	return 0;
    So, i thought i just needed to declare a vector, and switch everything that is an array to the vector. I started out by declaring a vector like:
    Code:
    vector<vertex> *vertexArray;
    Then i replaced all my function calls with array1 to vertexArray. Then i went to access the members of vertex, but i couldn't figure out how to do it.
    Code:
    array1[tempId]->id = 5;
    
    vertexArray[tempId]->...   ???
    I couldn't access the members of vertex with the vector like i did for the array. I was looking at some examples about vectors, but none of them used structs.

    Anyways, i'm looking for the simplest way to convert this program into using a dynamic array, where a new position in the array is created every time a new vertex is read in from the file. If this can be done in an easier way than using a vector, i'm open to suggestions. However, a vector is the only way i've heard that can do this. I also have breadth-first, depth-first, and topological sort functions that are all based on a fixed size array. So, the easiest way to covert this program into a dynamic array, the better.

    Any help would be appreciated.

    PS: I'm sure i'll have some more questions about using vectors for my program, so i'll keep posting on this thread.
    IDE - Visual Studio 2005
    Windows XP Pro

  2. #2
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    Code:
    while(!inFile.eof())
    Not a very good idea. http://faq.cprogramming.com/cgi-bin/...&id=1043284351

    I was looking at some examples about vectors, but none of them used structs.
    Most of the time, with vectors, you just use something like this.
    Code:
    std::vector<int> intvector;
    std::vector<std::string> stringvector;
    struct struct_type {
        std::string key;
        int value;
    };
    std::vector<struct struct_type> structvector;
    (Though the last example would be a good case for a map.)

    This
    Code:
    vector<vertex> *vertexArray;
    is a pointer to a vector of vertexes. You'd only want that if you were planning to dynamically allocate the vector or pass it into a function (in which case you might want to use a reference instead).

    Sometimes, one might use
    Code:
    vector<vertex *> vertexArray;
    for a vector of pointers to vertexes. For example:
    Code:
    vertex *v = new vertex;
    vector<vertex *> vertexArray;
    
    vertexArray.push_back(v);
    But that means you have to free the data, of course. However, I think this last version is what you're looking for in your code. It's the closest translation to this, at least.
    Code:
    vertex *array1[tableSize] = {NULL};
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  3. #3
    Registered User Cpro's Avatar
    Join Date
    Oct 2006
    Posts
    149
    Ok, i went with
    Code:
    vector<vertex *> vertexArray;
    Now, i guess i can't create a new vertex like i did with the array. This doesn't work:
    Code:
    int InsertVertex(int tempId, string tempLabel)
    {
    	vertexArray[tempId] = new vertex;	
    	vertexArray[tempId]->id = tempId;
    	vertexArray[tempId]->label = tempLabel;
    	vertexArray[tempId]->next = NULL;	
    	
    	return 0;
    }
    I think it's crashing here.
    I need to create a new vertex in tempId position. So, if tempId = 1, then i need to create a new vertex in position 1 in the vector.
    How would i go about doing this?

    Thanks
    IDE - Visual Studio 2005
    Windows XP Pro

  4. #4
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    Code:
    vertexArray[tempId] = new vertex;
    As you have discovered, with vectors you can't just access any element and have it spring into existence. (You can with other containers, but not vectors.) You have a few options:
    • Use std::vector::push_back() to add an element to the end of the vector. Of course, this only works at the end.
    • Use std::vector::insert() to insert an element between two other elements. This will mess up the order of the elements, however.
    • Use std::vector::reserve() to allocate enough space for a certain number of members. Then you can use the vector like an normal array.
    • I'm sure there are other options. Browse this for details. http://cppreference.com/cppvector/index.html

    The third option is probably what you want. Instead of just doing this every time
    Code:
    vertexArray[tempId] = new vertex;
    do something like this.
    Code:
    if(tempId >= vertexArray.size()) {
        vertexArray.reserve(tempId + 1);
    }
    
    vertexArray[tempId] = new vertex;
    That way, if the vector only has 4 elements, and you try to access element 6, it will expand to seven elements so that [6] is valid. ([4] and [5] will be uninitialized, but that's what you get with arrays, too.)

    If you can get the elements in the right order, you can just use push_back().
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  5. #5
    Registered User Cpro's Avatar
    Join Date
    Oct 2006
    Posts
    149
    Works great now. The conversion to a dynamic array went a lot smoother than i thought it would.

    Thank you very much for the help.
    IDE - Visual Studio 2005
    Windows XP Pro

  6. #6
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by dwks View Post
    Code:
    std::vector<int> intvector;
    std::vector<std::string> stringvector;
    struct struct_type {
        std::string key;
        int value;
    };
    std::vector<struct struct_type> structvector;
    Are we working in C now?

    This is C++, so let's get rid of the ugly struct syntax:
    Code:
    std::vector<struct_type> structvector;
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  7. #7
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    >> Use std::vector::reserve() to allocate enough space for a certain number of members. Then you can use the vector like an normal array.

    This is incorrect. You should be using resize if you want to do it like this. The resize function creates new entries in the vector that you can access with array syntax. The reserve function only allocates memory for them, but you still would have to use push_back (or something else) to create the object.

    It probably for you, Cpro, only accidentally because you are storing pointers. However, the internal data in the vector will be incorrect and you could have real problems going forward.

  8. #8
    Registered User Cpro's Avatar
    Join Date
    Oct 2006
    Posts
    149
    Ya, reserve wasn't working for me. So, I went to that link dwks posted and found resize, and it worked. I probably should have said this in my last post to clarify what i actually used.
    IDE - Visual Studio 2005
    Windows XP Pro

  9. #9
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    Well, at least my link help you even if I couldn't . . . .

    Quote Originally Posted by Elysia View Post
    Are we working in C now?

    This is C++, so let's get rid of the ugly struct syntax:
    Code:
    std::vector<struct_type> structvector;
    I left it in, because I think it's clearer. I meant to make a note about it, but I forgot.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 07-11-2008, 07:39 AM
  2. Replies: 4
    Last Post: 11-02-2006, 11:41 AM
  3. Identify dynamic IP address of network device
    By BobS0327 in forum Tech Board
    Replies: 2
    Last Post: 02-21-2006, 01:49 PM
  4. operator overloading and dynamic memory program
    By jlmac2001 in forum C++ Programming
    Replies: 3
    Last Post: 04-06-2003, 11:51 PM
  5. Dynamic memory confusion
    By ripper079 in forum C++ Programming
    Replies: 5
    Last Post: 11-04-2002, 06:15 PM