Home > Software design >  search in nested map C
search in nested map C

Time:06-11

I have a nested map:

std::map<std::string,std::map<std::string,float>> registration_by_date_time;

where the key is a string for the date and the value is another map with key a string for time end value a float.

I have to implement this method:

float get_registration(const string & date, const string & time) const;

which returns the time series value at date and time or "NaN" in case the value was not previously added in the time series.

My implementation is the following:

float get_registration(const string & date, const string & time) const{
    if(registration_by_date_time.find(date) != registration_by_date_time.cend())
        if(registration_by_date_time.at(date).find(time) != registration_by_date_time.at(date).cend())
            return registration_by_date_time[date][time];
        else
            return "NaN";
    else
        return "NaN";
}

Is it correct? in particular I wold like to know if I am using correctly .at and if I also could use the access operator [] or "second".

CodePudding user response:

Note that the index operator for map is not a constant operation (for std::map access is O(log(n))). So here you pay this cost twice - once for the find and second time to return the value (if available). A better approach is to store the result of find:

std::map<std::string,std::map<std::string,float>>::iterator by_date_it = registration_by_date_time.find(date);
// or auto by_date_it = registration_by_date_time.find(date);
if (by_date != registration_by_date_time.end()) {
  std::map<std::string,float>::iterator by_time = by_date_it->second.find(time);
  if (by_time != by_date_it->end()) {
    return by_time->second;
  }
}
return "NaN;

As pointed out, not only is this code shorter but it should be faster, avoiding double access with cost O(log(n)) for both the outer and the inner map. In general as I suggest you can use auto here to make the code shorter, I have written out the type explicitly in hope to make the logic clearer.

NOTE: std::map is not implemented with a hashmap, it is implemented with red-black trees (a type of binary search tree), so it is possible this is what led you to think the complexity of access is with expected constant complexity.

  • Related