Acclerated C++:我可以编写一个程序,使用相同的命令对列表或向量进行排序吗？

Question

我意识到std :: sort函数需要使用随机访问迭代器,而列表具有双向迭代器.关于这个问题有一个问题:

使用STL排序功能对列表进行排序

我正在努力回答加速C++书中用于家庭学习的问题5-4.

5-4.再看一下你在上一个练习中写的驱动函数.请注意,可以编写仅在保存输入文件的数据结构的类型声明中不同的驱动程序.如果向量和列表测试驱动程序以其他任何方式不同,请重写它们,使它们仅在此声明中有所不同.

除了这个教科书问题,如果我使用模板而不是typedef来定义容器类型,这将是有用的.

Answer 1

...使用相同的命令对列表或向量进行排序？

最简单的方法是使用重载:

template <typename T>
inline void sort(std::vector<T>& x) { std::sort(x.begin(), x.end()); }

template <typename T>
inline void sort(std::list<T>& x) { x.sort(); }

UPDATE

你暗示你的文本还没有引入模板,所以这里是一个无模板的替代品.这个问题说:"只有在不同的保存输入文件中的数据结构类型的声明"和我们谈论vector和list,所以必须有这样的:

std::vector<std::string> input;

也许类型不是std::string- 你可能有自己的数据类型 - 但不管它是什么,标准容器 - 包括vector和list- 有一个typedef所包含的类型可以被引用到ala input::element_type.这意味着您可以编写更多限制版本的模板,这些版本仅适用于具有该特定元素类型的vectors和lists:

inline void sort(std::vector<input::element_type>& x) { std::sort(x.begin(), x.end()); }

inline void sort(std::list<input::element_type>& x) { x.sort(); }

当然,如果您只想硬编码std::string或当前的元素类型也可以正常工作 - 从维护角度来看,如果您稍后更改元素类型,则需要更改此代码.

inline void sort(std::vector<std::string>& x) { std::sort(x.begin(), x.end()); }

inline void sort(std::list<std::string>& x) { x.sort(); }

Answer 2

既然简单的方法已经得到回答,那么让我指出一个艰难的方法:

#include <algorithm>
#include <iterator>
#include <list>
#include <vector>

template <typename IterType>
struct sort
{
    template<typename Cont, typename Comp>
    inline static void impl(Cont &container, Comp F) {
        container.sort(F);
    }
    template<typename Cont>
    inline static void impl(Cont &container) {
        container.sort();
    }
};

template <>
struct sort<std::random_access_iterator_tag>
{
    template<typename Cont, typename Comp>
    inline static void impl(Cont &container, Comp F) {
        std::sort(std::begin(container), std::end(container), F);
    }
    template<typename Cont>
    inline static void impl(Cont &container) {
        std::sort(std::begin(container), std::end(container));
    }
};

template<typename Cont>
void Sort(Cont &container) {
    sort<typename std::iterator_traits<typename Cont::iterator
        >::iterator_category>::impl(container);
}

template<typename Cont, typename Comp>
void Sort(Cont &container, Comp F) {
    sort<typename std::iterator_traits<typename Cont::iterator
        >::iterator_category>::impl(container, F);
}

int main ()
{
    std::list<int> ml;
    std::vector<int> mv;

    Sort(ml);
    Sort(mv);
    Sort(ml, [](int a, int b) { return a > b; });
    Sort(mv, [](int a, int b) { return a > b; });

    return 0;
}

现在,如果你只想区分一个list和一个vector以上将是一个矫枉过正.仅当您需要按类型机制实现标记分派时才使用,该机制可扩展到实现某些迭代器概念的任意容器.

这种方式例如排序std::array或者std::deque不需要额外的过载,因为它们的迭代器可以指向正确的分派结构