All criticism is welcome especially if you see any mistakes on the code. Be warned I am probably not the best writer in the world and this is my first tutorial I have ever done so ;p.
This tutorial is aimed at beginners that have some knowledge of C++ but have yet to dabble much with the STL. This is part of the a series of tutorials I am putting together about algorithms and the usefulness of the STL.
Also I have yet to actually go through this more then once to do spelling corrections and all that so this is basically a first draft.
Let me know what you think thank you :)
Beginning with STL Algorithms
Tutorial #1 the sort() Function
By Zereo
Sort Function
First before we start lets take a quick look at how the function looks and what it does.
Here is what the function looks like in its default form, and with the optional third parameter. Don’t worry I will explain each parameter and more in a second, but first take a look at each of these functions and see if you can figure out what each parameter does.
Example 1~
std::sort(myvector.begin(), myvector.end())
Example 2~
std::sort(myvector.begin(), myvector.end(), myCompFuncion)
So lets go dig into these and figure out what each does and why it does it. First lets go over what everything is.
Found in ~
#include <algorithm>
Parameter 1 myvector.begin()~ The first parameter is where you will be putting a iterator(Pointer) to the first element in the range that you want to sort. The sort will include the element that the iterator points to.
Parameter 2 myvector.end() ~ The second parameter is almost like the first but instead of putting a iterator to the first element to sort you will be putting a iterator to the last element. One very important difference is that the search won’t include the element that this iterator points to. It is [First,Last) meaning it includes the first parameter in the sort but it doesn’t include the second parameter in the sort.
Parameter 3 myCompFunction() Optional ~ I will only give a brief description here, because I will explain this parameter in more detail later. The third parameter is used to define how you do the search. For example if you have a struct that has 3 different variables in it how does the function know which one to sort? Or how does it know how it should sort it? This is what this parameter is for. I will explain this more in a bit.
Function Return ~ This function doesn’t return anything because it alters the container directly through iterator (Pointers).
Array Example
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
|
// sort() Example using arrays.
// By Zereo 04/22/13
#include <iostream>
#include <algorithm>
using namespace std;
const int SIZE = 7;
int main()
{
int intArray[SIZE] = {5, 3, 32, -1, 1, 104, 53};
//Now we call the sort function
sort(intArray, intArray + SIZE);
cout << "Sorted Array looks like this." << endl;
for (size_t i = 0; i != SIZE; ++i)
cout << intArray[i] << " ";
return 0;
}
|
Things to know
When we use the sort function to sort a array our arguments will look a bit different then when we use it on a vector for example. In the example above when we pass in intArray as a argument we are telling the function to start the sort at the beginning of the array. If we wanted it to start the sort at the second element of the array we would do
sort(intArray + 2, intArray + SIZE);
. So when we do intArray + SIZE for the second argument we are telling the array to sort up to the last element in the array.
Sorting Vectors and other STL Containers Example
Warning: This example uses features that are only available in C++11 compilers. If you try this code and it doesn’t compile you most likely don’t have a C++11 compiler. Since the last time I checked Code::Blocks IDE comes with a C++11 compiler and you can enable it by going to settings->compiler->compiler settings->compiler flags-> and then you should see a checkbox that says something like Have g++ follow the C++11 ISO C++ language standard. Enable that and click ok and you should be good to go.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
|
// Vector Sorting Example.
// By Zereo 04/22/13
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
int main()
{
// Warning this type of initialization requires a C++11 Compiler
vector<int> intVec = {56, 32, -43, 23, 12, 93, 132, -154};
vector<string> stringVec = {"John", "Bob", "Joe", "Zack", "Randy"};
// Sorting the int vector
sort(intVec.begin(), intVec.end());
for (vector<int>::size_type i = 0; i != intVec.size(); ++i)
cout << intVec[i] << " ";
cout << endl;
// Sorting the string vector
sort(stringVec.begin(), stringVec.end());
// Ranged Based loops. This requires a C++11 Compiler also
// If you don't have a C++11 Compiler you can use a standard
// for loop to print your vector.
for (string &s : stringVec)
cout << s << " ";
return 0;
}
|
Things to know:
First as you can see the sorting function works almost the same as on a array but we just have to pass our arguments a little differently. Since the first parameter in sort() accepts a iterator(pointer) to the first element we want to sort we can pass stringVec.begin() to it and it will start sorting at the first element in the vector. The same goes for stringVec.end() for the second parameter because remember stringVec.end() is a pointer to 1 past the last element in the container, and the sort function sorts up to but not including what we pass in as the second parameter.
You also probably noticed that the sort works on things other then numbers. When we printed out the vector of strings it gave us a nice and neat vector that holds the names in their alphabetical order.
The Third Optional Parameter.
The third parameter in the sort() function is actually a very useful feature. It allows up to define how the sort() function will actually perform the search. This parameter is optional because for basic types and containers it isn’t needed most of the time. But what if we wanted to change how the container was sorted by having it sort by descending instead of ascending? Or what if we had a container full of a special type of class we created and need to sort that container a special way? Well this is where the third parameter comes in.
Making it sort by descending order example.
Warning: Uses C++11 Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
|
// Vector Sorting Descending Example.
// By Zereo 04/22/13
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// We need this function to define how to sort
// the vector. We will pass this function into the
// third parameter and it will tell it to sort descendingly.
bool wayToSort(int i, int j) { return (i>j); }
int main()
{
vector<int> intVec = {56, 32, -43, 23, 12, 93, 132, -154};
// Do not include the () when you call wayToSort
// It must be passed as a function pointer or function object
sort(intVec.begin(), intVec.end(), wayToSort);
for (int i : intVec)
cout << i << " ";
return 0;
}
|
The Function
First lets look at the function. What we did is we created a function that will determine whether i > j if it is it will return true, if not it will return false every time it is called. The sort function will automatically assign a element to both i and j.
The function you make needs to have a return type of bool and must return only types that can be converted into bool.
So when we defined
bool wayToSort(int i, int j) { return (i>j); }
We are saying we wanted it to sort descending because i > j whereas ascending would be i < j.