Sort std::vector but ignore a certain number

问题:

I have an std::vector<int> of the size 10 and each entry is initially -1. This vector represents a leaderboard for my game (high scores), and -1 just means there is no score for that entry.

std::vector<int> myVector;
myVector.resize(10, -1);

When the game is started, I want to load the high score from a file. I load each line (up to 10 lines), convert the value that is found to an int with std::stoi, and if the number is >0 I replace it with the -1 currently in the vector at the current position.

All this works. Now to the problem:

Since the values in the file aren't necessarily sorted, I want to sort myVector after I load all entries. I do this with

std::sort(myVector.begin(), myVector.end());

This sorts it in ascending order (lower score is better in my game).

The problem is that, since the vector is initially filled with -1 and there aren't necessarily 10 entries saved in the high scores file, the vector might contain a few -1 in addition to the player's scores.

That means when sorting the vector with the above code, all the -1 will appear before the player's scores.

My question is: How do I sort the vector (in ascending order), but all entries with -1 will be put at the end (since they don't represent a real score)?

回答1:

Combine partitioning and sorting:

std::sort(v.begin(),
          std::partition(v.begin(), v.end(), [](int n){ return n != -1; }));

If you store the iterator returned from partition, you already have a complete description of the range of non-trivial values, so you don't need to look for −1s later.

回答2:

You can provide lambda as parameter for sort:

std::sort(myVector.begin(), myVector.end(),[]( int i1, int i2 ) {
    if( i1 == -1 ) return false;
    if( i2 == -1 ) return true;
    return i1 < i2; }
);

here is the demo (copied from Kerrek)

but it is not clear how you realize where is which score after sort.

回答3:

From your description, it appears that the score can be never negative. In that case, I'd recommend the scores to be a vector of unsigned int. You can define a constant

const unsigned int INFINITY = -1;

and load your vector with INFINITY initially. INFINITY is the maximum positive integer that can be stored in a 32 bit unsigned integer (which also corresponds to -1 in 2's complement)

Then you could simply sort using

sort(v.begin(),v.end());

All INFINITY will be at the end after the sort.

回答4:

std::sort supports using your own comparison function with the signature bool cmp(const T& a, const T& b);. So write your own function similar to this:

bool sort_negatives(const int& a, const int& b)
{
    if (a == -1) {
        return false;
    }
    if (b == -1) {
        return true;
    }
    return a < b;
}

And then call sort like std::sort(myVector.begin(), myVector.end(), sort_negatives);.

EDIT: Fixed the logic courtesy of Slava. If you are using a compiler with C++11 support, use the lambda or partition answers, but this should work on compilers pre C++11.

回答5:

For the following, I assume that the -1 values are all placed at the end of the vector. If they are not, use KerrekSB's method, or make sure that you do not skip the indices in the vector for which no valid score is in the file (by using an extra index / iterator for writing to the vector).

std::sort uses a pair of iterators. Simply provide the sub-range which contains non--1 values. You already know the end of this range after reading from a file. If you already use iterators to fill the vector, like in

auto it = myVector.begin();
while (...) {
    *it = stoi(...);
    ++it;
}

then simply use it instead of myVector.end():

std::sort(myVector.begin(), it);

Otherwise (i.e., when using indices to fill up the vector, let's say i is the number of values), use

std::sort(myVector.begin(), myVector.begin() + i);

回答6:

An alternative approach is to use reserve() instead of resize().

std::vector<int> myVector;
myVector.reserve(10);

for each line in file:
  int number_in_line = ...;
  myVector.push_back(number_in_line);

std::sort(myVector.begin(), myVector.end());

This way, the vector would have only the numbers that are actually in file, no extra (spurious) values (e.g. -1). If the vector need to be later passed to other module or function for further processing, they do not need to know about the special nature of '-1' values.