Geek asks and answers

How to build a tree structure in C ++ using std :: map

I am trying to write a tree type structure in C ++. As in every tree there are branches and leaves. The branch may contain other branches, as well as leaves. Now my implementation requires that each branch and leaf have different functionality. For example. Take a tree structure

                                          Root                                             
                                |                          |                             
                             Branch1                     Branch2                     Branch3
      |                |                |
    Leaf1            Leaf2           Branch4

Now each leaf and branch has a different function to execute, so Leaf1 will have a function called leaf1_func, Leaf2 will have leaf2_func, Branch4 has Branch4_func.

At first I tried to implement a composite design structure. But that means that I will have as many classes as there are leaves. But since I have tons of leaves and branches, I would like to avoid creating classes. I understand that this is an unusual situation, but I hoped that someone could help me in this regard. What would be the best way to implement this tree without creating too many classes.

I use the STL container for data storage, I want to use this tree implementation to solve this problem in TSP.

#include <cstdlib>
#include <iostream>
#include <map>

using namespace std;

int n=4;
int min=1, max=10;




struct graph
{
int nodes;//total no. of nodes or vertices namely cities
std::map<std::pair<int,int>, int> graphMap;//an object that links a pair of vertices   
};


void directed_Graph(graph);

void directed_Graph(graph G)
{
//int n = G->nodes; //city count
int i, j;
for(i = 0; i <= n-1; i++)
{
    for(j = 0; j <= n-1; j++)
    {
        if(i!=j)
        {
            G.graphMap[std::make_pair(i,j)] = (rand()%10)+1;
            //cout<<G.graphMap[std::make_pair(i,j)]<<"\n";
        }

        else
        {
            G.graphMap[std::make_pair(i,j)] = 0;
        }

    }
}
}


int main(int argc, char** argv) 
{
graph g;
g.nodes = 4;

directed_Graph(g);

return 0;
}
+3
source share
3 answers

. , , , void * ( ), node.

struct node {
    void (*fptr)(); // pointer to any function taking no args, no return
    void *data; // pointer to anything, need to cast before using
};

void f() { std::cout << "hello"; }
void g() { std::cout << "world"; }

node a = { f, f };
node b = { g, g };

a.fptr();
static_cast< void (*)() >( b.data )();

. , .

, .

+1

, , . , STL . .

, . -, , .

#include <set>

int foo( ) {
  return 5;
}

std::set< int (*)( ) > my_set;
my_set.insert( &foo );

, , .. . , , , .. .

, , - . , - .

#include <set>
#include <iostream>

struct base {
  virtual void print( ) const = 0;
};

struct derived1 : public base {
  void print( ) const { std::cout << "derived1" << std::endl; }
};

struct derived2 : public base {
  void print( ) const { std::cout << "derived2" << std::endl; }
};

std::set< base* > my_set;

my_set.insert( new derived1( ));
my_set.insert( new derived2( ));

, , - , , , :

bool operator < ( base const * const b1, base const * const b2 ) {
  // Figure out which is less here.
}

, -, , . , , , , node, , .

0

If you have a limited depth of the tree, it is convenient to describe it like this:

typedef std::map<std::string, double> action_map_t;
typedef std::map<std::string, action_map_t> objid_map_t;
typedef std::map<std::string, objid_map_t> objtype_map_t;

objtype_map_t m_mapTooltipDuration;

m_mapTooltipDuration[objtype][objid][action] = atof(duration.c_str());
0
source

More articles:


All Articles