How to sort a vector of custom objects in C++98

This article shows how to sort a collection of custom Skyscraper objects using sort algorithm from the standard C++ library. You will only need basic knowledge of operator overloading to accomplish the task.

Note: If you need to sort custom objects in C++11, read this article which shows how to accomplish the sorting with the help of a lambda expression.

How to use the sort algorithm

What we will try to do in this article is to sort the Skyscrapers by their height. But before we do to that, we are going to accomplish a much simpler task - sorting integer numbers. After that, we are going to deal with our collection of custom objects.

I am going to illustrate how sorting works on the main.cpp below. The collection of numbers is represented by the container 'vector' (requires to #include<vector>). To accomplish sorting we are going to use the algorithm 'sort' from the standard library (requires to #include<algorithm>). The default version of 'sort' takes two arguments - the iterator to the initial and final position of a sequence to be sorted. By default, the sequence is sorted in ascending order.

#include<iostream>
#include<vector>
#include<algorithm>

int main()
{
    std::vector<int> numbers;
    numbers.push_back(10);
    numbers.push_back(14);
    numbers.push_back(20);
    numbers.push_back(2);
    numbers.push_back(9);

    std::sort(numbers.begin(),numbers.end());
    for(unsigned int i = 0; i < numbers.size(); i++)
        std::cout << numbers.at(i) << '\n';

    return 0;
}

For the moment there is not much more we need to know. If you run the code you will get the numbers sorted in ascending order.

2
9
10
14
20

Sorting Skyscrapers

Now that we know how to use the sort algorithm, we can proceed with sorting skyscrapers. We are going to use the implementation of Skyscraper with two member variables (name and height) to accomplish this.

#ifndef SKYSCRAPER_H
#define SKYSCRAPER_H
#include <string>
#include <iostream>
#include <stdexcept>

class Skyscraper
{
public:
    Skyscraper(const std::string& name, double height);
    double getHeight() const {return m_height;}
    std::string getName() const {return m_name;}
    void print() const;

private:
    std::string m_name;
    double m_height;
};        

#include "skyscraper.h"

Skyscraper::Skyscraper(const std::string &name, double height):
    m_name(name), m_height(height){
    if(m_height < 0)
        throw std::invalid_argument(
                "Height must be non-negative.");
}

void Skyscraper::print() const {
    std::cout << this->m_name << " "
              << this->m_height << '\n';
}

Ideally, what we would like to do is to sort the Skyscrapers in pretty much the same way we sorted the integer numbers. You can see the scenario in the main.cpp below. I created a vector of 4 skyscrapers and called the sort algorithm on the vector just as we did with the integers.

#include <iostream>
#include <vector>
#include <algorithm>
#include "skyscraper.h"

int main()
{
    std::vector<Skyscraper> skyscrapers;
    skyscrapers.push_back(Skyscraper("Empire State", 381));
    skyscrapers.push_back(Skyscraper("Petronas", 452));
    skyscrapers.push_back(Skyscraper("Burj Khalifa", 828));
    skyscrapers.push_back(Skyscraper("Taipei", 509));

    std::sort(skyscrapers.begin(),skyscrapers.end());
    for(unsigned int i = 0; i < skyscrapers.size(); i++)
        skyscrapers.at(i).print();

    return 0;
}

Unfortunately, if you try to compile the code above, it won't work. The compiler will also tell you why: no match for 'operator<' in '__a <__b'. What does this mean, you are asking?

Overloading operator <

The compiler has no way of knowing how to sort the skyscrapers! In the end, it is a user-defined class and the compiler does not know how we intended for the class to work. We will have to tell him that. In fact, it is not so difficult. We do not have to care about how the sort algorithm works, at all. We only have to tell the compiler how to evaluate which one out of two arbitrary skyscrapers is shorter. How do we know that? The compiler actually implied that with the error statement 'no match for operator<...'. This means that we will have to overload the operator<.

This article shows two different ways of operator< overloading (non-member and member approach). The non-member approach requires that we define the operator< outside of the Skyscraper class. The non-member approach is easier to understand and also the preferred approach according to the new C++ Core Guidelines (C.161: Use nonmember functions for symmetric operators). This means that we are going to add an extra line behind the class brackets in skyscraper.h. Notice that the function has two references to skyscrapers as parameters. They are declared as const as the operator< should not modify any of the skyscrapers.

#ifndef SKYSCRAPER_H
#define SKYSCRAPER_H
#include <string>
#include <iostream>
#include <stdexcept>

class Skyscraper
{
public:
    Skyscraper(const std::string& name, double height);
    double getHeight() const {return m_height;}
    std::string getName() const {return m_name;}
    void print() const;

private:
    std::string m_name;
    double m_height;
};

bool operator<(const Skyscraper &s1, const Skyscraper &s2);

You can see the details of the overloaded operator< in skyscraper.cpp below. The operator< evaluates the Skyscraper s1 as shorter than the Skyscraper s2 if the height of s1 is less than the height of s2. There is no scope resolution operator::, as operator< is not a member of the class Skyscraper.

#include "skyscraper.h"

Skyscraper::Skyscraper(const std::string &name, double height):
    m_name(name), m_height(height){
    if(m_height < 0)
        throw std::invalid_argument(
                "Height must be non-negative.");
}

void Skyscraper::print() const {
    std::cout << this->m_name << " "
              << this->m_height << '\n';
}

bool operator<(const Skyscraper &s1, const Skyscraper &s2){
    return s1.getHeight() < s2.getHeight();
}

Note: The code snippet

bool operator<(const Skyscraper &s1, const Skyscraper &s2){
    return s1.getHeight() < s2.getHeight();
}

is equivalent to:

bool operator<(const Skyscraper &s1, const Skyscraper &s2){
    if(s1.getHeight() < s2.getHeight())
        return true;
    else
        return false;
}

Notice that it is us that defines what 'less than' means. We should always make sure that what we define as 'less than' makes sense in the context of our class. In the context of Skyscrapers, it makes sense to say that s1 < s2 if the height of s1 is less than the height of s2. But of course, the body of the function can look completely arbitrarily, e.g. like the code below, which ranks the skyscraper as shorter if its name is shorter. Is that a good definition of 'less than' in the context of our class? Probably not.

bool operator<(const Skyscraper &s1, const Skyscraper &s2){
    return s1.getName().size() < s2.getName().size();
}

Now you can run the code with the original main.cpp. The sorting algorithm will now work with the class Skyscraper and you will get the correct result.

Empire State 381
Petronas 452
Taipei 509
Burj Khalifa 828

If you are accustomed to the use of the pointer 'this', you might want to overload the operator< as part of the Skyscraper class. This is called the member approach (this approach is no longer recommended by C++ Core Guidelines C.161 for this particular situation). In the member-approach, the operator< is part of the public section of the class Skyscraper. In the skyscraper.cpp notice that the parameter s1 disappeared, it has been 'substituted' by the pointer 'this'.

#ifndef SKYSCRAPER_H
#define SKYSCRAPER_H
#include <string>
#include <iostream>
#include <stdexcept>

class Skyscraper
{
public:
    Skyscraper(const std::string& name, double height);
    double getHeight() const {return m_height;}
    std::string getName() const {return m_name;}
    void print() const;
    // flagged, see C.161 C++ Core Guidelines
    bool operator <(const Skyscraper& s2) const;

private:
    std::string m_name;
    double m_height;
};

#endif // SKYSCRAPER_H

#include "skyscraper.h"

Skyscraper::Skyscraper(const std::string &name, double height):
    m_name(name), m_height(height){
    if(m_height < 0)
        throw std::invalid_argument(
                "Height must be non-negative.");
}

void Skyscraper::print() const {
    std::cout << this->m_name << " "
              << this->m_height << '\n';
}

bool Skyscraper::operator <(const Skyscraper& s2) const {
    return this->m_height < s2.m_height;
}

How to sort vector of objects according to a specific parameter - use of a function object

To show you how to sort objects according to a specific parameter, I introduced an extra attribute into the Skyscraper class - namely the number of floors. Now we have two different parameters according to which we can sort and we need to inform the sorting function about this parameter.

class Skyscraper
{
public:
    Skyscraper(const std::string& name, double height, int nrFloors);
    double getHeight() const {return m_height;}
    std::string getName() const {return m_name;}
    int getNrFloors() const {return m_nrFloors;}
    void print() const;

private:
    std::string m_name;
    double m_height;
    int m_nrFloors;
};

Perhaps you noticed that there are two different versions of the sort function. The first one relies on operator< to compare the objects (what we did before), the second one takes a comparison function object as a parameter. A function object is simply an object that can be called as if it was a function. To achieve this, it defines operator(). You can see this below, represented by the structure EntityComp in skyscraper.h. The operator() more or less does the same thing as the operator< did for our class before. It takes references to two Skyscraper objects and returns the result of the comparison.

struct EntityComp {
  int property;
  EntityComp(int property) {this->property = property;}
  bool operator()(const Skyscraper& s1, const Skyscraper& s2) const {
      if(property == FLOORS)
          return s1.getNrFloors() < s2.getNrFloors();
      else
          return s1.getHeight() < s2.getHeight();
  }
};

If we had only one parameter according to which we needed to sort, overloading operator() would be all we would need to do to make the sort function work. It would also be an alternative to the solution from the previous section. However, because we need to account for the parameter (nrFloors or height), we need to introduce an extra attribute into the object responsible for sorting (in the code above). The attribute's name is 'property'. FLOORS and HEIGHT are const ints that are defined in the file itemnames.h.

Now all that are sorting function needs to do is to call the following:

std::sort(skyscrapers.begin(),skyscrapers.end(), EntityComp(FLOORS));

You can see the complete use below:

int main()
{
    std::vector<Skyscraper> skyscrapers;
    skyscrapers.push_back(Skyscraper("Empire State", 381, 102));
    skyscrapers.push_back(Skyscraper("Petronas", 452, 88));
    skyscrapers.push_back(Skyscraper("Burj Khalifa", 828, 163));
    skyscrapers.push_back(Skyscraper("Taipei", 509, 101));

    std::sort(skyscrapers.begin(),skyscrapers.end(), EntityComp(FLOORS));
    for(unsigned int i = 0; i < skyscrapers.size(); i++)
        skyscrapers.at(i).print();

    return 0;
}

If you run the code, you will get the following output (the second number represents the number of floors).

Petronas 452 88
Taipei 509 101
Empire State 381 102
Burj Khalifa 828 163

That's it! As an exercise, try changing the parameter to HEIGHT.

Tagged: C++