STL map for an struct defined in ANSI C

Question

I am coding in a mixed C/C++ environment. I have an struct in C part and I would like to collect it in a map container in C++ part. I think I should define a custom key_compare function object, and let STL map::insert() orders nodes. However I don't know how can I modify map container to customize map::find() function. I am looking for a way to customize map::find() function to do something more that key_compare function for equivalence checking.

Would you please let me know how I can put these functions into STL::map or STL::set ?

here is my struct in C part (compile with gcc):

typedef struct  iotrace_arh_node 
{
    double time;
    unsigned long long int blkno;
    int bcount;
    u_int flags;
    int devno; 
    unsigned long stack_no;
} iotrace_arh_node_t;

here is my proposed key_compare and equivalence checking function for find() in the C++ part (compile with g++):

int key_compare ( struct iotrace_arh_node tempa, struct iotrace_arh_node tempb )
{
return (tempa.blkno-tempb.blkno);
}


int key_equal( struct iotrace_arh_node tempa, struct iotrace_arh_node tempb )
{
    if( (tempa.blkno == tempb.blkno) && (tempa.bcount == tempb.bcount) )
        return 0; // tempa and tempb is equal, node fund in the map
    else if ( (tempb.blkno < tempa.blkno)  )
        return -1;  //tempb is less than tempa
    else if ( (tempb.blkno >= tempa.blkno) && ( tempb.blkno + tempb.bcount < tempa.blkno + tempa.bcount) )      
        return 0; // tempa and tempb is equal, node fund in the map
    else
        return 1;  //tempb is grater than tempa
}

Answer 1

To use the type as the key in a map or set, you need to provide a "less-than" comparison, which takes two arguments and returns true if the first should come before the second. The easiest way to use it in a set is to define it as a function object:

struct key_compare {
    bool operator()(const iotrace_arh_node & a, const iotrace_arh_node & b) {
        return a.blkno < b.blkno;
    }
};

and use it as the "comparator" template argument in the map or set:

typedef std::set<iotrace_arh_node, key_compare> node_set;

If you need different ways of comparing the keys, then you can create different sets with different comparators. However, you can't change the comparator once the set is created; the objects in the set are stored according to the order defined by the comparator, so changing it would make the set unusable. If you need to search the same set by different fields, then have a look at Boost.MultiIndex

You don't need to provide an equality comparison.

Answer 2

Standard compare functions differ in C and C++. In C, as you written, you return -1, 0 or 1 when first argument is lesser, equal or greater than the second one. But in C++ you should either overload the < operator, or write a compare function which does the same as < operator and give its name to STL functions. But you should make sure that your < should be transitive (i.e. a<b && b<c => a<c) It means that your key_compare function should be like:

bool key_compare ( const struct iotrace_arh_node& tempa, const struct iotrace_arh_node& tempb )
{
return (tempa.blkno < tempb.blkno);
}

There is no need to define key_equal, because (k1 == k2) <=> (!(k1<k2)&&!(k2<k1)). And AFAIK you can not use different compare functions when you insert and find.

Answer 3

For the comparer, see here: STL Map with custom compare function object

struct my_comparer
{
   bool operator() ( const struct iotrace_arh_node& left, const struct iotrace_arh_node& right )
   {
      return left.blkno < rigth.blkno);
   }

}

The comparer must be a binary predicate, not a simple function.

Then you can use it in a Map:

std::map<Key, Data, Compare, Alloc>

(look here: http://www.cplusplus.com/reference/stl/map/ )

Compare and Alloc have default values.

What is your key-type, btw?

hth

Mario