Issues using comparator on std::map

6532e3e5e09db6f966770fdf86c03345
0
hellhound_01 104 Aug 26, 2012 at 12:58 c++

I try to implement my own comparator for a std::map to use a complex object as key value. I kow i could overwrite the less operator in my complex object, but I’ve decided to be more flexible, to use a comparator struct object instead. So I could perform different comparsions if required. I followed the instructions at this link: http://stackoverflow…map-with-struct

Here is my comparator, which is a protected member of my class, which holds the map:

struct Comparator : public std::binary_function<brCore::brConfigSet, brCore::brConfigSet, bool>
    {
        bool operator()(brCore::brConfigSet const & left, brCore::brConfigSet const& right) const
        {
            // comparison logic goes here
            return true;
        }
     };

And here is my map declaration:

typedef std::map<brCore::brConfigSet, boost::shared_ptr<brFont>, Comparator> Fonts_t;

The code compiles, but when I perform a find operation after I’ve added the first element to map, the find execution crashes with the hint that the less operator is missed.
But why? If I understand this article correctly the less operator isn’t required to be more flexible … Thanks for any help.

7 Replies

Please log in or register to post a reply.

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Aug 26, 2012 at 22:41

the find execution crashes with the hint that the less operator is missed

Please be more specific. What gave you the idea that it “hints” the less operator is missing?

Are you sure it is not an assert because your comparator is wrongly implemented? If you really always return true, there might be some debug code in the std::map implementation you’re using (which compiler?) that checks whether your implementation is consistent. If you always return true, it’s not consistent: a<b and b<a can’t be both true at the same time.

6532e3e5e09db6f966770fdf86c03345
0
hellhound_01 104 Aug 27, 2012 at 05:07

Solved. Thanks Oysin for the hint with the true value, this was the failure. As you have supposed the inconsistent return value throws an assert. I’ve not implemented the comparsion yet, but changing the return value to false, the check with the empty trunk passes succesfully.

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Aug 27, 2012 at 10:47

Yes, always returning false means that all keys are equal (because for any two items neither one is less than the other)

6532e3e5e09db6f966770fdf86c03345
0
hellhound_01 104 Aug 27, 2012 at 19:15

Here we are again … I’ve implemented my comparsion function:

class Comparator {
public:
   bool operator( )(const brCore::brConfigSet& set1, const brCore::brConfigSet& set2) const
   {      
      // check if number of registered config is less
      if(set1.getNumberOfConfigs()< set2.getNumberOfConfigs()){
          return true;
      }
      
      // only check if numbers are equals
      else if(set1.getNumberOfConfigs() == set2.getNumberOfConfigs())
      { 
          // check if any given config value is less      
          for(unsigned int i = 0; i< set1.getNumberOfConfigs(); i++)
          {                                       
            brCore::brConfig conf1 = set1.getConfig(i);
            brCore::brConfig conf2 = set2.getConfig(i);
            
            // first check key values
            if(conf1.getKey() < conf2.getKey()){
              return true;
            }
            
            // finally check config value
            if(conf1.asString() < conf2.asString()){
              return true;
            }
          }   
      }
      
      // return result is equal or grater               
      return false;
   }
};

This comparator checks if the values (each is a string) are less. This works successfully using MSYS
and MinGW, but same code crashes using MSVC 2010 compiler when find operation is performed:

typedef std::map<brCore::brConfigSet, std::string, Comparator> TestMap_t;
    TestMap_t map;
    
    brCore::brConfigSet set1("Testset1");
    brCore::brConfigSet set2("Testset2");
    
    brCore::brConfig conf1(std::string("value1"), "value1");
    brCore::brConfig conf2(std::string("value2"), "value2");
    
    set2.addConfig(conf1.getKey(), conf1);
    set2.addConfig(conf2.getKey(), conf2);  
        
    map.insert(std::pair<brCore::brConfigSet, std::string>(set1, "hallo"));
    map.insert(std::pair<brCore::brConfigSet, std::string>(set2, "buuuu"));
    
    for(TestMap_t::const_iterator p = map.begin( ); p != map.end( ); ++p) {
        cout << "Entry: " << " " << p->second << endl;
    }
    
    // create test search values
    brCore::brConfigSet set3("Testset2");
    brCore::brConfig conf31(std::string("value1"), "value1");
    brCore::brConfig conf32(std::string("value2"), "value1");   // value change at key results in crash
    
    set3.addConfig(conf31.getKey(), conf31);
    set3.addConfig(conf32.getKey(), conf32);
    
    TestMap_t::iterator iter = map.find(set3); // here crash (assert) happends on value change
    if(iter!=map.end()){
      cout << "Search successfull: " << iter->second << endl;
    }
    else{
      cout << "Search failed for: " << set3.getName() << endl;
    }

On MSVC I got an debug assertion as before with an invalid < operator.
The crash occures only if I change the the key of the second config object
to a less value than first A>B , i.e:

brCore::brConfig conf32(std::string("value"), "value1");

But only when I change the key value, if I change the value representation
no crash occurs, i.e.:

brCore::brConfig conf32(std::string("value2"), "value");

I’m running out of ideas why, and why only on MSVC with this
condition

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Aug 27, 2012 at 22:37

The problem lies in the fact that you check for conf1.getKey() < conf2.getKey() (and similar for asString()) in the inner loop, but not for >. You probably only want to actually continue the koop when both keys and strings compare equal. You should return false when conf1.getKey() > conf2.getKey().

6532e3e5e09db6f966770fdf86c03345
0
hellhound_01 104 Aug 28, 2012 at 05:08

You are right, indeed I only want to continue the inner loop if the values are equals. I’ve completly
forgotten that I’ve got an inner loop! Thanks again Oisyn for the beat to the back of the head ;)

6532e3e5e09db6f966770fdf86c03345
0
hellhound_01 104 Aug 28, 2012 at 20:23

I would report that your hint solves the issue now it is working! Thanks again …