Какой самый быстрый способ сортировки списка в C ++?

Question

У меня есть структура

typedef struct  
{ 
    int id;  
    string name;  
    string address;
    string city;  
    // ...
} Customer;

У меня будет несколько клиентов, поэтому мне нужно сохранить эти структуры в некотором списке, а затем отсортировать по идентификатору.Здесь возможно несколько решений, и у меня есть несколько идей, но я ищу лучшее решение с точки зрения производительности.

Answer 1

Используйте sort , предоставляемый пакетом алгоритмов stl, пример:

struct Customer {
    int id;
    Customer(int i) : id(i) {}
};

bool sortfunc(struct Customer i, struct Customer j) {
    return (i.id < j.id);
}

int main() {
    vector<Customer> customers;
    customers.push_back(Customer(32));
    customers.push_back(Customer(71));
    customers.push_back(Customer(12));
    customers.push_back(Customer(45));
    customers.push_back(Customer(26));
    customers.push_back(Customer(80));
    customers.push_back(Customer(53));
    customers.push_back(Customer(33));

    sort(customers.begin(), customers.end(), sortfunc);

    cout << "customers:";
    vector<Customer>::iterator it;
    for (it = customers.begin(); it != customers.end(); ++it)
        cout << " " << it->id;

    return 1;
}

Answer 2

Я бы порекомендовал вам хранить клиентов в std :: set.

Вы должны создать оператор <</p>

bool Customer::operator < (const Customer& other) const {
    return id < customer.id;
}

Теперь, после каждой вставки, коллекция уже отсортирована по id.

И вы можете перебрать всю коллекцию следующим образом:

for(std::set<Customer>::iterator it = your_collection.begin(); it != your_collection.end(); it++)

Это самое быстрое решение, потому что вам ничего не нужно сортировать, и каждая вставка занимает O (log n) времени.

Answer 3

Определите operator< для вашей структуры, чтобы обеспечить отношение порядка между Customer экземплярами:

struct Customer {

    ...

    friend bool operator<(const Customer& a, const Customer& b) {
        return a.id < b.id;
    }

};

Используйте эту таблицу (в частности, блок-схему внизу), чтобы решить, какой контейнер следует использовать в вашей конкретной программе. Если это std::set, ваша сортировка выполняется всякий раз, когда вы вставляете Customer в set. Если это std::list, вызовите функцию-член sort() из списка:

std::list<Customer> customers;
customers.push_back(Customer(...));
...
customers.sort();

Если это std::vector или std::deque, используйте std::sort() из заголовка <algorithm>:

std::vector<Customer> customers;
customers.push_back(Customer(...));
...
std::sort(customers.begin(), customers.end());

Если вам нужно выполнить сортировку несколькими способами, определите функцию сортировки для каждого заказа:

struct Customer {

    ...

    static bool sort_by_name(const Customer& a, const Customer& b) {
        return a.name < b.name;
    }

};

Затем скажите std::list::sort() или std::sort(), чтобы использовать этот компаратор:

customers.sort(Customer::sort_by_name);

std::sort(customers.begin(), customers.end(), Customer::sort_by_name);

Answer 4

Использование метода std :: list.sort должно быть самым быстрым способом.