array of unknown length in a class

[qmech]

First timer poster...

I'm having a bit of a problem formulating my question, so please bare with me...

I've done a lot of programming in a lot of languages, from obscure to common - but somehow I always avoided C and C++. Well, I recently decided to fix this glaring fault in my upbringing and decided to do my next project in C++ (I have done some C programming, but not a lot).

I'm *trying* to do The Right Thing and not think in terms of the languages I know and simply "translating" that into C++. This would be especially bad considering that I've not done a lot of OOP...

My problem, then, is this:

I want to describe a bunch of "nodes" connected in some manner (a mesh). So, trying to think in OO terms, the right thing to do would seem to be to make a node class (and a mesh class, in which the node appears). An instance of a node needs to contain, among other things, information about the other nodes it is connected to.

A node can be connected to any number of other nodes (all, some or none), so the question is how is this property best described in the node class?

My simple non-C++ way of thinking would just use a dynamic array to store this information. IOW something along the lines of:

class MyNodeClass {
public:
int connections[];
};

where the connections array would just contain a list of all the node id's, that the node is connected to.

(I know I shouldn't use the code as above, it's there to explain my line of thinking)

What's The Right Way of implementing this in C++? Do I dynamically allocate memory for array on creation (I would rather avoid STL and similar solutions). Should I look at using linked lists? Am I just being completely dense? (always a possibility)

Any insight would be greatly appreciated.

[answer]

I don't know what larger problem you are trying to solve. But to me it seems just having a node class is fine.


class Node {
public:
Node* othernodes[MAX_CONNECTIONS]
}
// Or ...
class Node{
public:
Node** other_nodes; // This requires new/delete to resize as necessary
}

// I would preffer below

class Node{
public:
vector<Node*> other_noes;
}


Perhaps try solving simpler problems in C++, that you could word well first. This way you will have more experience points and gain enough levels to attack a larger problem like this more easily.

[john_avi]

I think you should use linked list for storing the nodes connected. As a node connects to a new node append the ID of new node in linked list dynamically. to me it seems the best solution.

[laserlight]

A node can be connected to any number of other nodes (all, some or none), so the question is how is this property best described in the node class?
Generally, the idea would be to have a container of pointers to the neighbour nodes. The node does not own its neighbours, so it will not be responsible for managing the memory of its neighbours.

Which container to use depends on what is needed. For example, do you often need random access to neighbour nodes (perhaps a vector will do)? Do you need to delete individual nodes (perhaps a container of weak_ptr is desirable)?

[Paul McKenzie]

What's The Right Way of implementing this in C++? Do I dynamically allocate memory for array on creation (I would rather avoid STL and similar solutions). Should I look at using linked lists? Am I just being completely dense? (always a possibility)What is your reason for avoiding STL? It is part of the C++ standard library. You will get your work finished much faster and have less (maybe no) bugs if you use the well-tested standard components.

Please take a look here:

http://www.parashift.com/c++-faq-lite/containers.html#faq-34.1

Everything you mentioned, vectors, linked lists, maps, queues, etc. are available to you to create your final application. There is no need to reinvent the wheel, and especially if you do not know C++ very well. For example, it isn't easy as just dynamically allocating memory and deleting memory to use a dynamic array properly within a class. There are a whole host of other issues -- copy/assignment, exception safety, etc. that arise. All this is taken care of by the container classes (as the FAQ above states).

Regards,

Paul McKenzie