How to implement a lambda function for a sort algo

2020-02-12 21:38发布

I'm working on some code and I have a section where I do a one off sort function. To implement it I decided it was easiest to overload the operator< function. What I would prefer to do is move the implementation of the sort closer to the actual call by using some sort of boost::bind, boost::phoenix, lambda or some other type of implementation. Unfortunately I don't have access to new C++11 functionality. Below is some example code.

// In a header
struct foo
{
   char * a;
   char * c_str() { return a; }
}

// In a header
struct bar
{
    foo * X;          

    bar(foo * _X) : X(_X) {}
    bool operator < (const bar& rhs) const
    {
        return std::string(X->c_str()) < std::string(rhs.X->c_str());
    }
};

struct bars : public std::vector<bar> { ... some stuff  };

// Some other header
bars Bs;


// A cpp file
... other stuff happens that fills the Xs vector with objects

...::Function()
{
    // Current use and it works fine
    std::sort(Bs.begin(), Bs.end())

    // Would like something that accomplishes this:
    // std::sort(Bs.begin(), Bs.end(), 
    //   std::string(lhs.X->c_str()) < std::string(rhs.X->c_str()))

    // A non-working example of what I'm trying to do
    // std::sort(Xs.begin(), Xs.end(), 
    //     std::string((bind(bar::X->c_str(), _1)) <
    //     std::string((bind(bar::X->c_str(), _2)) )
}

I get lost when trying to figure out how to access the member pointers, member function and then cast the result all within a boost::bind function.

Thank you for your help.

1条回答
手持菜刀,她持情操
2楼-- · 2020-02-12 21:52

I'm sure you can twist your way out of this using ample helpings of

  • Boost Phoenix bind and lambda
  • Boost Bind protect

However, I've learned to avoid these situations. Edit In fact, see below for one such contraption. I find this very very error prone and hard to reason about.

What you're seeing is, in essence, a violation of the Law Of Demeter. If you "just" wrote the code (not in a lambda), already it would be handling too many tasks.

So the first thing I'd do is rethink the class design.

The second thing I'd do is /extract/ different responsibilities from your comparator. Notice, that the comparator does three things:

  • access the c_str() of the X in lhs
  • access the c_str() of the X in rhs
  • compare the two

The first two steps are clear candidates for extraction. Let's write the generic comparer that remains first:

template <typename F>
struct compare_by_impl {
    compare_by_impl(F f = F{}) : _f(std::move(f)) {}

    template <typename T, typename U>
    bool operator()(T const& a, U const& b) const {
        return _f(a) < _f(b);
    }
  private:
    F _f;
};

As always, it's nice to have factory function that will deduce the accessor type (in case you can get away with just using Phoenix there, it will save you specifying the (arcane) typenames involved in the expression templates):

template <typename Accessor>
compare_by_impl<Accessor> comparer_by(Accessor&& f) {
    return compare_by_impl<Accessor>(std::forward<Accessor>(f));
}

Now you could already move the implementation with your sort call:

void Function()
{
    struct accessX_c_str {
        std::string operator()(bar const& b) const { 
            return b.X->c_str();
        }
    };

    std::sort(Bs.begin(), Bs.end(), comparer_by(accessX_c_str()));
}

I'd personally leave it there.

Here's some more twisted contraptions:

// to avoid `comparer_by`
std::sort(Bs.begin(), Bs.end(), phx::bind(accessX_c_str(), arg1) < phx::bind(accessX_c_str(), arg2));


// to avoid any helper types (!?!?!? untested!)
std::sort(Bs.begin(), Bs.end(), 
        phx::construct<std::string>(phx::bind(&foo::c_str, phx::lambda [ phx::bind(&bar::X, arg1) ](arg1))) 
      < phx::construct<std::string>(phx::bind(&foo::c_str, phx::lambda [ phx::bind(&bar::X, arg1) ](arg2)))
    );
查看更多
登录 后发表回答