How to check if a container passed to a function is sorted and sort it if not

Question

I have this function we wrote some time ago:

template <class C, class T>
static inline bool findClosestObject( const C& container, const TimeUnit& now, T& object );

C is a container of T elements
TimeUnit is a class encapsulating date and time
T is an object with a TimeUnit information

This function does a binary search (using std::lower_bound) in the container to find the closest object to now.

As we do a binary search, the container must be sorted. This function is used with many kind of containers (C can be std::vector, std::set, std::map...) in many places. Sometimes we use sorted std::vector rather than std::set because their memory management is faster and also for historical issue and compatibility with other piece of your code which is using vectors.

Problem is that I found a place in the code where a developer called findClosestObject with a container that was not sorted....nice bug...and I cannot safely identify all places where this could have been done.

So I now need to prevent that by sorting the container in this specific case where it's not (will be slow but will at least work and guarantee function returns what we want it to return)

So I tried to modify my function:

template <class C, class T>
static inline const C& fixOrder( const C& container, C& temp )
{
    if ( std::is_sorted( container.begin(), container.end() )
    {
        return container;
    }
    else
    {
        assert( false ); // to alert developper
        // in Release, fix the issue to have function work!
        temp = container;
        std::sort( temp.begin(), temp.end() );
        return temp;
    }
}

template <class C, class T>
static inline bool findClosestObject( const C& originalContainer, const TimeUnit& now, T& object )
{
    C temp;
    const C& container = fixOrder( originalContainer, temp );
    ...
    // leave old code unchanged
}

But this fails to compile when C is a std::set or a std::map. Because std::sort is not allowed for those kind of containers...

Can fixOrder be written in such a way that it would only do things for std::vector and not for other containers?

Why not add a overload for `std::vector`? – NathanOliver Dec 16 '16 at 15:47 — NathanOliver, Dec 16 '16 at 15:47

score 6 · Accepted Answer · edited May 23 '17 at 12:08

6

You could just add a partial specialization for std::set<T> and std::map<T1,T2> for your template function:

// This one is called for every C not having a better specialization
template <class C>
static inline const C& fixOrder( const C& container, C& temp )
{
    if ( std::is_sorted( container.begin(), container.end() ))
    {
        return container;
    }
    else
    {
        assert( false ); // to alert developper
        // in Release, fix the issue to have function work!
        temp = container;
        std::sort( temp.begin(), temp.end() );
        return temp;
    }
}

// This one is called for std::set<T>
template<class T>
static inline const set<T>& fixOrder( const set<T>& container, set<T>& temp )
{
    return container;
}

// This one is called for std::map<T1, T2>
template<class T, class T2>
static inline const map<T, T2>& fixOrder( const map<T, T2>& container, map<T, T2>& temp )
{
    return container;
}

This answer has details about the template functions overload resolution.

edited May 23 '17 at 12:08

Community

1
1

answered Dec 16 '16 at 15:53

alexeykuzmin0

6,344
2
28
51

By the way, as the goal is to guarantee container is always sorted, it's probably safer to have unspecialized version do the sorting, and have specialized versions for `set`/`map` that will do nothing (then we can add some specialized versions when needed, but we keep default behaviour to silently sort "all"). It may make sense to update your post to reflect that. – jpo38 Dec 16 '16 at 17:18
@jpo38 Agree, will fix – alexeykuzmin0 Dec 17 '16 at 05:59
Nice. Thanx again for your help. – jpo38 Dec 17 '16 at 11:47

score 5 · Answer 2 · edited May 23 '17 at 12:13

alexeykuzmin's answer is simpler and should solve your issue. My answer below is slightly more complicated but it could be an interesting read for educational purposes.

Can fixOrder be written in such a way that it would only do things for std::vector and not for other containers?

Yes! You can use std::enable_if and an helper is_specialization_of trait:

template <typename, template <typename...> class>
struct is_specialization_of : std::false_type
{
};

template <template <typename...> class TTemplate, typename... Ts>
struct is_specialization_of<TTemplate<Ts...>, TTemplate> : std::true_type
{
};

template <class C>
static inline auto fixOrder(const C& x, C&)
    -> typename std::enable_if<is_specialization_of<C, std::vector>{}, const C&>::type
{
    std::cout << "C is a vector\n";
    return x;
}

template <class C>
static inline auto fixOrder(const C& x, C&)
    -> typename std::enable_if<!is_specialization_of<C, std::vector>{}, const C&>::type
{
    std::cout << "C is not a vector\n";
    return x;
}

With the above code...

int main() 
{
    std::vector<int> v;
    std::set<int> s;

    fixOrder(v, v);
    fixOrder(s, s);
}

...will print:

C is a vector

C is not a vector

wandbox example

How to check if a container passed to a function is sorted and sort it if not

2 Answers2