Apologises for the ambiguous title.

Here is my code:

struct LowHigh
{
};
struct HighLow
{
};

template < class LookupScheme>
struct ladder_base
{
    using value_type     = price_depth;
    using ladder_type    = std::vector< value_type >;

    template < class T >
    struct lookup;

    template <>
    struct lookup< LowHigh >
    {
        static constexpr auto func = std::upper_bound< ladder_type::iterator, value_type >;
    };
    template <>
    struct lookup< HighLow >
    {
        static constexpr auto func = std::lower_bound< ladder_type::iterator, value_type >;
    };

    void
    insert(value_type v)
    {
        auto iter = lookup< LookupScheme >::func(std::begin(data_), std::end(data_), v);
        data_.insert(iter, std::move(v));
    }

  protected:
    std::vector< value_type > data_;
};
}   // namespace detail

struct bid_ladder : detail::ladder_base< detail::HighLow >
{
};

struct offer_ladder : detail::ladder_base< detail::LowHigh >
{
};

I'm specialising lookup::func depending on the scheme passed as a template type. There are currently only two possible schemes: LowHigh & HighLow. This has the effect of determining how the underlying vector is sorted.

Is there a more idiomatic/cleaner way to express this logic?

CodePudding user response：

These algorithms take a comparison object as their last parameter - so you can use that to your advantage.

template < class Compare >
struct ladder_base
{
    using value_type     = price_depth;
    using ladder_type    = std::vector< value_type >;

    void
    insert(value_type v)
    {
        auto iter = std::upper_bound(data_.begin(), data_.end(), v, Compare{} );
        data_.insert(iter, std::move(v));
    }

  protected:
    std::vector< value_type > data_;
};

And then use ladder_base<std::less<>> or ladder_base<std::greater<>>, depending on which sort order you want.

Note that std::lower_bound and std::upper_bound are not antonyms, so your original wasn't really correct. lower_bound gives you the first element >= x and upper_bound gives you the first element > x. So changing from one to the other doesn't change your sort order (both require increasing order), only the comparison object affects that.

For instance:

std::vector<int> v = {1, 3, 5, 7};
auto i = std::lower_bound(v.begin(), v.end(), 3); // this is the 3
auto j = std::upper_bound(v.begin(), v.end(), 3); // this is the 5

Note that the vector is sorted in increasing order, but both calls are perfectly well-formed. If you wanted a reverse sort, you'd have to pass std::greater{} in as the comparison object (as I'm showing).

But either way, you want to use std::upper_bound - regardless of sort order.

CodePudding user response：

The idiomatic way of doing that type of stuff is to have the template parameter contain the code to invoke directly, instead of indirecting through a tag type like you are doing.

Mind you, at that point, you could always just pass std::upper_bound directly as a template parameter.

Furthermore, since this is tagged c 20, you would also ideally use a concept, to constrain the types that can be passed to ladder_base.

#include <concepts>
#include <vector>

using price_depth = int;

template<typename T>
concept LookupScheme = requires (const T& x, const std::vector<price_depth>& v) {
    {x(v.begin(), v.end(), price_depth{})} -> std::same_as<decltype(v.begin())>;
};

namespace detail {
struct LowHigh {
    template<typename ForwardIt, typename T>
    decltype(auto) operator()(ForwardIt first, ForwardIt last, const T& value ) const {
        return std::upper_bound(first, last, value);
    }
};

struct HighLow {
    template<typename ForwardIt, typename T>
    decltype(auto) operator()(ForwardIt first, ForwardIt last, const T& value ) const {
        return std::lower_bound(first, last, value);
    }
};

template <LookupScheme Scheme>
struct ladder_base
{
    using value_type     = price_depth;
    using ladder_type    = std::vector< value_type >;

    void insert(value_type v)
    {
        auto iter = Scheme::exec(std::begin(data_), std::end(data_), v);
        data_.insert(iter, std::move(v));
    }

  protected:
    std::vector< value_type > data_;
};

}   // namespace detail

struct bid_ladder : detail::ladder_base< detail::LowHigh >
{
};

struct offer_ladder : detail::ladder_base< detail::HighLow >
{
};

You can see the same approach used in the standard library's sorted containers, such a std::map<>'s Compare parameter.

CodePudding user response：

template<class C>
auto lookup(C& c, value_type v) {
  if constexpr(std::same_as<LookupScheme, LowHigh>)
    return std::upper_bound(c.begin(), c.end(), v);
  else if constexpr(std::same_as<LookupScheme, HighLow>)
    return std::lower_bound(c.begin(), c.end(), v);
}

void insert(value_type v) {
  auto iter = lookup(data_, v);
  data_.insert(iter, std::move(v));
}