Is There Support in C++/Stl for Sorting Objects by Attribute

Is there support in C++/STL for sorting objects by attribute?

Generic adaptor to compare based on member attributes. While it is quite more verbose the first time it is reusable.

// Generic member less than
template <typename T, typename M, typename C>
struct member_lt_type 
{
   typedef M T::* member_ptr;
   member_lt_type( member_ptr p, C c ) : ptr(p), cmp(c) {}
   bool operator()( T const & lhs, T const & rhs ) const 
   {
      return cmp( lhs.*ptr, rhs.*ptr );
   }
   member_ptr ptr;
   C cmp;
};

// dereference adaptor
template <typename T, typename C>
struct dereferrer
{
   dereferrer( C cmp ) : cmp(cmp) {}
   bool operator()( T * lhs, T * rhs ) const {
      return cmp( *lhs, *rhs );
   }
   C cmp;
};

// syntactic sugar
template <typename T, typename M>
member_lt_type<T,M, std::less<M> > member_lt( M T::*ptr ) {
   return member_lt_type<T,M, std::less<M> >(ptr, std::less<M>() );
}

template <typename T, typename M, typename C>
member_lt_type<T,M,C> member_lt( M T::*ptr, C cmp ) {
   return member_lt_type<T,M,C>( ptr, cmp );
}

template <typename T, typename C>
dereferrer<T,C> deref( C cmp ) {
   return dereferrer<T,C>( cmp );
}

// usage:    
struct test { int x; }
int main() {
   std::vector<test> v;
   std::sort( v.begin(), v.end(), member_lt( &test::x ) );
   std::sort( v.begin(), v.end(), member_lt( &test::x, std::greater<int>() ) );

   std::vector<test*> vp;
   std::sort( v.begin(), v.end(), deref<test>( member_lt( &test::x ) ) );
}

Sorting a vector of custom objects

A simple example using std::sort

struct MyStruct
{
    int key;
    std::string stringValue;

    MyStruct(int k, const std::string& s) : key(k), stringValue(s) {}
};

struct less_than_key
{
    inline bool operator() (const MyStruct& struct1, const MyStruct& struct2)
    {
        return (struct1.key < struct2.key);
    }
};

std::vector < MyStruct > vec;

vec.push_back(MyStruct(4, "test"));
vec.push_back(MyStruct(3, "a"));
vec.push_back(MyStruct(2, "is"));
vec.push_back(MyStruct(1, "this"));

std::sort(vec.begin(), vec.end(), less_than_key());

---

Edit: As Kirill V. Lyadvinsky pointed out, instead of supplying a sort predicate, you can implement the operator< for MyStruct:

struct MyStruct
{
    int key;
    std::string stringValue;

    MyStruct(int k, const std::string& s) : key(k), stringValue(s) {}

    bool operator < (const MyStruct& str) const
    {
        return (key < str.key);
    }
};

Using this method means you can simply sort the vector as follows:

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

Edit2: As Kappa suggests you can also sort the vector in the descending order by overloading a > operator and changing call of sort a bit:

struct MyStruct
{
    int key;
    std::string stringValue;

    MyStruct(int k, const std::string& s) : key(k), stringValue(s) {}

    bool operator > (const MyStruct& str) const
    {
        return (key > str.key);
    }
};

And you should call sort as:

std::sort(vec.begin(), vec.end(),greater<MyStruct>());

Sorting a vector of objects by a property of the object

There are several different objects and several different properties that could it be sorted by.

While the solution Erik posted is correct, this statement leads me to think that it's impractical at best if you are in fact planning to sort by multiple public data members of multiple classes in multiple ways in the same program, as each sorting method will require its own functor type.

I recommend the following abstraction:

#include <functional>

template<typename C, typename M, template<typename> class Pred = std::less>
struct member_comparer : std::binary_function<C, C, bool> {
    explicit member_comparer(M C::*ptr) : ptr_{ptr} { }

    bool operator ()(C const& lhs, C const& rhs) const {
        return Pred<M>{}(lhs.*ptr_, rhs.*ptr_);
    }

private:
    M C::*ptr_;
};

template<template<typename> class Pred = std::less, typename C, typename M>
member_comparer<C, M, Pred> make_member_comparer(M C::*ptr) {
    return member_comparer<C, M, Pred>{ptr};
}

Usage would look like:

#include <algorithm>
#include <string>
#include <vector>

struct MyClass {
    int         i;
    std::string s;

    MyClass(int i_, std::string const& s_) : i{i_}, s{s_} { }
};

int main() {
    std::vector<MyClass> vec;
    vec.emplace_back(2, "two");
    vec.emplace_back(8, "eight");

    // sort by i, ascending
    std::sort(vec.begin(), vec.end(), make_member_comparer(&MyClass::i));
    // sort by s, ascending
    std::sort(vec.begin(), vec.end(), make_member_comparer(&MyClass::s));
    // sort by s, descending
    std::sort(vec.begin(), vec.end(), make_member_comparer<std::greater>(&MyClass::s));
}

This will work for any type with public data members, and will save a lot of typing if you need to sort your classes more than a couple of different ways.

Here is a variation that works with public member functions instead of public data members:

#include <functional>

template<typename C, typename M, template<typename> class Pred = std::less>
struct method_comparer : std::binary_function<C, C, bool> {
    explicit method_comparer(M (C::*ptr)() const) : ptr_{ptr} { }

    bool operator ()(C const& lhs, C const& rhs) const {
        return Pred<M>{}((lhs.*ptr_)(), (rhs.*ptr_)());
    }

private:
    M (C::*ptr_)() const;
};

template<template<typename> class Pred = std::less, typename C, typename M>
method_comparer<C, M, Pred> make_method_comparer(M (C::*ptr)() const) {
    return method_comparer<C, M, Pred>{ptr};
}

With usage like:

#include <algorithm>
#include <string>
#include <vector>

class MyClass {
    int         i_;
    std::string s_;

public:
    MyClass(int i, std::string const& s) : i_{i}, s_{s} { }

    int                i() const { return i_; }
    std::string const& s() const { return s_; }
};

int main() {
    std::vector<MyClass> vec;
    vec.emplace_back(2, "two");
    vec.emplace_back(8, "eight");

    // sort by i(), ascending
    std::sort(vec.begin(), vec.end(), make_method_comparer(&MyClass::i));
    // sort by s(), ascending
    std::sort(vec.begin(), vec.end(), make_method_comparer(&MyClass::s));
    // sort by s(), descending
    std::sort(vec.begin(), vec.end(), make_method_comparer<std::greater>(&MyClass::s));
}

How I can use C++ STL Sort for sorting array of object with inheritance

You ought to have tested these functions as you wrote them. The problem is here:

double Shape::getArea(){
    return area;
}

bool sortByArea(const Shape * lhs, const Shape * rhs) { 
    return lhs->getArea() < rhs->getArea(); 
}

You correctly gave sortByArea const pointer arguments, but neglected to make getArea a const function. The compiler is telling you that you are commanding that the code perform an operation that might change the shapes, after you forbade that they be changed.

C++ STL - How does the third argument of the STL sort() work?

To sort a range using std::sort (or any function for that matter), it needs to know how two elements from the range are compared, in order to determine less than (or greater than) relationship.

The Standard Library function std::sort comes in two flavors: one uses operator<, the other uses a compare function/functor. You've used both of them in your code — in particular, the third one in your example uses < and the rest use compare function/functor.

As for which one is the best approach?

Well, it depends. The one which uses operator< is less flexible since it is fixed but requires you less typing as well. Use it when it suffices.

The other one is more flexible as you can pass any compare function and get your elements sorted accordingly. Use it when operator< doesn't suffice. Also, when you choose this flavor, you have other choices as well : the comparer could be a function, a functor, or a lambda — if you use function or functor (defined at namespace level), then you can reuse them; on the other hand, lambda is usually defined in a function scope, so it is not that reusable, unless you define it at namespace scope, in which case it is almost same as function.

Example, suppose you want to sort a vector of int in increasing order:

 std::vector<int>  v{10, 3, 12, -26};
 std::sort(v.begin(), v.end());
 print(v);

Output: -26,3,10,12. So operator< does do the job.

But what if you want the elements sorted considering only magnitude (i.e ignore signs), then you have to use the other flavor:

 std::vector<int>  v{10, 3, 12, -26};
 auto abs_cmp = [](int a, int b) { return std::abs(a) < std::abs(b); };
 std::sort(v.begin(), v.end(), abs_cmp);
 print(v);

Output : 3,10,12,-26. That is the output you would expect in this case.

Hope that helps.

Sorting class members in a template class in C++

When you call container.reserve(3); you increase the capacity of the vector (size of the internal storage), but the vector remains empty. operator[] doesn't insert elements, so when you do this:

container.reserve(3);
container[0] = a; container[1] = b; container[2] = c;

You're accessing some elements that don't actually exist in the vector, the vector is still empty after this.

The method that does what you want is resize(), which actually increases the size of the vector.

The constructor that you call in your testLocally method sets the initial size of the vector, not it's initial capacity, that's why in that method it works as you expect it to work.

---

Related Topics