CODEWITHSUNDEEP
c++performancelistsortingdata-structures
Pittfall
Pittfall

Reputation: 2851

What is the fastest way to sort some sort of list in c++?

I have a struct

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

I will have multiple customers so I need to store these structs in some sort of a list and then I need to sort by id. There a probably multiple solutions here and I have a few ideas myself but I am looking for the best solution in terms of performance.

Upvotes: 1

Views: 362

Answers (4)

dacwe
dacwe

Reputation: 43504

Use the sort provided by the stl algorithms package, example:

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

Upvotes: 9

Jarosław Gomułka
Jarosław Gomułka

Reputation: 4995

I would recommend you storing Customers in std::set.

You should create operator <

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

Now, after each insert, collection is already sorted by id.

And you can iterate over whole collection by:

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

This is fastest solution because you don't need to sort anything, and each insert takes O(log n) time.

Upvotes: 4

Jon Purdy
Jon Purdy

Reputation: 54971

Define operator< for your structure to provide an ordering relation between Customer instances:

struct Customer {

    ...

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

};

Use this cheatsheet (in particular the flowchart at the bottom) to decide which container you should use in your particular program. If it’s std::set, your sorting is done whenever you insert a Customer into the set. If it’s std::list, call the sort() member function on the list:

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

If it’s std::vector or std::deque, use std::sort() from the <algorithm> header:

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

If you need to sort in multiple ways, define a sorting function for each ordering:

struct Customer {

    ...

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

};

Then tell std::list::sort() or std::sort() to use that comparator:

customers.sort(Customer::sort_by_name);

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

Upvotes: 0

synopia
synopia

Reputation: 2314

Using std::list.sort method should be the fastest way.

Upvotes: 0

Related Questions