which is best container to use for this problem?

[whitmcrae]

I'm trying to set up a container of classes that each contain a point A and a point B, and this container's objects should follow a contiguous line (ie. index 0's point B is the same as index 1's point A). Here is an example of what I mean by this:

// A --> B --> C --> D
// |     |     |     |
//   [0]   [1]   [2]   etc. (array indexes) 

Because each connector point is shared between two connection classes I would like for each connection class to contain only one point (say point A, so the last connection would have no point B) as an attribute, and then a pointer/reference to the next rather than an entire copy (these points are fairly large, and of course upkeep would be much simpler with only a single object to change when required).

I cannot implement this just as a container of points because the connectors themselves also have attributes (and each connector must be able see both ends within the class itself). The problem is that vector<T> seems inefficient because of the constant deallocation/reallocation upon change, and I do not believe deque<T> or list<T> can be guaranteed to remain in the same location in order to use pointers (unless deque::pointer or list::pointer change along with reallocation??). Iterators also seem inefficient in this case, because then the connection class would have to be able to see the container it is within to know if the iterator is valid.

Note that there will be pretty substantial manipulation to both connection coordinates as well as connection attributes themselves during program run. Here is the basic implementation I would like to have (2 unknowns commented):

class CCoordinate
{
    // coordinate attributes
};

class CConnect
{
    CCoordinate  mPointA_;
    CCoordinate* mPointB_;    // pointer or reference, or container::pointer here??
    
    // connection attributes
};

std::container<CConnect> my_array; // which container type?? 

Any suggestions as to the best way to approach this would be greatly appreciated. Also, please note that this is not related to any schooling or homework assignment that I'm trying to have others do for me!

Thanks in advance for your advice on this!!!

[kev82]

A std::list<CCoordinate> gives you a container of points where the iterators do not invalidate regardless of what you do to the points

a std::vector<CConnect> gives you a container of connections where each connection will have a std::list<CCoordinate>::iterator for point a and point b.

It is then up to you to encapsulate these and always maintain the condition that point b of one connection is point a of the next.

[whitmcrae]

So in the above code if "std::list" replaces "std::container" then I would be guaranteed that pointer mPointB_ would never go invalid (so long as the index containing the actual point B is not erased from the list), regardless of what else is inserted deleted or where this takes place? This is not a guarantee for std::deque as well is it?

[kev82]

Firstly, it wouldn't be a pointer, it would be a std::list<CConnect>::iterator. Secondly, a std::list<> does not have a index. But yes, so long as the list element with point b in it existed in the list, then the iterator would be valid.

So in theory you could have

class CCoordinate;

class CConnect {
  CCoordinate point_a;
  std::list<CConnect>::iterator nextConection;
  CCoordinate &point_b() { return nextConnection->point_a; }
}

No it isn't for a std::deque. Any add/delete operation on a std::deque has the possibility of invalidating all iterators as far as I know.

[m4ster r0shi]

whitmcrae wrote:

Note that there will be pretty substantial manipulation to both connection
coordinates as well as connection attributes themselves during program run.

Could you be more specific here? How exactly do you intend to manipulate the data?

Do you need random access or is sequential access enough? Do you intend to
insert new connections in the middle or the beginning of your container often?

Can the way you use the data be separated in steps where one container may perform
better than another? For example, you may have a build phase in which you need blitz
fast insertion at any point and then a read phase in which you only need fast lookup.

It all depends on how you intend to use your data.

[whitmcrae]

It will actually be used to construct/manipulate a flight plan from a mission computer. Points may be added anywhere in the list through lookup tables, with connecting attributes auto-populated based on a number of internal databases.

Random access is needed for display in various ways, and of course to add/remove/shift to/from certain points, however this can be done using external functions to iterate to an index and return the value that way if random access is not built into the type (ie. with std::list).

Insertion will be on the fly (via key press) and blitz fast is not a priority as all insertion methods should be faster than the data transfer protocols to get from the computer to the display unit, but of course speed is always a priority when it comes to doing it the most efficient way! Insertion can also be automatic in the case of loading saved data from external files (which will be used frequently), and of course the speed of this load will ideally be quick enough to not notice at load/construct time.

Insertion can be anywhere in the list (generally middle, as the first and last point will generally be the first things keyed in), and certain types of insertion involve shifting while others involve copying, with connection attributes always existing between points.

Any advice as to the best way to handle all this would be greatly appreciated!

[m4ster r0shi]

It sounds to me like you want everything :D
Don't worry, this is not a bad thing. At all.

In this case, you need a fast access container on top
of a doubly linked list, as suggested above. However,
there are a couple of other things I'd like to point out.

I assume that your CCoordinates represent
waypoints of a route or something like that.

If you build/analyze each route separately and a
waypoint can't be the starting point of more than
one connections, you can just do something like this:

class CCoordinate
{
    // coordinate attributes

    // this -> next connection attributes

    CCoordinate * mNext_;
    CCoordinate * mPrevious_;
};

std::map<KeyType, CCoordinate *> my_route;

That is, build an intrusive list out of waypoints
(this saves you a whole level of indirection)
and use a map to index it. KeyType could be
a string, an int, or anything you think you'll
be using more often to access the waypoints.

If a waypoint can be the starting point of more than one
connections, you can't use an intrusive list for them.
You can do that for the connections though if they are
guaranteed not to belong to more than one routes.

In this case, CConnect instances should hold pointers
to waypoints. Note that you don't need to hold both
points in a connection, since point B of one connection
will always be point A of the next connection in the list:

class CCoordinate
{
    // coordinate attributes
};

class CConnect
{
    CCoordinate * mPoint_;

    // this -> next connection attributes

    CConnect * mNext_;
    CConnect * mPrevious_;
};

std::map<CoordKeyType, CCoordinate *> my_points;
std::map<ConnKeyType,  CConnect *>    my_route;

Using a reference to CCoordinate is not a good choice, because
you can't rebind a reference to another object after you initialize it.

I'm sure that you can figure out how you should lay things
out if a connection can be part of many different routes.

Oh, and something else. If the number of the elments stored in your map
is really big, a hashmap could be a better choice. I guess you could try both
std::map and a hashmap and see which one performs better in your case.

[whitmcrae]

Thanks so much for the well thought out answer and good advice as to which direction to go with this! I'll keep you posted down the road as to which method I find is most efficient as I get further in implementing it, just in case you are interested in a follow-up!! :)