当前位置: 动力学知识库 > 问答 > 编程问答 >

C++ adjacency list of pointers and structs

问题描述:

Working on adjacency list --> directed weighted graph

One class looks like this, i.e. header:

class CGraph;

class CMap {

public:

//voided constructors and destructors

//functions one is:

void SetDirGraph(string commands);

private:

CGraph* m_myMap;

};

Second class:

class CNode {

public:

//voided constructor and desctructor

int m_distance, m_vert;

bool m_isKnown;

};

typedef struct edges {

int v2, weight;

} edge;

class CGraph {

public:

CGraph(int map_size);

~CGraph(void);

void AddMap(int v1, int v2, int weight);

void AddEndVert(int v2, int weight);

private:

list<edge> List;

int size;

public:

CNode* verts;

};

I'm reading vertices from a file, and that works. My problem is I am having trouble creating an adjacency list based on the code given. I'm trying to use pointers first that points to a list and it is not working correctly. I don't know how to create my pointers to the list without writing over them.

void CMap::SetDirGraph(string command) {

istringstream buffer(command)

char ch;

int num, vert1, vert2, weight; //specify vertices and weight and number of vertices

buffer>>ch; //throw away first character (not needed)

buffer>>num // size of vertices

while(!buffer.eof()) { // keep reading until end of line

buffer>>v1; // vertex start

buffer>>v2; // vertex end

buffer>>weight;

m_myMap = new CGraph(map_size); //initialize m_myMap.

m_myMap->verts->m_vert = v1; // mymap->verts->vert points to first edge

m_myMap->AddMap(v1, v2, weight); // create list?

m_myMap->AddEndVert(v2, weight); //create list? push v2 and weight on my list using my list.

}

}

I've tried several different ways and I keep confusing myself, any point in the right direction would be awesome.

EDIT:

I have more code too if needed to be produced, just publishing the main stuff.

What I mean by "not working" is that I am just writing over the previous vertex. I don't know if I should create an array using m_myMap (tried and still writes over and get a memory error as well). No compiler errors.

网友答案:

I don't know how to create my pointers to the list without writing over them.

Apart from your application, the answer to this question is the new operator, which I assume you are aware of, since you used it within your example code. Code like int * a = new int(42); allocates memory for an int on the heap and you are responsible for cleaning it up when it is not needed anymore. You thereby have full control over how long a variable will be available. In int x = 42; int * a = &x; on the other hand, x will automatically be cleaned up when it runs out of scope, and a will be a pointer to a memory block that has no meaningful data in it anymore. If you try to dereference it, you will encounter undefined behavior, and, if you are lucky, your program will blow up.

If you can use the C++11 standard, or a library that offers smart pointers, you should prefer those over managing the pointer yourself whenever possible. A smart pointer is an object that holds the allocated memory and frees it automatically when it is destructed. More specific information depends heavily on which sort of smart pointer you are using. The reason for using smart pointers is that doing the management yourself is tedious and error prone. If you do not delete your pointers you had allocated, your application will keep on allocating more memory until it blows up some day (depending on how often and how much memory you allocate); this is called leaking. If you call delete more than once, your program will bail out as well. Here is an example of C++11 shared_ptr in your application:

class CMap
{
  private:
    std::shared_ptr<CGraph> m_myMap;
  // etc.
};

// in SetDirGraph
m_myMap.reset(          // if the smart pointer has previously been managing
                        // memory, it will free it before allocating new
  new CGraph(map_size)  // allocate CGraph as before
);

Besides that, what hopefully answers your question, I have run into several potential problems concerning your code:

  • Definitely wrong: In SetDirGraph you set m_myMap->verts->m_vert = v1. m_myMap->verts is a pointer. You have freshly created m_myMap and thus verts is not initialized, hence pointing at a random block of memory. You then try to dereference it by m_myMap->verts->m_vert = v1. This cannot work. You need to create verts first, i.e. verts = new CNode;.

  • typedef struct edges { /* etc */ } edge; is a C construct and there is no need for the typedef wrapper in C++. It does work and all, but it is really redundant and lots of those constructs just pollute the namespace you are working in.

  • Do you really need pointers in the first place? Your provided snippets do not hint at why you would need to use them. You will want to reduce usage of pointers to a minimum (or at least use smart pointers, see above)

分享给朋友:
您可能感兴趣的文章:
随机阅读: