An Introduction For How to Insert your Own Custom Objects Inside a std:::set

• Download source - 1.27 KB

Introduction

This article is about how you can insert a bunch of custom defined object (those which are comparable by some means of-course) into an associative container, specially set and multiset.

Background

Those who are familiar with STL know the code definition of a set and multiset looks like this:

namespace std{
    template <class T,
    class Compare = less<T>,
    class Allocator = allocator<T> > class set;
    template <class T,
    class Compare = less<T>,
    class Allocator = allocator<T> > class multiset;
}

The difference between set and multiset is, multiset allows duplicates, but sets don't. More importantly, both set and multiset maintain an order, in which they store the elements. To be brief, both set and multiset use a Red-Black Tree (an advanced form of balance binary tree) to store their elements, so you need to have an order in which the elements will get inserted.

The elements of a set of multiset may have any type T that is assignable, copyable and comparable according to some sorting criterion. The optional second argument holds the stands for this comparison based operation. If a special sorting criterion is not passed while declaring a set and/or multiset, the default std::less<> is used by the container.

So, now if you need to push a bunch of custom objects (objects of your own class), how can you design your class so that they can be contained in set/multiset.

As I said earlier: "The elements of set/multiset can be of any type T, that is:

• Assignable (that is you have to have an overloaded assignment operator, or default assignment operator - if it is sufficient enough to do the job)
• Copyable (that is you have to have an copy constructor, or default copy constructor - if it is sufficient enough to do the job) 
• Comparable: This is the most important part. You have to put some kind of decision making branch which will compare two custom defined objects based on some comparison criteria. Here you have two choices:

1. You can overload a "<" operator inside your class itself.
2. You can create a functor to do the comparison job.

Another important thing is, the sorting criterion must define "String Weak Ordering". Strict Weak Ordering is defined by following three properties:

1. It has to be anti-symmetric, aka if x<y is true then y<x is false.
2. It has to be transitive: aka, if x<y is true and y<z is true then x<z is also true.
3. It has to be irreflexive: aka x<x is always false.

Using the Code

If you just unzip the source, you'll find three source files named:

1. MyType.hpp - This class defines the custom defined type along with overloaded < operator. 
2. MyComparator.hpp - This class defines a custom define functor which does the comparison job.
3. newmain.cpp - The main file.

First let us analyze the MyType.hpp file:

/* 
 * File:   MyType.hpp
 * Author: Tushar
 *
 * Created on May 6, 2009, 5:10 PM
 */

#ifndef _MYTYPE_HPP
#define	_MYTYPE_HPP

namespace Tushar{
template <typename T>
class MyType{
private:
    T value;
public:
    MyType(){
        value = T();
    }
    MyType(T val):value(val){
    }
    MyType(const MyType& other){
        value = other.value;
    }
    MyType& operator=(MyType const& other){
        if((void*)this == (void*)&other)
            return *this;
        value = other.getValue();
        return *this;
    }

    bool operator< (const MyType& other) const{
        return value<other.getValue();
    }
    T getValue() const{
        return value;
    }
};
}

#endif	/* _MYTYPE_HPP */

Here, everything is very much simple. Just go through it.

Now, let's have a look at MyComparator.hpp.

/* 
 * File:   MyComparator.hpp
 * Author: Tushar
 *
 * Created on May 6, 2009, 5:11 PM
 */

#ifndef _MYCOMPARATOR_HPP
#define    _MYCOMPARATOR_HPP
#include "MyType.hpp"
template <typename T>
class MyComparator{
public:
    bool operator() (const T& t1, const T& t2) const{
        return t1.getValue()<t2.getValue();
    }
};
#endif    /* _MYCOMPARATOR_HPP */

Here the idea is to overload the () operator (it's a true functor) which takes two templated args (we'll pass two custom defined objects actually), it compares the two objects by using the < operator.

Now let's see the driver file:

#include <iostream>
#include <set>
#include "myType.hpp"
#include "MyComparator.hpp"

int main()
{  
    Tushar::MyType<int> m1(100);
    Tushar::MyType<int> m2(200);       
    typedef std::set<Tushar::MyType<int>, MyComparator<Tushar::MyType<int> > > CustomSet;
    CustomSet mySet;
    mySet.insert(m1);
    mySet.insert(m2);
    CustomSet::const_iterator it(mySet.begin());
    for(;it!=mySet.end();++it){
        std::cout<<"Element is: "<<it->getValue()<<std::endl;
    }
    return 0;
}

Here the custom typedef line is the most important one, just look at the declaration carefully, here we are declaring a std::set which will hold our custom types and will compare based on the functors we have. Again, MyComparator declaration inside std::set declaration also needs to hold the type definition of our customized class, since our functor is also templated.

 Of course, you can also use directly...

typedef std::set<Tushar::MyType<int> > CustomSet;

... and the program will work fine.

Still, it is advisable to use the Functor.

History

• 6^th May, 2009: Initial post