Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Always prefer set<T, less<>> to set<T> since C++14?

#include <set>
#include <string>
#include <string_view>

using namespace std;

int main()
{
    string_view key = "hello";

    set<string> coll1;
    coll1.find(key); // error

    set<string, less<>> coll2;
    coll2.find(key); // ok since C++14
}

Then, should it be a rule:

Always prefer set<T, less<>> to set<T> since C++14?

like image 463
xmllmx Avatar asked Dec 12 '16 04:12

xmllmx


2 Answers

It's trivial to find a counterexample:

#include <set>
#include <string>

using namespace std;

struct converts_to_string {
    operator string() const { return ""; }
};

int main()
{
    converts_to_string key;

    set<string> coll1;
    coll1.find(key); // OK

    set<string, less<>> coll2;
    coll2.find(key); // error
}
like image 58
T.C. Avatar answered Nov 11 '22 07:11

T.C.


There can be a performance downside when using associative_container<T, less<>>: Consider a type like

#include <iostream>
#include <set>
#include <string>

struct stupid_string
{
    stupid_string(char const* s)
      : s(s)
    { std::cout << "copy\n"; }

    stupid_string(char const* s, int) // silent
      : s(s)
    {}

    friend bool operator<(stupid_string const& lhs, stupid_string const& rhs);

private:
    std::string s;
};

bool operator<(stupid_string const& lhs, stupid_string const& rhs) {
    return lhs.s < rhs.s;
}

int main() {
    std::set<stupid_string, std::less<>> s;
    s.emplace("hello", 0);
    s.emplace("world", 0);
    s.emplace("foobar", 0);
    std::cout << "find\n";
    (void)s.find("test");
}

Here, the application of operator< in the algorithm performed by s.find will convert the character literal to a stupid_string implicitly. This happens for each comparison performed! Live demo

I know of one case where something similar happened in production code, with a non-conforming C++03 StdLib implementation.


This is by the way the main reason why heterogeneous lookup via less<> was made opt-in; see N3657:

Stephan T. Lavavej suggested that the two problems of preserving existing behaviour and allowing heterogeneous lookups could both be solved by making the containers detect when the comparison object accepts heterogeneous arguments and only conditionally overloading the current lookup functions with template versions.

like image 41
dyp Avatar answered Nov 11 '22 05:11

dyp