changing the sorting criteria/algorithm of STL containers -map , multimap , set ,etc


In STL associative containers-map,multimap,etc-the elements stored in them are sorted in the ascending order of the key or if the key type is a string the elements are sorted in the lexicographical manner.This automatic sorting of the elements is due to the default less<int> criteria/algorithm used by the containers.

The STL associative containers however,are versatile enough to allow the programmers to implement some other sorting criteria of their own if the need ever arises.On top of this it can handle a criteria having many sorting criteria allowing programmers to opt for one or the other and making the implementation more resourceful and versatile.

There are two ways to sort the elements of all STL containers.

i)Changing criteria as type.
ii)Using criteria as a function.

The first method is mainly use for associative containers and the second method is mainly used for sequence containers-excludes forward_list and list containers.And note you cannot use the second method for sorting the elements of associative containers and the first method cannot be used for sorting the sequence containers due to some reasons which is describe below.

The discussion of the two methods is given below.

Lin: Types of STL containers.

Changing criteria as type

When we say “criteria as a type” we are referring to the class or structure that actually performs the sorting of the elements.Such class definition can vary from one member function to many member functions.The simplest one consists of only one operator() member function.

In STL associative containers if you look at the template class declaration the third argument type is the type of the sorting criteria used by the container.For instance in map template class declaration as shown below.

template<typename Key , typename T , typename Compare= lesse<Key> ,
typename Allocator= allocatore<paire< const Key , Te>e> e>
class map ;

The third type typename Compare= less<Key>,the lesse<Key> is the (default) criteria of the map container.If you want to use your own criteria you will pass the name of the criteria(class) as the third argument in the map or any other container object declaration.

Defining our own criteria

Defining a criteria is easy! it is same as defining a class.Say you want to sort the elements in a descending order instead of the default ascending order,the class can be defined as shown below.

class DescendingOrder
{
public:
 bool operator()(const int arg1,const int arg2)
 {
 return arg1>arg2 ; //uses greater than operator
 }
};

The above criteria consists of only one function operator() ,also I have mentioned earlier a simplest criteria type definition can have only one member function,so we just made the simplest criteria.

The next step is using the criteria in our program.One thing you should remember is if you look at the argument type of the operator() function,it is an int type so use this criteria for containers having it’s key as int or char type.If the key type differs change the argument type accordingly.In the code below the key type of map object is an int type.

Note include the <map>header file.

map<int,string> mp{{ 23, “Twenty-three”} , { 9 , “nine”} , { 14 , “1414”} , { 78 ,”7878″ }}; ///this uses the default criteria

for(auto elem:mp)
{
cout<< elem.first << ”   ” << elem.second << endl;
}

cout<< endl ;

map<int,string , DescendingOrder> mp1{{ 23, “Twenty-three”} , { 9 , “nine”} , { 14 , “1414”} , { 78 ,”7878″ }};

for(auto elem:mp1)
{
cout<< elem.first << ”   ” << elem.second << endl;
}

Output

9 nine
14 1414
23 Twenty-three
78 7878

78 7878
23 Twenty-three
14 1414
9 nine

You will notice that the first container which uses the default criteria elements are sorted in ascending order but the container using DescendingOrder criteria sorts it’s elements in descending order;just exactly what we wanted.

I am sure looking at this program has convinced you that incorporating our own criteria into the map container is pretty easy.You can try out some other criteria of your own to have a firm grasping of the concept,say a criteria for sorting string without any case sensitivity.

Objects with different sorting criteria should not be intermingled

One of the most important points you should remember while using your own criteria is you cannot intermingle objects using the different sorting criteria.By this I mean you cannot assign one object to another or perform copy assignment or any such similar operations between objects implementing different criteria.If you try to do so it is ultimately and error.I don’t think I even need to explain why?.

map<int, char ,DescendingOrder> mp1 {{ 2 ,’2′} , { 4 , ‘4’}} ;

map<int,char> m(mp1) ; //error

map<int ,char ,DescendingOrder> mp2(mp1) ; //work fine


 


Stop wasting time,earn money($$$) from your website-Join Now!

A criteria having two or more criteria

The DescendingOrder criteria which we have defined above does only one thing-sort elements in descending order.But sometimes it is not impossible that our situation may demands for more sorting criteria or to make our program more versatile we may want to add more criteria.In such case instead of defining a class for each criteria we can include many criteria we want in just one class and with little tweaking we can make our program choose the desired criteria when needed.

Let us take the criteria we have defined before- DescendingOrder criteria.And,let us modify this criteria to also support sorting of elements in ascending order-let us also give our class a different name to suit the criteria say AscendingDescendingOrder.The modification involve is easy and needs little editing of the code.In the DescendingOrder criteria we will add a const int data member.This member value will either be 1 or 0.If it is 0 the ascending sorting criteria will be chosen if 1 the descending sorting criteria is chosen.By default the ascending sorting criteria is chosen.The class definition is shown below

class AscendingDescendingOrder
{
const int order;

public:
AscendingDescendingOrder(int ord=0):order(ord) { }

bool operator()(const int arg1,const int arg2)
{
//Sorts in ascending order
if(order==0)
{
 return arg1<arg2 ;
}
else //sorts in descending order
 return arg1>arg2;
}

~AscendingDescendingOrder =default ;
};

The class is simple and note if you want to sort the elements in descending order you must pass 1 to the class constructor first.A code example is given below.

Include the <map> header file.

map< int,char,AscendingDescendingOrder >mAs{{90 , “()”} , { 67 , “^&”} , { 77 , “&&” }}; //choose the ascending order sorting

for(auto elem:mAs)
{
cout<< elem.first << ”   ” << elem.second << endl ;
}

cout<< endl;

map< int,char,AscendingDescendingOrder > mDs(1) ; //choose the descending order sorting

mDs.insert({90 , “()”} );
mDs.insert({67 , “^&”} );
mDs.insert({77 , “&&”} );

for(auto elem:mDs)
{
cout<< elem.first << ”   ” << elem.second << endl;
}

Output

67 ^&
77 &&
90 ()

90 ()
77 &&
67 ^&

By passing 1 to constructor we are making the compiler know what sorting criteria we want to use for that container,if we hadn’t passed the value the default ascending criteria would have been implemented.

Link:map::insert function






Using criteria as a function

When we want to sort the elements of the sequence containers-excludes list and forward_list and associative and unordered containers because they they provide no random access iterators which is require for this method- and implement our own criteria we will use the function sort() provided in the header file <algorithm>.

The sort() accept three arguments ,the third is optional and it signify the criteria you want to use for sorting the elements.If the third argument is not provided it uses the default criteria which sorts the element in ascending order.The first and second is an iterator pointing to the beginning and one past the end of the elements in the container.In our case we will pass our criteria as the third argument and it will sort the elements in descending order.

Note include <vector> and <algorithm> headers file.

//defining our own criteria function
bool criteria(const int arg1, const int arg2)
{
return arg1>arg2
}

int main()
{
vector<int> vec{ 12 ,89 , 0 , 34 , 9 };

sort(vec.begin() , vec.end() ); //sorts elements in ascending order

for(auto elem:vec)
{
cout<< elem << ” ” ;
}

cout<< endl ;

sort(vec.begin() ,vec.end() , criteria); //sorts elements in descending order

for(auto elem:vec)
{
cout<< elem << ” ” ;
}
cin.get();
return 0;
}

Output

0 9 12 34 89

89 34 12 9 0

Note only function criteria is applicable with the sort function also the function name cannot be used as a type so passing function name as a template argument is just plain wrong.