Fastest way to sort a list of number and their index
std::pair
and std::sort
fit your requirements ideally: if you put the value into the pair.first
and the index in pair.second
, you can simply call a sort
on a vector of pair
s, like this:
// This is your original data. It does not need to be in a vector
vector<long> orig;
orig.push_back(10);
orig.push_back(3);
orig.push_back(6);
orig.push_back(11);
orig.push_back(2);
orig.push_back(19);
orig.push_back(7);
// This is a vector of {value,index} pairs
vector<pair<long,size_t> > vp;
vp.reserve(orig.size());
for (size_t i = 0 ; i != orig.size() ; i++) {
vp.push_back(make_pair(orig[i], i));
}
// Sorting will put lower values ahead of larger ones,
// resolving ties using the original index
sort(vp.begin(), vp.end());
for (size_t i = 0 ; i != vp.size() ; i++) {
cout << vp[i].first << " " << vp[i].second << endl;
}
The obvious starting point would be a structure with operator<
defined for it:
struct data {
unsigned long long int number;
size_t index;
};
struct by_number {
bool operator()(data const &left, data const &right) {
return left.number < right.number;
}
};
...and an std::vector to hold the data:
std::vector<data> items;
and std::sort
to do the sorting:
std::sort(items.begin(), items.end(), by_number());
The simple fact is, that the normal containers (and such) are sufficiently efficient that using them doesn't make your code substantially less efficient. You might be able to do better by writing some part in a different way, but you might about as easily do worse. Start from solid and readable, and test -- don't (attempt to) optimize prematurely.
Edit: of course in C++11, you can use a lambda expression instead:
std::sort(items.begin(), items.end(),
[](data const &a, data const &b) { return a.number < b.number; });
This is generally a little more convenient to write. Readability depends--for something simple like this, I'd say sort ... by_number
is pretty readable, but that depends (heavily) on the name you give to the comparison operator. The lambda makes the actual sorting criteria easier to find, so you don't need to choose a name carefully for the code to be readable.