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.
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;
}
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.
Using std::list.sort method should be the fastest way.
std::list. But I think he was probably just using the word 'list' as a general term for a sequence container, not necessarily std::list.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);
std::set<Customer*,CompareFunctor>, remove and re-insert whenever you update a Customer) and traverse this in linear time.