Matching Standard Library Containers Using Variadic Templates in C++ 2011

From my “Printing Standard Library Sequence and Associative Containers in C++ 2011″ post, let’s discuss the second template:

template < template < typename, typename, typename ... > class C, typename T1, typename T2, typename ... T_PACK >
inline std::ostream & operator << ( std::ostream & o, C< T1, T2, T_PACK ... > const & c ) {
	write( o, c );
	return o;
}

NOTE: This code uses write() as discussed in my last post, “Writing with Iterators in C++ 2011″.

From 14[1] of the C++ 2011 Standard, we have the following:

A template defines a family of classes or functions or an alias for a family of types.

  • template-declaration:
    • template < template-parameter-list > declaration
  • template-parameter-list:
    • template-parameter
    • template-parameter-list , template-parameter

From 14.1[2], there is no semantic difference between class and typename in a template-parameter; however, from 14.1[1], the Standard delineates the following:

The syntax for template-parameters is:

  • template-parameter:
    • type-parameter
    • parameter-declaration
  • type-parameter:
    • class ...opt identifieropt
    • class identifieropt = type-id
    • typename ...opt identifieropt
    • typename identifieropt = type-id
    • template < template-parameter-list > class ...opt identifieropt
    • template < template-parameter-list > class identifieropt = id-expression

So we can use typename everywhere except before the optional identifier in a template template parameter (the last couple of items in the type-parameter listing above) … where we must use class … but we can still use typename in its template-parameter-list (in the inner <>).

Also, notice that all identifiers are optional for type-parameters … even after an ellipsis (...).  Moreover, the second example from 14.3.3[2] of the C++ 2011 Standard includes the following line:

template<template<class ...> class Q> class Y { /* ... */ };

Since typename and class are usually interchangeable, we could swap out the first class for typename in that example … but we would still need to use class for that second instance of class. In other words, we could change the line above to:

template<template<typename ...> class Q> class Y { /* ... */ };

As we’ve previously discussed, a template parameter pack is a template parameter that accepts zero or more template arguments per 14.5.3[1] of the 2011 Standard. If we’d like to ensure that we capture at least two types as template arguments (such as T and A in C< T, A >), then we can just put two typenames in front of a typename ....

So now that we have template parameter packs to go with template template parameters, we have an easy way to describe Standard Library Sequence and Associative Containers … not including std::array. Standard Library Sequence Containers have the form C< T, A >. Standard Library Associative Containers have the form C< K, P, A > for set-related containers and C< K, T, P, A > for map-related containers. Hence, these Sequence and Associative Containers are classes with either 2, 3, or 4 template parameters (some of which contain default template arguments). One way of doing this is just to create a template that matches classes with two or more template parameters:

template < template < typename, typename, typename ... > class C,

Of course, we’re not done … we’d still like the compiler to use template argument deduction (14.8.2) so that we can just use operator << () the same way we always have … without specifying its templates explicitly .. so for a container of the form C< T1, T2, T_PACK ... >, we’d need:

template < template < typename, typename, typename ... > class C, typename T1, typename T2, typename ... T_PACK >

Per 14.5.3[4], a pack expansion consists of a pattern and an ellipsis, the instantiation of which produces zero or more
instantiations of the pattern in a list. Per 14.5.3[5], a parameter pack whose name appears within the pattern of a pack expansion is expanded by that pack … so our second line holds our pack expansion:

inline std::ostream & operator << ( std::ostream & o, C< T1, T2, T_PACK ... > const & c ) {

Now to tie up loose ends.

In order to print std::map, we’ll need to print std::pair … and to get all C++ 2011 up in here, we’ll use std::get, vice the old .first and .second members variables:

template < typename F, typename S >
inline std::ostream & operator << ( std::ostream & o, std::pair< F, S > const & p ) {
	o << "{ " << std::get< 0 >( p ) << ", " << std::get< 1 >( p ) << " }";
	return o;
}

Lastly, as we also mentioned before, std::string is just a typedef for std::basic_string< char, std::char_traits< char >, std::allocator< char > > … so std::string has the exact same form as std::set … which means that our new-fangled variadic template will match std::string just like it matches std::set. While one could argue that std::string is just a container of chars, we definitely didn’t intend for our variadic template to match std::string … and the output of our variadic template for std::string would be “interesting” (i.e. for "abc", we’d get { a, b, c }, vice the more traditional abc … if it could compile). As you might have also guessed, the string header file already has a templated operator << () that prints classes like std::string … so if we throw in one more template that trys to print std::string, then things will get all kinds of ambiguous … and we’ll get compiler errors like:

main.cpp: In function 'void write(std::ostream&, const C&) [with C = std::forward_list<std::basic_string<char> >, std::ostream = std::basic_ostream<char>]':
main.cpp:28:2:   instantiated from 'std::ostream& operator<<(std::ostream&, const C<T1, T2, T_PACK ...>&) [with C = std::forward_list, T1 = std::basic_string<char>, T2 = std::allocator<std::basic_string<char> >, T_PACK = {}, std::ostream = std::basic_ostream<char>]'
main.cpp:52:25:   instantiated from here
main.cpp:18:3: error: ambiguous overload for 'operator<<' in 'std::operator<< [with _Traits = std::char_traits<char>]((* & o), 32) << i.std::_Fwd_list_const_iterator<_Tp>::operator* [with _Tp = std::basic_string<char>, std::_Fwd_list_const_iterator<_Tp>::reference = const std::basic_string<char>&]()'
main.cpp:18:3: note: candidates are:
main.cpp:27:23: note: std::ostream& operator<<(std::ostream&, const C<T1, T2, T_PACK ...>&) [with C = std::basic_string, T1 = char, T2 = std::char_traits<char>, T_PACK = {std::allocator<char>}, std::ostream = std::basic_ostream<char>]
c:\mingw\bin\../lib/gcc/mingw32/4.6.2/include/c++/ostream:581:5: note: std::basic_ostream<_CharT, _Traits>& std::operator<<(std::basic_ostream<_CharT, _Traits>&&, const _Tp&) [with _CharT = char, _Traits = std::char_traits<char>, _Tp = std::basic_string<char>] <near match>
c:\mingw\bin\../lib/gcc/mingw32/4.6.2/include/c++/ostream:581:5: note:   no known conversion for argument 1 from 'std::basic_ostream<char>' to 'std::basic_ostream<char>&&'
c:\mingw\bin\../lib/gcc/mingw32/4.6.2/include/c++/bits/basic_string.h:2693:5: note: std::basic_ostream<_CharT, _Traits>& std::operator<<(std::basic_ostream<_CharT, _Traits>&, const std::basic_string<_CharT, _Traits, _Alloc>&) [with _CharT = char, _Traits = std::char_traits<char>, _Alloc = std::allocator<char>]

Which is … of course … a lot to take in … but there are probably a gagillion more lines like this … just to make things that much more unreadable. What to do?! All we need to do is bypass all this template stuff with a straight, to-the-point function call … no ambiguity … the compiler will always use this operator << () for std::string:

inline std::ostream & operator << ( std::ostream & o, std::string const & s ) {
	auto i = std::begin( s );
	auto end = std::end( s );
	for ( ; i != end; ++i )
		o << *i;
	return o;
}

So … after all that … if we have the following main.cpp:

#include <iostream>
#include <string>
#include <deque>
#include <forward_list>
#include <list>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

template < typename C >
inline void write ( std::ostream & o, C const & c ) {
	auto i = std::begin( c );
	auto end = std::end( c );
	o << '{';
	if ( i != end ) {
		o << ' ' << *i;
		for ( ++i; i != end; ++i )
			o << ", " << *i;
		o << ' ';
	}
	o << '}';
}

template < template < typename, typename, typename ... > class C, typename T1, typename T2, typename ... T_PACK >
inline std::ostream & operator << ( std::ostream & o, C< T1, T2, T_PACK ... > const & c ) {
	write( o, c );
	return o;
}

template < typename F, typename S >
inline std::ostream & operator << ( std::ostream & o, std::pair< F, S > const & p ) {
	o << "{ " << std::get< 0 >( p ) << ", " << std::get< 1 >( p ) << " }";
	return o;
}

inline std::ostream & operator << ( std::ostream & o, std::string const & s ) {
	auto i = std::begin( s );
	auto end = std::end( s );
	for ( ; i != end; ++i )
		o << *i;
	return o;
}

int main () {

	std::deque< int > d = { 1, 2, 3};
	std::cout << "d: " << d << '\n';

	std::forward_list< std::string > fl = { "c", "b", "a" };
	std::cout << "fl: " << fl << '\n';

	std::list< std::string > l = { "a", "b", "c" };
	std::cout << "l: " << l << '\n';

	std::vector< double > v = { 1.1, 2.2, 3.3 };
	std::cout << "v: " << v << '\n';

	std::vector< bool > b = { true, false, true };
	std::cout << "b: " << b << '\n';

	std::map< std::string, int > m = { { "a", 1 }, { "b", 2 }, { "c", 4 }, { "c", 3 } };
	std::cout << "m: " << m << '\n';

	std::multimap< std::string, int > mm = { { "a", 1 }, { "b", 2 }, { "c", 4 }, { "c", 3 } };
	std::cout << "mm: " << mm << '\n';

	std::set< double > s = { 1.1, 2.2, 3.3, 3.3 };
	std::cout << "s: " << s << '\n';

	std::multiset< double > ms = { 1.1, 2.2, 3.3, 3.3 };
	std::cout << "ms: " << ms << '\n';

	std::unordered_map< std::string, int > um = { { "a", 1 }, { "b", 2 }, { "c", 4 }, { "c", 3 } };
	std::cout << "um: " << um << '\n';

	std::unordered_multimap< std::string, int > umm = { { "a", 1 }, { "b", 2 }, { "c", 4 }, { "c", 3 } };
	std::cout << "umm: " << umm << '\n';

	std::unordered_set< double > us = { 1.1, 2.2, 3.3, 3.3 };
	std::cout << "us: " << us << '\n';

	std::unordered_multiset< double > ums = { 1.1, 2.2, 3.3, 3.3 };
	std::cout << "ums: " << ums << '\n';

	return 0;
}

And we executed the following command:

g++ -o main.exe main.cpp -std=c++0x -march=native -O3 -Wall -Wextra -Werror && ./main.exe

Then we would get the following output:

d: { 1, 2, 3 }
fl: { c, b, a }
l: { a, b, c }
v: { 1.1, 2.2, 3.3 }
b: { 1, 0, 1 }
m: { { a, 1 }, { b, 2 }, { c, 4 } }
mm: { { a, 1 }, { b, 2 }, { c, 4 }, { c, 3 } }
s: { 1.1, 2.2, 3.3 }
ms: { 1.1, 2.2, 3.3, 3.3 }
um: { { c, 4 }, { a, 1 }, { b, 2 } }
umm: { { c, 4 }, { c, 3 }, { a, 1 }, { b, 2 } }
us: { 3.3, 2.2, 1.1 }
ums: { 3.3, 3.3, 2.2, 1.1 }

While all this might seem good to go, we’ve already seen a conflict with std::string … so even though it works now, the more complex our classes get, the more likely an ambiguity might pop up unexpectedly. To minimize the debugging that would need to be done, we might want to ditch this variadic-template method of printing in favor of a little more type-ity type. If you haven’t already figured out the unabridged solution, I’ll detail it a few posts from now … after we cover printing the Container Adaptors and std::tuple.

Leave a Reply

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

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="">