如何检查传递给函数的容器是否已排序,如果没有则对其进行排序

Question

我有一段时间以前写的这个功能:

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

• C 是T元素的容器
• TimeUnit 是一个封装日期和时间的类
• T是一个有TimeUnit信息的对象

此函数std::lower_bound在容器中执行二进制搜索(使用)以查找最接近的对象now.

当我们进行二分查找时,必须对容器进行排序.该函数用于许多种容器(C可以是std::vector,std::set,std::map...)在很多地方.有时我们使用sorted std::vector而不是std::set因为它们的内存管理更快,也因为历史问题和与使用向量的其他代码的兼容性.

问题是我在代码中找到了一个地方,开发人员findClosestObject用一个没有排序的容器调用....好的bug ...而且我无法安全地识别出可以完成的所有地方.

所以我现在需要通过在这个特定的情况下对容器进行排序来防止它(它将会很慢但是至少会工作并且保证函数返回我们希望它返回的内容)

所以我试着修改我的功能:

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
}

但是当Ca std::set或a 时,这无法编译std::map.因为std::sort这种容器不允许......

可以fixOrder用这样的方式编写,它只会std::vector为其他容器而不是为其他容器做事吗？

Answer 1

你可以只添加一个部分专门用于std::set<T>与std::map<T1,T2>您的模板功能:

// 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;
}

这个答案有关于模板函数重载决议的详细信息.

Answer 2

alexeykuzmin的答案更简单,应该解决您的问题.我在下面的回答稍微复杂一点,但它可能是一个有趣的阅读教育目的.

可以用这样的方式编写fixOrder,它只能为std :: vector而不是其他容器做事吗？

是! 您可以使用std::enable_if和辅助is_specialization_of特征:

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;
}

用上面的代码......

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

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

...将打印:

C是矢量

C不是矢量

wandbox示例