How to insert an object to a map structure by a certain field?

Question

Hello, i have an object - Employee, and i want to know how to insert this object to a map structure sorted by char* lastName field. Thanx. My map need to contain pointers to Employee objects not the objects themselves. the key is the last name of the employee, the map need to be sorted by the employees last name, should i use multimap?

Answer 1

So you've got an std::map with a custom comparator function (you've overloaded the less than operator) and you want to insert objects so that they're in the right order?

myMap.insert( make_pair( myKey, myEmployee ) );

where myKey is the key to your map. However, from the sound of your question it actually sounds like you're using the object as it's own key. In that case, just use std::set and

mySet.insert( myEmployee );

I'd also suggest that you not use char* as a means to store lastName and prefer the std::string.

EDIT:

Following the comments down below, are you having to be able to pass in a const char* into another function? If so, still use string as it has a nice method .c_str() specifically for legacy compatibility. It can be used as so:

void stuffHappens(const char* _input){
    //magic happens in here
}

stuffHappens( myString.c_str() );

and voila, you're much safer!

Answer 2

Define bool operator <(const Employee& other) for the Employee class. Alternatively, define bool operator <(const Employee& left, const Employee& right) as a non-member function, and make it a friend of Employee. The advantage of the first approach is that it's local to Employee, and that enhances encapsulation. The advantage of the latter approach is that it will work with any two types that are convertible to Employee. Alternatively, you can create a comparator functor, instead of operator <(), and pass that the map's constructor.

Lastly, use the insert() member function of std::map<> to insert the new employees. std::map<> also has operator []() defined, and it allows you to insert into the map. The insert() function will not insert the element if the element is already in the map, whereas operator []() will update the element if it already exists.

Answer 3

You could create a "functor" which overrides operator(), taking references to two of your objects and returning a boolean of obj1 < obj2.

For example:

class EmployeeComparator
{
    public:
    bool operator()(const Employee& emp1, const Employee& emp2)
    {
        return strcmp(emp1.lastName, emp2.lastName) < 0;
    }
}

When you create your std::map, you then pass EmployeeComparator as the comparison object, like so:

std::map<Employee, T, EmployeeComparator> m;

Other posters' ideas of overriding the < operator will work too, but with that method you have pick a single criteria to sort by. With my way, you could have one map that sorts by last name, another that sorts by employee ID, etc. With each map you'd pass a different functor as your sorter.

Keep in mind that with my way, if you are trying to sort by a private field, declare your sorting functor as a friend class of the class to be sorted.

Answer 4

To add to what wheaties said, if the Employee object contains its own key, you should probably use a set. In order to use the set, you are going to have to explicitly define a method of comparison for the Employee object. There are two ways of doing that, either define operator< for the object:

class Employee
{
public:
  bool operator<(const Employee &rhs)
  {
    return strcmp(lastName, rhs.lastName) < 0;
  }
...
};

Or you can define a functor that you tell the set to use for comparison:

struct EmployeeLessThan
{
  bool operator()(const Employee &lhs, const Employee &rhs)
  {
    return strcmp(lhs.lastName, rhs.lastName) < 0;
  }
};

std::set<Employee, EmployeeLessThan> myEmployees;

Edit: One VERY important thing to keep in mind is that a set stores all of it's items as const. It does this because it's possible that a change to an element in the set could change the order of the elements and set isn't capable of detecting this and reordering. This can be problematic if you want to update any of the employees contained in the set. The best way around this problem is to declare any of the data members of Employee that you might want to change as mutable. This will let you change their values even when it's const.

Edit2: If you decide to continue using a map and the key is a char *, then keep in mind that by default the map is going to compare two char *s by the value of their pointer, not the string they point to. The best thing to do in this case is to use std::string instead of char *. Alternatively, you can define a functor to pass to the map:

struct CharStarLessThan
{
  bool operator()(const char *lhs, const char *rhs)
  {
    return strcmp(lhs, rhs) < 0;
  }
};

std::map<char *, Employee, CharStarLessThan> myEmployees;

Answer 5

As Philip Potter has written in comments, you should definetely use std::string. Because two different char* declared at several places/files in your cpp code WON'T have the same addresses ! As a char* is nothing but an integer, you will have several char* keys for one and only one same lastname, and this is not what you want.

go this way:

std::map<std::string,YourType> yourMap;
std::string strMyLastName = "Rolland";
YourType aValue;
yourMap[strMyLastName ] = aValue;