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.

Code:

---

while(!inFile.eof())

---

Not a very good idea. http://faq.cprogramming.com/cgi-bin/...&id=1043284351

Quote:

---

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};

---

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

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().

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.

Quote:

---

Originally Posted by dwks

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;

---

>> 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.

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.

Well, at least my link help you even if I couldn't . . . .

Quote:

---

Originally Posted by Elysia

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. :)