Using User Defined Types With STL Associative Containers

Consider the struct:

struct ProductKey
{
	std::string brand;
	std::string model;
	int type;
	int version;
};

Using  it in a  std::set will generate a compile time error.

#include  <set>

int main()
{
	std::set<ProductKey> productSet{
		{ "Best Prod", "M1" , 1, 3 },
		{ "Best Prod", "M2" , 32, 3 },
		{ "Value Prod", "P2" , 32, 3 }
	};
}

binary ‘<‘: no operator found which takes a left-hand operand of type ‘const ProductKey’

std::set internal structure calls for a less functor that given, two ProductKey objects, will determine which should be placed in front of the other in an ordered list.

by default std::set  uses std::less,  as we can see from std::set full declaration (line 4):

   		template<

  		class Key,
  		class Compare = std::less<Key>,
  		class Allocator = std::allocator<Key>

  		> class set;

The default less operator employs the ‘<’ operator to compare the  two keys:

template <class T> struct less {
  bool operator() (const T& x, const T& y) const {return x<y;}
  };

As our ProductKey  do not have  a  ‘<’  operator   defined for it, compilation fails.

One possible solution is  to overload the ‘< ‘  operator for the ProductKey   user type. Once it is defined, the default  std::less implementation  can  use this operator  during compilation.  However,  this will actually be a case of doing  too much.   The only consumer of this new ‘<’  operator will be the associative container. There is no need to expose the new operator to any other component which includes  ProductKey   (if nobody needs it don’t implement it!).  It will be more prudent to do the  minimum needed and simply overload the less functor instead.

defining it in the std namespace will enable us to plug our new less functor into the default std::set declaration:

template<> struct std::less<ProductKey>
	{
		bool operator() (const ProductKey& prod1, const ProductKey& prod2) const
		{
			if (prod1.brand != prod2.brand)
			{
				return prod1.brand < prod2.brand;
			}

			if (prod1.model != prod2.model)
			{
				return prod1.model < prod2.model;
			}

			if (prod1.type != prod2.type)
			{
				return prod1.type < prod2.type;
			}

			return prod1.version < prod2.version;
		}
	};

the empty <>  after the template keyword  in line 1 indicate that this is a specialized template.  That is , when the compiler tries to instantiate the less<T> functor  where T is  ProductKey  it will consider our template definition instead of the more  general  std::less functor defined in the standard library.

We can improve the less  functor’s implementation  by  using  std::tie. This function, included in <tuple>,   creates a tuple out  of  the values supplied to it ,  Since ‘< ‘  is defined for the tuple type  by the standard library ,  our std::less functor can be rewritten as

template<> struct std::less<ProductKey>
{
	bool operator() (const ProductKey& prod1, const ProductKey& prod2) const
	{
		return (std::tie(prod1.brand, prod1.model, prod1.type, prod1.version) <
		std::tie(prod2.brand, prod2.model, prod2.type, prod2.version));
	}
};

which is no only more readable,  It’s  also less error prone and not as boring to write!

So the complete example is:


#include <string>
#include <set>
#include <tuple>


struct ProductKey
{
	std::string brand;
	std::string model;
	int type;
	int version;
};

template<> struct std::less<ProductKey>
{
	bool operator() (const ProductKey& prod1, const ProductKey& prod2) const
	{
		return (std::tie(prod1.brand, prod1.model, prod1.type, prod1.version) < 
			std::tie(prod2.brand, prod2.model, prod2.type, prod2.version));
	}
};

int main()
{
	std::set<ProductKey> productSet{
		{ "Best Prod", "M1" , 1, 3 },
		{ "Best Prod", "M2" , 32, 3 },
		{ "Value Prod", "P2" , 32, 3 }
	};
}
Conclusion

Plugging your code into STL’s containers and algorithms,  Enables  you to  make  your code more robust and maintainable with less effort.  Most important it can make it more fun to write.

2 thoughts on “Using User Defined Types With STL Associative Containers”

Leave a Reply

Your email address will not be published. Required fields are marked *