按类型对std::vector进行排序

Question

我是一位有用的助手，能够翻译文本。

我正在观看http://channel9.msdn.com/Events/GoingNative/2013/Writing-Quick-Code-in-Cpp-Quickly，大约在第36分钟左右，他们谈到如果您要调用虚拟方法，则按其元素类型对集合进行排序的好处。

因此，给定

class Base {};
class Der1 : public Base {};
class Der2 : public Base {};
class Der3 : public Base {};

vector<Base *> myVector;

你如何对myVector进行排序，以使每种类型的元素都相邻？

是否有一种方法可以不使用虚函数来识别每个派生类型而实现这一点？（也许使用typeid？）

- José D.

---

Herb Sutter最近的Build 2014演讲也涵盖了这种优化方法。像往常一样，这是一场非常精彩的演讲。 - chris

Answer 1

你可以使用 type_index 来实现。你可以通过从 typeid 运算符返回的 type_info 对象构造一个 type_index 对象。这是一个带有重载关系运算符并具有明确定义排序的类，因此它在关联容器和类似容器中作为键类型非常有用。

以下是一个示例：

#include <typeinfo>
#include <typeindex>
#include <vector>
#include <algorithm>
#include <iostream>

struct Base {
    virtual ~Base() {}
    virtual const char* who() = 0;
};
struct D1 : Base { const char* who() { return "D1\n"; } };
struct D2 : Base { const char* who() { return "D2\n"; } };
struct D3 : Base { const char* who() { return "D3\n"; } };

int main()
{
    std::vector<Base*> vec { new D2, new D1, new D3, new D3, new D1, new D2 };
    std::sort( vec.begin(), vec.end(),
    [](const Base* p1, const Base* p2)
    {
        return
            std::type_index(typeid(*p1)) <
            std::type_index(typeid(*p2));
    });

    for (auto p : vec) { std::cout << p->who(); }
}

输出结果为：

D1
D1
D2
D2
D3
D3

- jrok

---

值得注意的是，它与智能指针一样有效 :) - chris

Answer 2

您可以指定比较函数。有关详细信息，请参见例如在两个值上对STL向量进行排序。

在比较函数内部，您可以编写任何内容。它可以比较对象的任何属性。特别地，它可以比较通过虚函数获得的一个特定值，例如getType()，它可能在Der1中返回1，在Der2中返回2，在Der 3中返回3。

- Daniel Daranas

Answer 3

你可以实现一个虚函数，比如说prio，它返回类型中的优先级（一个int）；prio应该在派生类中适当地实现。然后实现一个比较器，它会对两个Base实例上的prio进行评估以进行比较。

- Codor

Answer 4

这些只是可能性，没有一个真正的答案。

排序？

排序的主要问题是找到一个用于排序的关键字。这是“第一阶段”，如果你想的话。第二阶段是使用标准库中的通用排序，通常比第一阶段容易。

关键字

一种可能性是使用 typeid / type_info。

type_info 的实例定义了 operator == 和 operator !=，以及一个 hash_code 成员函数。

排序

使用标准算法中的通用排序算法。作为排序的关键字，你可以使用从 hash_code 函数返回的值。

- Sebastian Mach