std::map::find is not finding a match, but if i loop thru begin() to end() i see the match right there

Question

struct chainout {
    LONG cl;
    std::string cs;
    bool operator<(const chainout&o)const {
      return cl < o.cl || cs < o.cs;
    }
  } ;
  struct chainin{
    std::string tm;
    std::string tdi;
    short mss;
    LONG pinid;
    bool operator<(const chainin&o)const {
      return  mss < o.mss || pinid < o.pinid || tm<o.tm; //no tdi right now it's always empty
    }
  };
  std::map   <chainin,chainout> chainmap;
  std::map<chainin,chainout>::iterator it;
  chainin ci;
  chainout co;


 string FADEDevicePinInfo::getNetAtPinIdTmTidMss (const LONG p,const string tm, const string tid,const LONG mss){

  ci.tm=tm;
//  ci.tdi=tid;
  ci.tdi="";
  ci.mss=(short)mss;
  ci.pinid=p;
  for (it=chainmap.begin();it!=chainmap.end();it++){
    if(it->first.pinid==ci.pinid && it->first.tm==ci.tm&&it->first.mss==ci.mss && it->first.tdi==ci.tdi){
      cout << "BDEBUG: found p["; cout<<it->first.pinid; cout<<"] tm["; cout<<it->first.tm.c_str();cout<<"] mss[";cout<<it->first.mss;cout<<"] : ";cout<<it->second.chainSignal.c_str();cout<<endl;
    }
  }
  it=chainmap.find(ci);
  if(it == chainmap.end()){
    MSG(SEV_T,("no pin data found for pin[%ld]/tm[%s]/tdi[%s]/mss[%ld]",ci.pinid,ci.tm.c_str(),ci.tdi.c_str(),ci.mss));
  }
  return it->second.cs;
}

This is both printing the successfully found line, and then throwing the sev_t error due to map::find not returning a match. what did i do wrong?

I added print statements thruout the < function, but it seems to be ordering the map correctly, and when i do the lookup, it seems to find the correct mss/pinid, but then only sees one tm, which is the wrong tm.

Pop quiz: you have to `chainout`s, one has `cl=3`, and `cs="B"`, and the other one has `cl=4` and `cs="A"`. Which one is less than the other one? Your `<` will conclude that either one of them is less than the other one. As Mr. Spock would say: this is not logical. This `<` operator fails to implement strict weak ordering, and this results in undefined behavior and [demons flying out of your nose](https://en.wiktionary.org/wiki/nasal_demon), as you've observed. — Sam Varshavchik, Jul 15 '20 at 18:29

score 4 · Accepted Answer · answered Jul 15 '20 at 18:40

As noted in comments, you have a bad comparison operator. If you don't know what order the objects should be sorted in, then neither does std::map or any other sorted container.

When you have multiple things to compare, consider deciding which is most important, and use std::tie to compare them, as demonstrated here:

#include <string>
#include <iostream>

struct chainout {
    int cl;
    std::string cs;
    bool operator<(const chainout&o)const {
        return std::tie(cl, cs) < std::tie(o.cl, o.cs);
    }
};

int main(){
    chainout a{ 1, "b" };
    chainout b{ 2, "a" };
    std::cout << (a < b) << std::endl;
    std::cout << (b < a) << std::endl;
}

Remy Lebeau · Answer 2 · 2020-07-15T19:51:11.880

The operator< for both of your structs are implemented incorrectly.

std::map requires key comparisons to use Strict Weak Ordering. That means when your structs want to compare multiple fields, they need to compare later fields only when earlier fields compare equal. But you are not checking for that condition. You are returning true if any field in one instance compares less-than the corresponding field in the other instance, regardless of the equality (or lack of) in the other fields. So you are breaking SWO, which causes undefined behavior in std::map's lookups.

Try this instead:

struct chainout {
    LONG cl;
    std::string cs;
    bool operator<(const chainout &o) const {
        /*
        if (cl < o.cl) return true;
        if (cl == o.cl) return (cs < o.cs);
        return false;
        */
        return (cl < o.cl) || ((cl == o.cl) && (cs < o.cs));
    }
};

struct chainin{
    std::string tm;
    std::string tdi;
    short mss;
    LONG pinid;
    bool operator<(const chainin &o) const {
        if (mss < o.mss) return true;
        if (mss == o.mss) {
            if (pinid < o.pinid) return true;
            if (pinid == o.pinid) return (tm < o.tm);
        }
        return false;
    }
};

An easier way to implement this is to use std::tie() instead, which has its own operator< to handle this for you, eg:

struct chainout {
    LONG cl;
    std::string cs;
    bool operator<(const chainout &o) const {
        return std::tie(cl, cs) < std::tie(o.cl, o.cs);
    }
};

struct chainin{
    std::string tm;
    std::string tdi;
    short mss;
    LONG pinid;
    bool operator<(const chainin &o) const {
        return std::tie(mss, pinid, tm) < std::tie(o.mss, o.pinid, o.tm);
    }
};

Either way, then std::map::find() should work as expected, eg:

std::map<chainin, chainout> chainmap;

string FADEDevicePinInfo::getNetAtPinIdTmTidMss (const LONG p, const string tm, const string tid, const LONG mss)
{
    chainin ci;
    ci.tm = tm;
    //ci.tdi = tid;
    ci.tdi = "";
    ci.mss = (short) mss;
    ci.pinid = p;

    std::map<chainin, chainout>::iterator it = chainmap.find(ci);
    if (it != chainmap.end()) {
        cout << "BDEBUG: found"
             << " p[" << it->first.pinid << "]"
             << " tm[" << it->first.tm << "]"
             << " mss[" << it->first.mss << "]"
             << " : " << it->second.cs
             << endl;
    }
}

std::map::find is not finding a match, but if i loop thru begin() to end() i see the match right there

2 Answers2