Insert into any sorted container

Question

The following is my attempt to implement a insert_sorted() C++ function that accepts any sorted STL container and item and inserts it at the right position in the container:

template<template<typename, typename, typename> typename C, typename T1, typename Comp, typename A, typename T2>
inline typename C<std::enable_if_t<std::is_convertible_v<T1, std::remove_reference_t<T2>>, T1>, Comp, A>::iterator
insert_sorted (C<T1, Comp, A> & c, T2 && item)
{
    return c.insert (c.end(), std::forward<T2> (item));
}

template<template<typename, typename> typename C, typename T1, typename A, typename T2, typename Comp = std::less<T1>>
inline typename C<std::enable_if_t<std::is_convertible_v<T1, std::remove_reference_t<T2>>, T1>, A>::iterator
insert_sorted (C<T1, A> & c, T2 && item, Comp comp = Comp{})
{
    return c.insert (std::upper_bound (std::begin (c), std::end (c), static_cast<T1>(item), comp), std::forward<T2> (item));
}

These two compile and work fine; the first overload works for set-like containers, while the second for vector-like containers.

I was wondering if you see any drawbacks to this solution and if there is a more generic way to approach the problem, that is, is it possible to write a single insert_sorted() function that does the same as the above two?

EDIT: Thanks to the comments, I was able to replace the two template functions above with the following:

template<typename C, typename T, typename Comp = std::less<T>, 
         typename = std::enable_if<std::is_convertible_v<std::remove_reference_t<T>, typename C::value_type>>>
    inline auto insert_sorted (C & c, T && item, Comp comp = Comp{})
{
    return c.insert (std::upper_bound (std::begin (c), std::end (c), item, comp), std::forward<T> (item));
}

Thank you all for your help!

Toby Speight · Accepted Answer · 2021-09-06 09:37:35Z

inline is redundant when writing template functions.

When we use std::begin() and std::end(), we should always consider whether we actually want to use begin() and end() of the type's namespace instead (argument-dependent lookup, aka ADL), with fallback to std:

using std::begin;
using std::end;
return c.insert(std::upper_bound(begin(c), end(c), item, comp),
                std::forward<T>(item));

When we're inserting to a sorted container such as std::set, we probably want to use the container's key_compare as default, rather than std::less<T>. That will require splitting back into two functions again. I prefer to split out a helper that returns an appropriate default comparator:

#include <functional>

template<typename C>
auto comparator_for(const C& c)
    requires requires { c.key_comp(); }
{
    return c.key_comp();
}

template<typename C>
auto comparator_for(const C&)
{
    return std::less<typename C::value_type>{};
}

We can then use it in an overload that defaults the parameter:

#include <algorithm>
#include <concepts>
#include <iterator>
#include <utility>

template<typename C, typename T, typename Comp>
auto insert_sorted(C& c, T&& item, Comp comp)
    requires std::convertible_to<T, typename C::value_type>
{
    using std::begin;
    using std::end;
    return c.insert(std::upper_bound(begin(c), end(c), item, comp),
                    std::forward<T>(item));
}

template<typename C, typename T>
auto insert_sorted(C& c, T&& item)
{
    return insert_sorted(c, std::forward<T>(item), comparator_for(c));
}

(I've used modern Concepts syntax rather than std::enable_if, as I find that easier to read).

G. Sliepen · Accepted Answer · 2021-09-06 10:00:19Z

Just to present an alternative way of doing things: instead of using insert() and std::upper_bound(), you could use push_back() and std::inplace_merge(). If you are going to provide a ranges-like interface anyway, perhaps you could use std::ranges and copy the interface of std::ranges::inplace_merge() as much as possible:

template<std::ranges::bidirectional_range R, class T, class Comp = std::ranges::less, class Proj = std::identity>
requires std::sortable<std::ranges::iterator_t<R>, Comp, Proj>
std::ranges::borrowed_iterator_t<R>
insert_sorted(R&& r, T&& item, Comp comp = {}, Proj proj = {}) {
    using std::end;
    using std::prev;
    r.push_back(item);
    return std::ranges::inplace_merge(r, prev(end(r)), comp, proj);
}

Note that this doesn't work for std::set, but it does for std::list.

Stack Exchange Network

Insert into any sorted container

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Insert into any sorted container

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions