All geek questions in one place

Sort container several times, which container and what to use

I have some data that I need to print, for simplicity we can say that this is a container (vector) of people who have some parameters. In different parts of my program, I need to print all of them, sorted by different parameters. My question is:

1.) which container to choose? (I personally chose the vector).

2.) Which approach is better, sort the entire vector each time, or is it better to make a copy of this vector and keep it sorted? In my solution, I sorted the same vector every time, but maybe this is the wrong approach with huge vectors due to speed.

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

home:

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;
}
+4
source share
7

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

+5

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 , , .
+2

Person, Person. , . , , .

+2

IMO, , , , , , . . , . , , . , - , , . , .

+1

3 -
1.
2.
3. (), # 2

std::sort() avg nlogn -

, - last: N * log2 (N) ( N - ) , ( ).

, , , . . , ? , ? , avg.

,

+1

( , ), , , .

#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; };
+1

, , - .

, , , std:: reference_wrapper -, "" , .

; std::vector, .

In any case, compare different solutions (with optimized builds) and measure the performance of different solutions before installing them on one.

+1
source

Source: https://habr.com/ru/post/1680560/

More articles:


All Articles