is_transparent: How to search a C++ set with another type than its key

C++14 brought a interesting feature on associative containers that was cruelly missing for certain use cases: the ability to search an associative container with something that is semantically a key, even if it is not technically a key.

This fills a very similar need as the one in Functors are not dead: the double functor trick, but there we used algorithms whereas now we focus on containers.

Thanks to Reddit user u/iannus, who brought this feature to my attention in the thread about functors.

Motivation

This feature is particularly useful for sets. Some sets store object that embed their own keys, that is to say that such objects have a subpart that is to be considered as a key, like an ID for example, while the object itself is to be considered as a value.

These objects are typically of this form:

class Employee
{
public:
    explicit Employee(int id, std::string const& name) : id_(id), name_(name){}
    int getId() const { return id_; }
    std::string getName() const { return name_; }

private:
    int id_;
    std::string name_;
};

Employee is a type representing an employee, and we want to store several employees in an std::set. And since it doesn’t make sense to compare two employees and say which one is bigger, every employee has an ID, that provides a technical order by which the employees are sorted in the set.

To implement this, the C++ set provides the possibility to customize the comparison function:

struct CompareId
{
    bool operator()(Employee const& employee1, Employee const& employee2) const
    {
        return employee1.getId() < employee2.getId();
    }
};

std::set<Employee, CompareId> employees;

This way, employees are sorted by ID inside the set. This feature has been there since C++98.

But soon after starting to use it, a basic need generally comes up: searching for employees by their ID in the set. Doing this implies being able to compare an ID with an employee. And the natural way to go for a reasonable programmer is to think: “No problem! I’ll just throw some more comparison functions and we’ll be done with it!”:

struct CompareId
{
    bool operator()(Employee const& employee1, Employee const& employee2) const
    {
        return employee1.getId() < employee2.getId();
    }
    bool operator()(int id, Employee const& employee) const
    {
        return id < employee.getId();
    }
    bool operator()(Employee const& employee, int id) const
    {
        return employee.getId() < id;
    }
};

(Note that this can be achieved many different ways including inheriting from lambdas – see the last section of Functors are not dead for more discussion about this. But let’s not worry about that right now, in order to focus on the functional need).

And then at the calling of the search on an ID…

std::set<Employee, CompareId> employees = { Employee(1, "John"), Employee(2, "Bill") };
std::cout << employees.find(1)->getName() << '\n';

the code does not compile.

“What?”, the programmer is scratching his head, “why?”

The answer lies in the prototype of the find method:

iterator find( const Key& key );

Indeed, the find method only accepts keys of the same type as the elements of the set. So you’d have to pass an employee, even if the comparison is based only on the ID subpart of the element.

Our programmer re-reads the C++ documentation several times, convinced that there must be a way. And there isn’t. Dark options are lurking around though, trying the temptation of this otherwise well-meaning developer:

• damaging the Employee class by adding a constructor taking only a reference, to construct some sort of “empty” employee, just for the sake of performing comparisons,

• damaging the whole design, by using an std::map<int, Employee>, therefore duplicating the ID in code and in memory,

• avoiding duplicating the ID by violently gutting out the Employee class to take out the ID and putting it as the key in an std::map<int, Employee>.

And at the very moment where our candid companion was rising his fingers to type a desperate stab at the whole program, C++14 rides in and saves the situation. (Or, if C++14 wasn’t implemented in the project in time then it finds the desolated remains of a code crime scene dating from years ago. Oops.)

is_transparent

Essentially, C++14 fills the gap, by providing new overloads of the find method (along with new overloads of count, lower_bound, upper_bound and equal_range). These overloads are template, so they could theoretically accept anything that can be compared with an Employee, including an ID.

To activate these overloads, the comparison function object has to define a typedef called is_transparent. The value of this typedef is not used so it doesn’t matter what it is equal to, as long as it is defined:

struct CompareId
{
    using is_transparent = void; // for example with void,
                                 // but could be int or struct CanSearchOnId;
    bool operator()(Employee const& employee1, Employee const& employee2) const
    {
        return employee1.getId() < employee2.getId();
    }
    bool operator()(int id, Employee const& employee) const
    {
        return id < employee.getId();
    }
    bool operator()(Employee const& employee, int id) const
    {
        return employee.getId() < id;
    }
};

And then the find method does just what you would expect it to do. The following code:

std::set<Employee, CompareId> employees = { Employee(1, "John"), Employee(2, "Bill") };
std::cout << employees.find(1)->getName() << '\n';

outputs “John”.

This feature got in the standard in more discrete way than rockstars like generic lambdas, but is quite valuable nonetheless.

Related articles:

• Functors are not dead: the double functor trick
• Searching when you have access to an STL container

Don't want to miss out ? Follow:   
Share this post!