多次对容器进行排序，使用哪种容器和方法？

Question

我有一些需要打印的数据，为了简单起见，我们假设这是一个包含人员参数的容器（向量）。在程序的不同部分，我需要按不同的参数对所有人进行排序并打印出来。我的问题是：

1.) 选择哪种容器？（我个人选择了vector）。

2.) 什么方法更好，每次都对整个向量进行排序，还是将该向量复制一份并保存为已排序的副本？在我的解决方案中，我每次都对同一向量进行排序，但也许对于速度很慢的大型向量来说，这不是正确的方法。

class Person
{
private:
    std::string name;
    std::string surname;
    int age;
public:
    Person(std::string name, std::string surname, int age) : name{ name }, surname{ surname }, age{ age } {};
    void print() { std::cout << name << " " << surname << " " << age << std::endl; };
    static bool sortName(Person const &A, Person const &B) { return A.name < B.name; };
    static bool sortSurname(Person const &A, Person const &B) { return A.surname < B.surname; };
    static bool sortAge(Person const &A, Person const &B) { return A.age < B.age; };
};

主函数：

int main()
{
    std::vector<Person> persons;
    Person person1("John", "Smith", 30);
    Person person2("Mark", "Cooper", 28);
    Person person3("George", "Orwell", 19);

    persons.push_back(person1);
    persons.push_back(person2);
    persons.push_back(person3);

    std::sort(persons.begin(), persons.end(), Person::sortSurname);
    for (int i = 0; i < persons.size(); ++i)
    {
        persons[i].print();
    }

    // do some other stuff here ... and then ...
    std::sort(persons.begin(), persons.end(), Person::sortName);
    for (int i = 0; i < persons.size(); ++i)
    {
        persons[i].print();
    }

    // do some other stuff here ... and then ...
    std::sort(persons.begin(), persons.end(), Person::sortAge);
    for (int i = 0; i < persons.size(); ++i)
    {
        persons[i].print();
    }

    return 0;
}

- user8024280

---

你需要量化“巨大”，即小于10,000时对向量进行排序，而在10,000,000以上时，你可能需要采用不同的方法。在这两个范围之间进行度量。 - Richard Critten

向量元素的大小也会影响选择，我认为... - user8024280

Answer 1

boost::multi_index_container允许您定义任何类型的容器，其中包含任意数量的不同索引或视图。

该容器在插入和删除操作时会自动更新索引。

这是一个庞大的模板库，需要一些时间来适应，但文档很好，有很多示例。

以下是一种表达方式的实现：

#include <iostream>
#include <string>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/mem_fun.hpp>

class Person {
private:
    std::string name;
    std::string surname;
    int age;
public:
    Person(std::string name, std::string surname, int age) : name{name}, surname{surname}, age{age} {};

    auto get_name() const -> const std::string& { return name; }
    auto get_surname() const -> const std::string& { return surname; }
    auto get_age() const -> int { return age; }

    void print() const { std::cout << name << " " << surname << " " << age << std::endl; };
};

namespace bmi = boost::multi_index;

struct by_name {};
struct by_surname {};
struct by_age;
using PersonTable = boost::multi_index_container<Person,
        bmi::indexed_by<
                bmi::ordered_non_unique<bmi::tag<by_name>, bmi::const_mem_fun<Person,std::string const&,&Person::get_name>>,
                bmi::ordered_non_unique<bmi::tag<by_surname>, bmi::const_mem_fun<Person,std::string const&,&Person::get_surname>>,
                bmi::ordered_non_unique<bmi::tag<by_age>, bmi::const_mem_fun<Person,int,&Person::get_age>>
        >
>;

int main()
{
    PersonTable people;
    people.insert(Person("John", "Smith", 30));
    people.insert(Person("Mark", "Cooper", 28));
    people.insert(Person("George", "Orwell", 19));

    std::cout << "by name" << std::endl;
    for (auto&& person : people.get<by_name>())
    {
        person.print();
    }
    std::cout << "\nby surname" << std::endl;
    for (auto&& person : people.get<by_surname>())
    {
        person.print();
    }
    std::cout << "\nby age" << std::endl;
    for (auto&& person : people.get<by_age>())
    {
        person.print();
    }
}

预期输出：

by name
George Orwell 19
John Smith 30
Mark Cooper 28

by surname
Mark Cooper 28
George Orwell 19
John Smith 30

by age
George Orwell 19
Mark Cooper 28
John Smith 30

文档在此处：http://www.boost.org/doc/libs/1_64_0/libs/multi_index/doc/index.html

- Richard Hodges

Answer 2

考虑将存储 Person 的向量替换为指向 Person 的指针的向量。这样做，仅通过交换指针就可以轻松地交换两个 Person。接下来使用类中定义的函数对象将指针放入所需的排序顺序中，并开始打印。

- EvilTeach

Answer 3

我会使用3个std::set实例，每个都是std::shared_ptr<Person>类型的，分别按照Person的相应字段进行排序：

int main()
{
    std::shared_ptr<Person> person1 = std::make_shared<Person>("John", "Smith", 30);
    std::shared_ptr<Person> person2 = std::make_shared<Person>("Mark", "Cooper", 28);
    std::shared_ptr<Person> person3 = std::make_shared<Person>("George", "Orwell", 19);

    std::set<std::shared_ptr<Person>> persons1([](std::shared_ptr<Person> a, std::shared_ptr<Person> b) {
        return a->name < b->name;
    });
    std::set<std::shared_ptr<Person>> persons2([](std::shared_ptr<Person> a, std::shared_ptr<Person> b) {
        return a->surname < b->surname;
    });
    std::set<std::shared_ptr<Person>> persons3([](std::shared_ptr<Person> a, std::shared_ptr<Person> b) {
        return a->age < b->age;
    });

    persons1.insert(person1);
    persons1.insert(person2);
    persons1.insert(person3);

    persons2.insert(person1);
    persons2.insert(person2);
    persons2.insert(person3);

    persons3.insert(person1);
    persons3.insert(person2);
    persons3.insert(person3);

    return 0;
}

• 使用std::shared_ptr，可以避免在多个容器中存储对象时浪费内存。
• std::set是已经排序的容器，因此每次使用它时都不需要进行排序，只需从开头到结尾枚举元素即可。

- ks1322

Answer 4

我认为，你现在使用的方法是可行的，即在运行时需要排序。对于较大的数据集，您需要首先评估内存和处理能力方面的需求。例如，对于非常大的数据集，您将无法在内存中对其进行排序。而且，如果您决定采用多线程解决方案，则会出现同步问题。因此，您需要一些专业的解决方案，如DBMS，在其中可以按照需要在运行时查询排序数据。您将拥有索引等功能来优化查询时间。

- Azeem

Answer 5

在许多情况下，主要取决于三个因素 -
1. 数据大小
2. 您要寻找的性能类型
3. 您可以为＃2牺牲的空间（内存）数量

通常 std :: sort() 的平均表现为nlogn -

复杂度：平均而言，首尾之间的距离是线性对数级别的：执行大约N * log2（N）（其中N是此距离）元素比较，并且最多可以交换（或移动）那么多元素。

现在，如果您的用例需要经常调用排序方法，则预先排序并保存向量可能是有意义的-在这种情况下，您将获得相当大的性能提升。 现在，在这种设计中，您必须考虑诸如集合是否可修改等情况？ 如果是，则必须考虑平均插入性能影响。

因此，总之，它取决于

- Zakir

Answer 6

如果向量很小或元素复制成本低，您可能可以在需要时重新排序它而不会有任何问题。

如果向量的元素很大且复制成本高，则可以按一种所需方式对向量进行一次排序，然后创建一个std::reference_wrappers的第二个向量，并以不同的方式对其进行排序，以创建原始向量的第二个“视图”，该视图不修改原始向量也不将元素复制到第二个向量中。

至于容器选择，请使用std::vector，除非您特别需要其他容器的某些特性。

无论如何，请使用优化构建基准测试不同的解决方案，并测量不同解决方案的性能，然后再确定使用哪个。

- Jesper Juhl

Answer 7

不要对对象向量进行排序（对于具有许多字段的复杂对象而言，这相当昂贵），而是应该构建几个索引向量，按各种标准对存储在主向量中的对象进行排序。

#include <algorithm>
...

::std::vector< Person > persons;
//  add persons...

::std::vector< ::std::size_t > sorted_indexes;
sorted_indexes.reserve(persons.size());
{
    ::std::size_t index{};
    ::std::generate
    (
        sorted_indexes.begin()
    ,   sorted_indexes.end()
    ,   [&index]{return index++;}
    );
}
::std::sort
(
    sorted_indexes.begin()
,   sorted_indexes.end()
,   [&persons](::std::size_t const left, ::std::size_t const right)
    {
        return Person::sortSurname(persons[left], persons[right]);
    }
);
for(auto person_index: sorted_indexes)
{
    persons[person_index].print();
}

同时，sortSurname应该采用常量引用以避免复制：

static bool sortSurname(Person const & left, Person const & right) { return left.surname < right.surname; };

- user7860670

---

::std 中所有冗余的 :: 是怎么回事？ - Jesper Juhl

这不就是我用std::reference_wrapper提出的解决方案的更复杂版本吗？ - Jesper Juhl

@JesperJuhl 在 ::std 中使用 :: 看起来似乎是多余的，直到你在非全局作用域中遇到其他 std 命名空间并花费数天时间弄清楚为什么事情不像应该那样工作。使用引用包装器的解决方案本质上采用了相同的方法，但是当项目存储在向量中时，使用索引可能更好，因为将更多项目添加到主向量中将使所有引用无效。虽然在这个例子中并不真正相关，因为原始向量没有改变。 - user7860670

@VTT，是的，你说的const引用是正确的...我已经在问题中进行了编辑。 - user8024280