Sorting and Searching Without Writing Either

Chapter 11 had you write a highest function: set up a best-so-far, walk the vector, keep the bigger one. It was about ten lines and one of them was wrong.

Sorting is the same kind of job and much worse. Every beginner writes a sort eventually, gets it nearly right, and discovers that “nearly right” and “wrong” are the same thing here.

You don’t have to. C++ comes with them.

sort

#include <algorithm>

std::vector<int> scores{40, 10, 30, 20};

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

10 20 30 40

The vector is sorted in place. scores itself is rearranged, and nothing is returned. This is one of those cases where reading the line tells you very little and you simply have to be told.

<algorithm> is a new header, and it holds several dozen of these. It is the first time in this book that the interesting thing is not language syntax but knowing what’s in the box.

Those begin and end things

scores.begin(), scores.end() is a strange way to say “all of it”, and it turns up in every algorithm in this chapter.

They are markers: begin() marks the first element, end() marks the spot just past the last one. Passing both means work on the whole vector. Passing different markers would mean work on part of it, which is occasionally useful and not what you’re here for.

For now, treat thing.begin(), thing.end() as a single lump of punctuation that means “the whole thing”. What those markers actually are is chapter 29, and they turn out to be one of the better ideas in the language. Learning them now would cost you this chapter.

Sorting other things

Strings sort too, and the result will surprise you exactly once:

std::vector<std::string> words{"pear", "Apple", "apple", "Banana"};
std::sort(words.begin(), words.end());

Apple Banana apple pear

Not alphabetical. Every capital letter comes before every lowercase one, because the comparison is on character codes and the alphabet was numbered twice: capital A through Z first, then lowercase a through z. Banana beats apple because B is 66 and a is 97.

Case-insensitive sorting is a real job with real complications, and the tools for it belong later. What matters now is recognising the symptom, because “my sort put all the capitals first” looks like a broken sort and isn’t.

Sorting backwards

sort takes an optional third argument: a function that answers “should a come before b?”

bool higher(int a, int b) {
    return a > b;
}

std::sort(scores.begin(), scores.end(), higher);

40 30 20 10

Note what’s passed: higher, with no brackets after it. You are not calling it. you are handing sort the function itself, to call as many times as it needs. A function can be a value. That is a genuinely new idea and it is the seed of chapter 29.

The function takes two of whatever you’re sorting and returns a bool. a > b means “a comes first when it’s bigger”, which is descending order. Swap it for a < b and you’re back to ascending, which is what you get with no third argument at all.

This looks like a small thing on a vector of ints. It stops being small in the next chapter, where you’ll have contacts with names and phone numbers and will want them by name, and the only change is which comparison function you hand over.

find

std::find looks for a value:

auto found = std::find(v.begin(), v.end(), 30);

if (found != v.end()) {
    std::cout << "found 30\n";
}

It does not return true or false, and it does not return a position. It returns one of those markers, pointing at the element it found, or at end() if it never found one.

So the test for “was it there” is comparing against end():

if (found != v.end())    // yes, it's in there
if (found == v.end())    // no, it isn't

Copy that shape. It reads oddly now and it’s worth knowing on sight, because it is everywhere in real C++ code. end() means “past the last element”, so a marker pointing there is the library’s way of saying nowhere.

Sorting without losing the original

sort rearranges what you give it, and sometimes you need the old order back: the file as it was written, the scores in the order they were entered. There is no flag for this. Copy it first:

std::vector<int> sorted = scores;
std::sort(sorted.begin(), sorted.end());

original first: 40, sorted first: 10

Chapter 12’s copying rule in reverse: here the copy is the point, and paying for it is cheaper than losing the original.

Two more worth knowing while you’re here. std::reverse flips a vector end to end and on a sorted vector that is a second way to get descending order, without a comparison function. And std::count tells you how many times a value appears:

std::count(scores.begin(), scores.end(), 10);   // 2

Unlike find, count gives you a plain number, so there’s no end() comparison to remember. When you only want to know whether something is present, count(...) > 0 reads better than the find version and costs a little more.

accumulate

Adding up a vector is a range-for and a running total, which you can write in your sleep by now. There’s a ready-made one, in a different header:

#include <numeric>

int sum = std::accumulate(v.begin(), v.end(), 0);

The third argument is what to start from, and nearly always 0. Starting from 100 gives you 100 plus the total, which is occasionally what you want.

Top five
1. 300
2. 210
3. 180
4. 120
5. 99

Entries: 8
Best:    300
Average: 129

int count = scores.size();
int average = sum / count;