Making a comparator from an ordered container

Question

Given a list of objects, what is the cleanest way to create a functor object to act as a comparator, such that the comparator respects the ordering of the objects in the list. It is guaranteed that the objects in the list are unique, and the list contains the entire space of possible objects.

For example, suppose we have:

const std::vector<std::string> ordering {"dog", "cat", "mouse", "elephant"};

Now we want a function to act as a comparator, say for a map:

using Comparator = std::function<bool(const std::string&, const std::string&>;
using MyMap      = std::map<std::string, int, Comparator>;

I have a solution, but it's not what I'd call pretty:

const auto cmp = [&ordering] (const auto& lhs, const auto& rhs)
                 {
                     const std::array<std::reference_wrapper<const std::decay_t<decltype(lhs)>, 2> values {lhs, rhs};
                     return *std::find_first_of(std::cbegin(ordering), std::cend(ordering),
                                                std::cbegin(values), std::cend(values),
                                                [] (const auto& lhs, const auto& rhs) {
                                                    return lhs == rhs.get();
                                                }) == lhs;
                 };

Is there something a little less verbose?

Answer 1

You can use:

const std::vector<std::string> ordering {"dog", "cat", "mouse", "elephant"};

struct cmp
{
   bool operator()(const std::string& lhs, const std::string& rhs)
   {
      return (std::find(ordering.begin(), ordering.end(), lhs) <
              std::find(ordering.begin(), ordering.end(), rhs));
   }
};

using MyMap = std::map<std::string, int, cmp>;

See it working at http://ideone.com/JzTNwt.

Answer 2

KISS. Build up your solution from reusable primitives with clear semantics.

order_by takes a projection A->B and returns an ordering on A using the ordering on B. It optionally takes an ordering on B (not used here):

template<class F, class Next=std::less<>>
auto order_by(F&& f, Next&& next = {}) {
  return [f=std::forward<F>(f), next=std::forward<Next>(next)]
    (auto&& lhs, auto&& rhs)->bool
  {
    return next(f(lhs), f(rhs));
  };
}

index_in takes a container c and returns a function that takes an element, and determines its index in c:

template<class C>
auto index_in( C&& c ) {
  return [c=std::forward<C>(c)](auto&& x){
    using std::begin; using std::end;
    return std::find( begin(c), end(c), x ) - begin(c);
  };
}
template<class T>
auto index_in( std::initializer_list<T> il ) {
  return [il](auto&& x){
    using std::begin; using std::end;
    return std::find( begin(il), end(il), x ) - begin(il);
  };
}

We then compose them:

auto cmp = order_by( index_in(std::move(ordering) ) );

Each component can be independently tested and validated, and the composition "obviously" works. We can also rewrite index_in to use a faster lookup than linear, say a map from key to index, and we'd have two implementations that can unit test against each other.

I find order_by very often useful. index_in I've never had to use before.

This trick makes constructing the resulting map on one line, instead of storing cmp, practical, as the final description is short and clear.

template<class T>
using Comparator = std::function<bool(T const&, T const&>;
using MyMap      = std::map<std::string, int, Comparator<std::string>>;
MyMap m = order_by( index_in({"dog", "cat", "mouse", "elephant"}) );

is also really pretty looking.

---

Here is a second approach.

We can move some of the work outside of the lambda.

template<class T0, class...Ts>
std::array< std::reference_wrapper<T0>, sizeof...(Ts)+1 >
make_ref_array( T0& t0, Ts&... ts ) {
  return {std::ref(t0), std::ref(ts)...};
}

Then we can write the lambda from first principles instead of algorithms:

Comparator cmp = [&ordering] (const auto& lhs, const auto& rhs)
{
  if (lhs==rhs) return false; // x is never less than x.
  for (auto&& e:ordering)
    for (auto&& z:make_ref_array(lhs, rhs))
      if (e==z.get())
        return std::addressof(z.get())==std::addressof(lhs);
  return false;
};

The resulting lambda is a bit less verbose.

If you had ranged based algorithms it might also help.

---

In both my solutions, all elements not in the list are greater than any element in the list, and are equal to each other.

Answer 3

Just skip the algorithms and write a for-loop:

auto cmp = [&ordering](auto const& lhs, auto const& rhs) {
    for (auto const& elem : ordering) {
        // check rhs first in case the two are equal
        if (elem == rhs) {
            return false;
        }
        else if (elem == lhs) {
            return true;
        }
    }
    return false;
};

It might technically be longer than your solution, but I find it way easier to read.

---

Alternatively, depending on the size of the ordering, could throw both into a map:

std::unordered_map<std::string, int> as_map(std::vector<std::string> const& ordering)
{
    std::unordered_map<std::string, int> m;
    for (auto const& elem : ordering) {
        m.emplace(elem, m.size());
    }
    return m;
}

auto cmp = [ordering_map = as_map(ordering)](auto const& lhs, auto const& rhs){
    auto left = ordering_map.find(lhs);
    auto right = ordering_map.find(rhs);
    return left != ordering_map.end() && right != ordering_map.end() &&
        left->second < right->second;
};

Answer 4

This is basically the same as R. Sahu's answer. But since I'd already typed it up... The primary thing I'm advocating here is keeping ordering internal to cmp, presuming that you don't need it externally.

const auto cmp = [ordering = vector<string>{ "dog", "cat", "mouse", "elephant" }](const auto& lhs, const auto& rhs) { return find(cbegin(ordering), cend(ordering), lhs) < find(cbegin(ordering), cend(ordering), rhs); };

Live Example

Encapsulating the ordering within cmp makes the scope that a reader has to look at when he changes ordering much smaller. (Personally I wouldn't construct cmp as an Rvalue, I'd just dump it directly into the constructor for the same reason... Though it is becoming a bit of a redonculous one-liner:

map<string, int, function<bool(const string&, const string&)>> myMap([ordering = vector<string>{ "dog", "cat", "mouse", "elephant" }](const auto& lhs, const auto& rhs) { return find(cbegin(ordering), cend(ordering), lhs) < find(cbegin(ordering), cend(ordering), rhs); });

Live Example

Answer 5

I suggest you make the key a structure type containing the key (std::string in this case) and the index in the array.
Something like

struct Key
{
    std::string str;
    size_t index;
};

using MyMap      = std::map<Key, int, Comparator>;

struct Comparator
{
    bool operator()(const Key &a, const Key &b) const
    {
        return a.index < b.index;
    }
};