effective C++ data structure to consider in this case_问答_开发者

Greetings code-gurus!

I am writing an algorithm that connects, for instance node_A of Region_A with node_D of Region_D. (node_A and node_D are just integers). There could be 100k+ such nodes.

Assume that the line segment between A and D passes through a nu开发者_高级运维mber of other regions, B, C, Z . There will be a maximum of 20 regions in between these two nodes.

Each region has its own properties that may vary according to the connection A-D. I want to access these at a later point of time.

I am looking for a good data structure (perhaps an STL container) that can hold this information for a particular connection.

For example, for connection A - D I want to store :

node_A, 
node_D, 
crosssectional area (computed elsewhere) , 
regionB, 
regionB_thickness, 
regionB other properties, 
regionC, ....

The data can be double , int , string and could also be an array /vector etc.

First I considered creating structs or classes for regionB, regionC etc . But, for each connection A-D, certain properties like thickness of the region through which this connection passes are different. There will only be 3 or 4 different things I need to store pertaining to a region. Which data structure should I consider here (any STL container like vector?) Could you please suggest one? (would appreciate a code snippet)
To access a connection between nodes A-D, I want to make use of int node_A (an index). This probably means I need to use a hashmap or similar data structure. Can anyone please suggest a good data structure in C++ that can efficiently hold this sort of data for connection A -D described above? (would appreciate a code snippet)

thank you!

UPDATE for some reasons, I can not make use of pkgs like boost. So want to know if I can use any libraries from STL

You should try to group stuff together when you can. You can group the information on each region together with something like the following:

class Region_Info {
  Region *ptr;
  int thickness;
  // Put other properties here.
};

Then, you can more easily create a data structure for your line segment, maybe something like the following:

class Line_Segment {
  int node_A;
  int node_D;
  int crosssectional_area;
  std::list<Region_Info>;
};

If you are limited to only 20 regions, then a list should work fine. A vector is also fine if you would prefer.

Have you considered a adjacency array for each node, which stores the nodes it is connected to, along with other data?

First, define a node

class Node
{
   int id_;
   std::vector<AdjacencyInfo> adjacency_;

}

Where the class AdjacencyInfo can store the myriad data which you need. You can change the Vector to a hashmap with the node id as the key if lookup speed is an issue. For fancy access you may want to overload the [] operator if it is an essential requirement.

So as an example

class Graph
{
     std::map<int, Node> graph_;
}

boost has a graph library: boost.graph. Check it out if it is useful in your case.

Well, as everyone else has noticed, that's a graph. The question is, is it a sparse graph, or a dense one? There are generally two ways of representing graphs (more, but you'll probably only need to consider these two) :

adjacency matrix
adjacency list

An adjacency matrix is basically a NxN matrix which stores all the nodes in the first row and column, and connection data (edges) as cells, so you can index edges by vertices. Sorry if my English sucks, not my native language. Anyway, you should only consider adjacency matrix if you have a dense graph, and need to find node->edge->node connections really fast. However, iterating through neighbours or adding/removing vertices in an adjacency matrix is slow, the first requiring N iterations, and the second resizing the array/vector you use to store the matrix.

Your other option is to use an adjacency list. Basically, you have a class that represents a node, and one that represents an edge, that stores all the data for that edge, and two pointers that point to the nodes it's connected to. The node class has a collection of some sort (a list will do), and keeps track of all the edges it's connected to. Then you'll need a manager class, or simply a bunch of functions that operate on your nodes. Adding/connecting nodes is trivial in this case as is listing neighbours or connected edges. However, it's harder to iterate over all the edges. This structure is more flexible than the adjacency matrix and it's better for sparse graphs.

I'm not sure that I understood your question completely, but if I did, I think you'd be better off with an adjacency matrix, seems like you have a dense graph with lots of interconnected nodes and only need connection info.

Wikipedia has a good article on graphs as a data structure, as well as good references and links, and finding examples shouldn't be hard. Hope this helps :
Link