Printing Container Adaptors in C++ 2011

By Joshua Burkholder May 5, 2012 C++, C++ 2011, C++ Containers, C++ Templates, Generic Programming No Comments

From my “Printing Standard Library Sequence and Associative Containers in C++ 2011” post, let’s discuss how to print the Container Adaptors (i.e. queues, priority queues, and stacks):


template < template < typename, typename, typename ... > class A, typename T, typename C, typename ... P_PACK >
struct std__adaptor : public A< T, C, P_PACK ... > {
    friend inline std::ostream & operator << ( std::ostream & o, std__adaptor< A, T, C, P_PACK ... > const & a ) {
        o << a.A< T, C, P_PACK ... >::c;
        return o;
    }
};

template < typename T, typename C >
inline std::ostream & operator << ( std::ostream & o, std::queue< T, C > const & q ) {
    o << static_cast< std__adaptor< std::queue, T, C > const & >( q );
    return o;
}

template < typename T, typename C, typename P >
inline std::ostream & operator << ( std::ostream & o, std::priority_queue< T, C, P > const & p ) {
    o << static_cast< std__adaptor< std::priority_queue, T, C, P > const & >( p );
    return o;
}

template < typename T, typename C >
inline std::ostream & operator << ( std::ostream & o, std::stack< T, C > const & s ) {
    o << static_cast< std__adaptor< std::stack, T, C > const & >( s );
    return o;
}

Container Adaptors are located in 23.6[container.adaptors] of the C++ 2011 Standard. Currently, there are only three Container Adaptors in C++: std::queue, std::priority_queue, and std::stack. When we look at the definition of std::queue in 23.6.3.1[queue.defn]/1 of the Standard, we see the following:


namespace std {
  template <class T, class Container = deque<T> >
  class queue {
  public:
    typedef typename Container::value_type      value_type;
    typedef typename Container::reference       reference;
    typedef typename Container::const_reference const_reference;
    typedef typename Container::size_type       size_type;
    typedef Container                           container_type;
  protected:
    Container c;
.
.
.

The definition of std::priority_queue in 23.6.4[priority.queue]/1 and std::stack in 23.6.5.2[stack.defn] also contain this same member variable:


protected:
  Container c;

As we continue to look at these definitions, we notice the lack of iterators … which shouldn’t be too shocking since we’re talking about queues and stacks here … it wouldn’t make too much sense if we could easily get at the stuff in the middle of these containers. But that’s exactly what we need to do if we want to print them. There are a bunch of different ways to do this, but I led with that protected member variable, so let’s see if this Container c can get us where we need to go.

WARNING: We are about to rely on a C++ 2011 Standard Library that implements the Container Adaptors portion of the C++ 2011 Standard __exactly__. If your C++ 2011 Standard Library does not implement Container Adaptors using the class definitions in 23.6[container.adaptors] of the C++ 2011 Standard, then that protected Container c may not exist or may be slightly different (i.e. c may be named something like m_c or _c or some other non-standard nonsense) … and none of this Container Adaptor printing code should work and (hopefully) won’t even compile. Note: Container Adaptors in g++ 4.6.2 conform exactly to the C++ 2011 Standard … hopefully, that conformance will continue.

So how can we take advantage of the protected Container c member variable that all of these Container Adaptors share?

Simply, all we need to do to print any of the current Container Adaptors is to print that Container Adaptor’s protected Container c member variable. Okay … so how do we do that (esp. since that member variable is protected)?

From 11[class.access]/1 of the C++ 2011 Standard, a member of a class can be:

private; …
protected; that is, its name can be used only by members and friends of the class in which it is declared, by classes derived from that class, and by their friends (see 11.4).
public; …

In 11.4[class.protected] (Protected member access), the last half reads:

As described earlier, access to a protected member is granted because the reference occurs in a friend or member of some class C. If the access is to form a pointer to member (5.3.1), the nested-name-specifier shall denote C or a class derived from C. All other accesses involve a (possibly implicit) object expression (5.2.5). In this case, the class of the object expression shall be C or a class derived from C.

So let’s see if we can use that c member variable (i.e. the name of the protected Container) through a reference to a struct derived from that Container Adaptor class in a friend function. In other words, let’s use this (from the code above):


template < template < typename, typename, typename ... > class A, typename T, typename C, typename ... P_PACK >
struct std__adaptor : public A< T, C, P_PACK ... > {
    friend inline std::ostream & operator << ( std::ostream & o, std__adaptor< A, T, C, P_PACK ... > const & a ) {
        o << a.A< T, C, P_PACK ... >::c;
        return o;
    }
};

So the friend function is operator <<, a is the reference to a constant struct derived from that Container Adaptor class through which the member variable c can be used (i.e. a.A< T, C, P_PACK ... >::c), and the struct is std__adaptor which derives from the Container Adaptor that is relatively obfuscated in the template A< T, C, P_PACK ... > … where A stands for the Container Adaptor (i.e. std::queue, std::priority_queue, or std::stack), T stands for type of elements held in that Container Adaptor, C stands for the container that the Container Adaptor uses internally, and P_PACK is the parameter pack that captures zero or more additional parameters that the Container Adaptor may have.

Okay … but why does this work? I mean, we want to print std::queue, std::priority_queue, and std::stack, not std__adaptor … right? True … and that’s why the other code exists (also from above):


template < typename T, typename C >
inline std::ostream & operator << ( std::ostream & o, std::queue< T, C > const & q ) {
    o << static_cast< std__adaptor< std::queue, T, C > const & >( q );
    return o;
}

template < typename T, typename C, typename P >
inline std::ostream & operator << ( std::ostream & o, std::priority_queue< T, C, P > const & p ) {
    o << static_cast< std__adaptor< std::priority_queue, T, C, P > const & >( p );
    return o;
}

template < typename T, typename C >
inline std::ostream & operator << ( std::ostream & o, std::stack< T, C > const & s ) {
    o << static_cast< std__adaptor< std::stack, T, C > const & >( s );
    return o;
}

This code forces a reference to a constant std::queue, std::priority_queue, or std::stack to be a reference to a constant std__adaptor whenever we print these Container Adaptors … and then we print that reference to a std__adaptor.

Okay … but why does that work?

The first half of 5.2.9[expr.static.cast]/2 of the C++ 2011 Standard reads:

An lvalue of type “cv1 B,” where B is a class type, can be cast to type “reference to cv2 D,” where D is a class derived (Clause 10) from B, if a valid standard conversion from “pointer to D” to “pointer to B” exists (4.10), cv2 is the same cv-qualification as, or greater cv-qualification than, cv1, and B is neither a virtual base class of D nor a base class of a virtual base class of D. The result has type “cv2 D.”

Moreover, the Example from 5.2.9[expr.static.cast]/2 contains the following:


struct B { };
struct D : public B { };
D d;
B &br = d;
 
static_cast<D&>(br); // produces lvalue to the original d object

In our code, B is the Container Adaptor (i.e. std::queue, std::priority_queue, or std::stack) and D is our std__adaptor. Although we haven’t previously constructed a std__adaptor, we are casting from a reference to a constant Container Adaptor (i.e. the base class) to a reference to a constant std__adaptor (i.e. the derived class), we are maintaining our cv-qualification, and we aren’t dealing with virtual base classes, so all of the following casts are good to go:


// q is a std::queue< T, C > const &
static_cast< std__adaptor< std::queue, T, C > const & >( q );

// p is a std::priority_queue< T, C, P > const &
static_cast< std__adaptor< std::priority_queue, T, C, P > const & >( p );

// s is a std::stack< T, C > const &
static_cast< std__adaptor< std::stack, T, C > const & >( s );

Since all of these work, we are left with a reference to a constant std__adaptor … which just happens to have access to Container c through its base class. Since std__adaptor has access to Container c, so do all the friends of std__adaptor, namely operator <<. Any friend of std__adaptor can access Container c using either:


a.A< T, C, P_PACK ... >::c

… or, more succinctly, …

a.c

Once we’re allowed to drill down to Container c, we print that container the same way we’ve printed all the other containers. So, if we have the following main.cpp:


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

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 T, size_t N >
inline std::ostream & operator << ( std::ostream & o, std::array< T, N > const & a ) {
    o << '{';
    write( o, a );
    o << '}';
    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;
}
 
template < template < typename, typename, typename ... > class A, typename T, typename C, typename ... P_PACK >
struct std__adaptor : public A< T, C, P_PACK ... > {
    friend inline std::ostream & operator << ( std::ostream & o, std__adaptor< A, T, C, P_PACK ... > const & a ) {
        o << a.c;
        return o;
    }
};
 
 
template < typename T, typename C >
inline std::ostream & operator << ( std::ostream & o, std::queue< T, C > const & q ) {
    o << static_cast< std__adaptor< std::queue, T, C > const & >( q );
    return o;
}
 
template < typename T, typename C, typename P >
inline std::ostream & operator << ( std::ostream & o, std::priority_queue< T, C, P > const & p ) {
    o << static_cast< std__adaptor< std::priority_queue, T, C, P > const & >( p );
    return o;
}
 
template < typename T, typename C >
inline std::ostream & operator << ( std::ostream & o, std::stack< T, C > const & s ) {
    o << static_cast< std__adaptor< std::stack, T, C > const & >( s );
    return o;
}
 
int main () {
    
    std::queue< std::vector< int > > q;
    q.push( { 1 } );
    q.push( { 2, 2 } );
    q.push( { 3, 3, 3 } );
    std::cout << "q: " << q << '\n';
    
    std::priority_queue< std::list< double > > pq;
    pq.push( { 1.1 } );
    pq.push( { 2.2, 2.2 } );
    pq.push( { 3.3, 3.3, 3.3 } );
    std::cout << "pq: " << pq << '\n';
 
    std::stack< std::multimap< std::string, int > > s;
    s.push( { { "one", 1 } } );
    s.push( { { "two", 2 }, { "two", 22 } } );
    s.push( { { "three", 3 }, { "three", 33 }, { "three", 333 } } );
    std::cout << "s: " << s << '\n';
 
    return 0;
}

And we executed the following command:


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

Then we would get the following output:


q: { { 1 }, { 2, 2 }, { 3, 3, 3 } }
pq: { { 3.3, 3.3, 3.3 }, { 1.1 }, { 2.2, 2.2 } }
s: { { { one, 1 } }, { { two, 2 }, { two, 22 } }, { { three, 3 }, { three, 33 }, { three, 333 } } }

As mentioned before, this only works if the Standard Library used by our C++ 2011 compiler conforms to the C++ 2011 Standard … i.e. they copied & pasted the definitions of std::queue, std::priority_queue, std::stack straight from the Standard into their Standard Library so that all of these Container Adaptors have a protected member variable named c that is a Container … just like the C++ 2011 Standard says they should.

In my next post, I’ll detail how to print std::tuple.

Leave a Reply Cancel reply