Sort std::vector but ignore a certain number

Question

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)?

Why do you need to initially set the vector size to be 10? can you expand its size as you read the scores from the file? — Biruk Abebe, Apr 21 '16 at 18:38
`std::sort` takes another parameter that lets you specify a comparison function or object. Just write that function to make -1 come last instead of first. — Mark Ransom, Apr 21 '16 at 18:39
Use an unsigned int and std::numeric_limits::max(). It'll always come last and you can check for that instead of "-1". — kfsone, Apr 21 '16 at 18:41
`std::vector` the signed -1 will be converted to unsigned in comparisons. Ugly and hackish but quick. — Captain Giraffe, Apr 21 '16 at 18:42
How about a more radical change. Start with an empty vector. Reserve capacity 10. Then push back only the positive values as you find them. At the end, resize the thing to `(10, -1)` (if you even need that). — Kerrek SB, Apr 21 '16 at 18:58

score 9 · Accepted Answer · answered Apr 21 '16 at 18:42

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.

score 3 · Answer 2 · answered Apr 21 '16 at 18:44

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.

score 2 · Answer 3 · answered Apr 21 '16 at 18:51

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.

dquam · Answer 4 · 2016-04-21T18:50:15.933

0

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.

edited Apr 21 '16 at 18:50

answered Apr 21 '16 at 18:42

dquam

101
4

2

who +1 this answer should try to run it first – Slava Apr 21 '16 at 18:44
Fixed. Thanks Slava. – dquam Apr 21 '16 at 18:55
Algorithms with predicates were perfectly fine in C++03. You might need to write a predicate yourself, but that's not that bad. – Kerrek SB Apr 21 '16 at 18:56

leemes · Answer 5 · 2016-04-21T19:00:38.983

0

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

edited Apr 21 '16 at 19:00

answered Apr 21 '16 at 18:53

leemes

44,967
21
135
183

Hm, the way I read the OP's description was that the input file could contain arbitrary negative numbers, too. In that case you'd advance the cursor, but you wouldn't assign a value. – Kerrek SB Apr 21 '16 at 18:54
Well, I wasn't sure either. But one could easily introduce a counter for the non-negative values, which is then used to access the vector. Then they are all contiguously placed at the beginning of the vector. – leemes Apr 21 '16 at 18:56
Yeah, you could just skip over the negative values in the input. That said, you don't need any -1s at all, you can just build the vector as you go along and then resize it at the end... – Kerrek SB Apr 21 '16 at 18:58
Yup, already discussed in the question's comments... Just wanted to give an alternative to your solution. I'll mention my assumption in the answer. – leemes Apr 21 '16 at 18:58

score 0 · Answer 6 · answered Apr 21 '16 at 20:37

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.

Sort std::vector but ignore a certain number

6 Answers6

Linked