Page 1 of 1

STL Algorithms ~ Tutorial 1: Using sort() Rate Topic: ***** 1 Votes

#1 Zereo  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 44
  • View blog
  • Posts: 108
  • Joined: 08-November 12

Posted 24 April 2013 - 09:29 AM

Beginning with STL Algorithms
Tutorial #1 the sort() Function

By Zereo




Sorting with the STL



The sort() function in the algorithm header can be a very useful tool to both new and experienced programmers. It's use is to sort containers like arrays and vectors.

Important Information
Now before we start I would like to state that I will be uses features that are only availible on C++11 compilers. If you don't have a C++11 or don't know if your compiler supports it I would recommend doing this. Head on over to codeblocks and download their IDE. It 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.



Here is what the function looks like in its default form, and with the optional third parameter. First take a look at each of these functions and see if we 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



// 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.



Using C++11 to simplify things

We can make sorting whole arrays even easier by using std::begin() and std::end(). std::begin() will return a iterator(pointer) to the first element in the array we pass it. Whereas std::end() will return a iterator(pointer) to one past the last element in the array we pass it. So we could call the sort function by passing it begin() and end() like so.

sort(begin(intArray), end(intArray));




Sorting Vectors and other STL Containers Example



Warning: Uses C++11 features.
// 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 because .begin() returns a iterator to the first element. So 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 iterator that points to 1 past the last element in the container. Remember 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 Features
// 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 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.



Using the STL to simplify sorting in ascending or descending.

Another solution to the problem of getting it to sort descending is to use std::greater(). Which would look like this.

sort(intVec.begin(), intVec.end(), greater<int>());




Sorting User Made Types.



For a lot of program we arenít storing just ints, strings, or doubles. Instead we are making complicated classes with that have multiple number and string members and storing them in a container. So when we want to sort that container of our class objects we need to define a special function that will tell the sort() function how it should sort them object.

So for my last example lets say we have a struct that represents a person and it looks like this.

struct Person
{
    string name;
    int age;
    string favoriteColor;
};


As you can see it has three members: name, age and color. Now lets say we have a program that has a vector full per Person objects, and we need a way to be able to sort them by their name, age or favorite color at certain points in the program.

One way would be to make a function for each different way of sorting like in the example below.

Warning: Uses C++11 Features
// Complicated Types Sorting Example.
// By Zereo 04/22/13
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

struct Person
{
    // Left out making a constructor for simplicity's sake.
    string name;
    int age;
    string favoriteColor;
};

// Sort Container by name function
bool sortByName(const Person &lhs, const Person &rhs) { return lhs.name < rhs.name; }

// Sort Container by age function
bool sortByAge(const Person &lhs, const Person &rhs) { return lhs.age < rhs.age; }

// Sort Container by favorite color
// We can just sort alphabetically and then it will group the
// color together.
bool sortByColor(const Person &lhs, const Person &rhs) { return lhs.favoriteColor < rhs.favoriteColor; }

// A global const variable to hold how many people to ask for input for.
const unsigned numberOfPeople = 2;

int main()
{
    // Make a vector that holds 5 blank Person Objects
    vector<Person> people(numberOfPeople);

    // This will ask for user input to populate the container
    // with 5 different indivuals.
    for (vector<Person>::size_type i = 0; i != numberOfPeople; ++i)
    {
        cout << "Person #" << i + 1 << " name: ";
        cin >> people[i].name;

        cout << "Person #" << i + 1 << " age: ";
        cin >> people[i].age;

        cout << "Person #" << i + 1 << " favorite color: ";
        cin >> people[i].favoriteColor;
    }

    cout << "\n\n";

    // Sort by name
    sort(people.begin(), people.end(), sortByName);
    for (Person &n : people)
        cout << n.name << " ";

    cout << endl;

    // Sory by age
    sort(people.begin(), people.end(), sortByAge);
    for (Person &n : people)
        cout << n.age << " ";

    cout << endl;

    // Sort by color
    sort(people.begin(), people.end(), sortByColor);
    for (Person &n : people)
        cout << n.favoriteColor << " ";

    return 0;
}



Things to know

That was actually a pretty large program and sadly I wonít have space to go through it all. I will however explain a bit about the functions we just made.

Sort By Name Function

bool sortByName(const Person &lhs, const Person &rhs) 
{ 
    return lhs.name < rhs.name;
}


This function is actually very similar to the one we just made before except for we changed two things. We changed the parameter types from int to type Person, and we also changed the return calculation a bit.

First letís go over the change to the parameters.

The reason why we had to change the parameters from int to type Person, is because the container we are sorting is of type vector<Person>. And in order to be able to call the equation lhs.name < rhs.name the parameters would have to be of type Person.

Secondly we changed the return equation to lhs.name < rhs.name. Can you guess what this equation is asking? Well what this is saying is basically this. Remember that both lhs and rhs are pointing to a separate element in the container (Like lhs is element 1 and rhs is element 2). So when we say lhs.name we are telling it to access element 1ís object and then access that objects name member. The same goes for rhs.name but is it accessing element 2ís object instead. So when we say to return lhs.name < rhs.name we are asking it is rhsís objectís name less then rhsís objects name.

The other functions are actually just the same but use the different members of the struct.



THE END ;p

Well that is all for this tutorial, though there is a lot more to learn about sorting with the STL. So if you are interested you can look below for some links to other things that relate to sort(). If you have any comments (Especially on any mistakes) on the article/tutorial please let me know I enjoy any type of feedback good or bad.

The same goes for any questions, if you donít understand anything or the way I explained something didnít make sense (Very likely ;p) please let me know through a reply here or through a PM. I would be glad to help answer any questions you have.

I am hoping to create some more tutorials shortly about how to use algorithms from the STL. Hope everyone liked it and thanks for reading,



Resources


Documentations
std::end()
std::begin()
std::sort()
std::stable_sort
std::greater
std::less

Information
Ranged Based For Loops
Info on initialization in C++11


~ Zereo


Is This A Good Question/Topic? 2
  • +

Replies To: STL Algorithms ~ Tutorial 1: Using sort()

#2 Prim3  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 25
  • Joined: 27-November 12

Posted 16 September 2013 - 01:48 AM

Just started learning sorting techniques, this should be useful! Thanks.
Was This Post Helpful? 0
  • +
  • -

#3 Zereo  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 44
  • View blog
  • Posts: 108
  • Joined: 08-November 12

Posted 16 September 2013 - 05:02 AM

View PostPrim3, on 16 September 2013 - 08:48 AM, said:

Just started learning sorting techniques, this should be useful! Thanks.


Glad it might be of some help :)/>. Though I should point of a typo of mine in the article.

Quote

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
1
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.


If we wanted to start the sorting at the second element of the array we would start it at element 1 not 2 like it said. So instead of

sort(intArray + 2, intArray + SIZE); it should be sort(intArray + 1, intArray +SIZE);

This is because as we know array's and other containers start at 0.

Will try and find sometime to go through the article and correct the grammar typos also.

This post has been edited by Zereo: 16 September 2013 - 05:03 AM

Was This Post Helpful? 1
  • +
  • -

Page 1 of 1