Tech Off Thread

17 posts

Forum Read Only

This forum has been made read only by the site admins. No new threads or comments can be added.

Templated STL container pretty printer

Back to Forum: Tech Off
  • User profile image
    KerrekSB

    [Preface: I just discovered and watched STL's series "STL" and "Advanced STL". In response to STL#2's homework question to create a template to erase predicated elements from a container, I'd like to post a similar "homework" question.]

    Task: Write a templated solution that will pretty-print the contents of any STL container, or more generally anything that supports begin/end iterators.

    I originally posted this question on StackOverflow (http://stackoverflow.com/questions/4850473/pretty-print-c-stl-containers), but looking back at it I'm still not happy with any of the proposed solutions.

    Synopsis: Given something like std::CONTAINER x, I want to write "std::cout << x;" and get something like "{1, 5, -3, 12}" (with customizable delimiters), but I don't want to have to change the code to accomodate new containers -- I'd like a single piece of code that will work for ALL containers that have begin/end.

    Any suggestions (also to the original SO page) would be most welcome!

  • User profile image
    Sven Groot

    There's the lazy solution:

    std::vector<int> v;
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(cout, ", "));

    But that has the problem of printing an extra comma at the end.

    More generically, you can do:

    template<typename T>
    ostream& write_container(ostream &s, const T &container)
    {
        bool first = true;
        cout << "{ ";
        for( typename T::const_iterator it = container.begin(); it != container.end(); ++it )
        {
            if( first )
                first = false;
            else
                cout << ", ";
            cout << *it;
        }
        cout << " }";
        return s;
    }

    However, you cannot overload operator<< to do this. Since containers have no common base class, the only way to do this is using templates, and the above template declaration matches basically any type. Doing the above with operator<< would make operator<< ambiguous for any type with its own operator<<, and produce some seriously weird errors.

    If you insist on overloading operator<<, I think the solution using boost::enable_if giving on SO is just about the best you can do.

  • User profile image
    KerrekSB

    I see -- OK, overloading << isn't necessary, as long as I can say something like "std::cout << "My vector is " << PrintContainer(vec) << ".\n" without having to touch the definition of PrintContainer in the future.

  • User profile image
    Sven Groot

    @KerrekSB: That's the other solution given on SO, though as one of the comments points out, it won't work for nested collections.

  • User profile image
    Sven Groot

    I've been thinking a bit more about this and came up with the following:

    #include <iostream>
    #include <iterator>
    #include <type_traits>
    #include <vector>
    #include <algorithm>
    
    // This works similar to ostream_iterator, but doesn't print a delimiter after the final item
    template<typename T, typename TChar = char, typename TCharTraits = std::char_traits<TChar> >
    class pretty_ostream_iterator : public std::iterator<std::output_iterator_tag, void, void, void, void>
    {
    public:
        typedef TChar char_type;
        typedef TCharTraits traits_type;
        typedef std::basic_ostream<TChar, TCharTraits> ostream_type;
    
        pretty_ostream_iterator(ostream_type &stream, const char_type *delim = NULL)
            : _stream(&stream), _delim(delim), _insertDelim(false)
        {
        }
    
        pretty_ostream_iterator<T, TChar, TCharTraits>& operator=(const T &value)
        {
            if( _delim != NULL )
            {
                // Don't insert a delimiter if this is the first time the function is called
                if( _insertDelim )
                    (*_stream) << _delim;
                else
                    _insertDelim = true;
            }
            (*_stream) << value;
            return *this;
        }
    
        pretty_ostream_iterator<T, TChar, TCharTraits>& operator*()
        {
            return *this;
        }
    
        pretty_ostream_iterator<T, TChar, TCharTraits>& operator++()
        {
            return *this;
        }
    
        pretty_ostream_iterator<T, TChar, TCharTraits>& operator++(int)
        {
            return *this;
        }
    private:
        ostream_type *_stream;
        const char_type *_delim;
        bool _insertDelim;
    };
    
    #if _MSC_VER >= 1400
    
    // Declare pretty_ostream_iterator as checked
    template<typename T, typename TChar, typename TCharTraits>
    struct std::_Is_checked_helper<pretty_ostream_iterator<T, TChar, TCharTraits> > : public std::tr1::true_type
    {
    };
    
    #endif // _MSC_VER >= 1400
    
    namespace std
    {
        // Pre-declarations of container types so we don't actually have to include the relevant headers if not needed, speeding up compilation time.
        template<typename T, typename TAllocator> class vector;
        template<typename T, typename TAllocator> class list;
        template<typename T, typename TTraits, typename TAllocator> class set;
        template<typename TKey, typename TValue, typename TTraits, typename TAllocator> class map;
    }
    
    // Basic is_container template; specialize to derive from std::true_type for all desired container types
    template<typename T> struct is_container : public std::false_type { };
    
    // Mark vector as a container
    template<typename T, typename TAllocator> struct is_container<std::vector<T, TAllocator> > : public std::true_type { };
    
    // Mark list as a container
    template<typename T, typename TAllocator> struct is_container<std::list<T, TAllocator> > : public std::true_type { };
    
    // Mark set as a container
    template<typename T, typename TTraits, typename TAllocator> struct is_container<std::set<T, TTraits, TAllocator> > : public std::true_type { };
    
    // Mark map as a container
    template<typename TKey, typename TValue, typename TTraits, typename TAllocator> struct is_container<std::map<TKey, TValue, TTraits, TAllocator> > : public std::true_type { };
    
    // Holds the delimiter values for a specific character type
    template<typename TChar>
    struct delimiters_values
    {
        typedef TChar char_type;
        const TChar *prefix;
        const TChar *delimiter;
        const TChar *postfix;
    };
    
    // Defines the delimiter values for a specific container and character type (default values in container_delimiters.h)
    template<typename T, typename TChar>
    struct delimiters
    {
        static const delimiters_values<TChar> values; 
    };
    
    // Default delimiters
    template<typename T> struct delimiters<T, char> { static const delimiters_values<char> values; };
    template<typename T> const delimiters_values<char> delimiters<T, char>::values = { "{ ", ", ", " }" };
    template<typename T> struct delimiters<T, wchar_t> { static const delimiters_values<wchar_t> values; };
    template<typename T> const delimiters_values<wchar_t> delimiters<T, wchar_t>::values = { L"{ ", L", ", L" }" };
    
    // Delimiters for set
    template<typename T, typename TTraits, typename TAllocator> struct delimiters<std::set<T, TTraits, TAllocator>, char> { static const delimiters_values<char> values; };
    template<typename T, typename TTraits, typename TAllocator> const delimiters_values<char> delimiters<std::set<T, TTraits, TAllocator>, char>::values = { "[ ", ", ", " ]" };
    template<typename T, typename TTraits, typename TAllocator> struct delimiters<std::set<T, TTraits, TAllocator>, wchar_t> { static const delimiters_values<wchar_t> values; };
    template<typename T, typename TTraits, typename TAllocator> const delimiters_values<wchar_t> delimiters<std::set<T, TTraits, TAllocator>, wchar_t>::values = { L"[ ", L", ", L" ]" };
    
    // Delimiters for pair
    template<typename T1, typename T2> struct delimiters<std::pair<T1, T2>, char> { static const delimiters_values<char> values; };
    template<typename T1, typename T2> const delimiters_values<char> delimiters<std::pair<T1, T2>, char>::values = { "(", ", ", ")" };
    template<typename T1, typename T2> struct delimiters<std::pair<T1, T2>, wchar_t> { static const delimiters_values<wchar_t> values; };
    template<typename T1, typename T2> const delimiters_values<wchar_t> delimiters<std::pair<T1, T2>, wchar_t>::values = { L"(", L", ", L")" };
    
    // Functor to print containers. You can use this directly if you want to specificy a non-default delimiters type.
    template<typename T, typename TChar = char, typename TCharTraits = std::char_traits<TChar>, typename TDelimiters = delimiters<T, TChar> >
    struct print_container_helper
    {
        typedef TChar char_type;
        typedef TDelimiters delimiters_type;
        typedef std::basic_ostream<TChar, TCharTraits>& ostream_type;
    
        print_container_helper(const T &container)
            : _container(&container)
        {
        }
    
        void operator()(ostream_type &stream) const
        {
            if( delimiters_type::values.prefix != NULL )
                stream << delimiters_type::values.prefix;
            std::copy(_container->begin(), _container->end(), pretty_ostream_iterator<typename T::value_type, TChar, TCharTraits>(stream, delimiters_type::values.delimiter));
            if( delimiters_type::values.postfix != NULL )
                stream << delimiters_type::values.postfix;
        }
    private:
        const T *_container;
    };
    
    // Prints a print_container_helper to the specified stream.
    template<typename T, typename TChar, typename TCharTraits, typename TDelimiters>
    std::basic_ostream<TChar, TCharTraits>& operator<<(std::basic_ostream<TChar, TCharTraits> &stream, const print_container_helper<T, TChar, TDelimiters> &helper)
    {
        helper(stream);
        return stream;
    }
    
    // Prints a container to the stream using default delimiters
    template<typename T, typename TChar, typename TCharTraits>
    typename std::enable_if<is_container<T>::value, std::basic_ostream<TChar, TCharTraits>&>::type
        operator<<(std::basic_ostream<TChar, TCharTraits> &stream, const T &container)
    {
        stream << print_container_helper<T, TChar, TCharTraits>(container);
        return stream;
    }
    
    // Prints a pair to the stream using delimiters from delimiters<std::pair<T1, T2>>.
    template<typename T1, typename T2, typename TChar, typename TCharTraits>
    std::basic_ostream<TChar, TCharTraits>& operator<<(std::basic_ostream<TChar, TCharTraits> &stream, const std::pair<T1, T2> &value)
    {
        if( delimiters<std::pair<T1, T2>, TChar>::values.prefix != NULL )
            stream << delimiters<std::pair<T1, T2>, TChar>::values.prefix;
    
        stream << value.first;
    
        if( delimiters<std::pair<T1, T2>, TChar>::values.delimiter != NULL )
            stream << delimiters<std::pair<T1, T2>, TChar>::values.delimiter;
    
        stream << value.second;
    
        if( delimiters<std::pair<T1, T2>, TChar>::values.postfix != NULL )
            stream << delimiters<std::pair<T1, T2>, TChar>::values.postfix;
        return stream;    
    }
    
    struct fibonacci
    {
        fibonacci() : f1(0), f2(1) { }
        int operator()()
        {
            int r = f1 + f2;
            f1 = f2;
            f2 = r;
            return f1;
        }
    private:
        int f1;
        int f2;
    };
    
    int main()
    {
        std::vector<int> v;
        std::generate_n(std::back_inserter(v), 10, fibonacci());
    
        std::cout << v << std::endl;
    
        // Example of using pretty_ostream_iterator directly
        std::generate_n(pretty_ostream_iterator<int>(std::cout, ";"), 20, fibonacci());
        std::cout << std::endl;
    }

    This version is pretty similar to Marcelo's version on SO, but it has a couple of differences.

    Most obviously, it defines and uses a pretty_ostream_iterator that works similar to the regular ostream_iterator, but doesn't print a trailing delimiter. This means that the main printing implementation can use std::copy, which can have an advantage in VC2005 and up. They use checked iterators, and that means that if you loop over the range yourself you'll be doing a bounds check on every iteration. Algorithms like std::copy will often do a single check to see if begin and end are in range, and then use unchecked iterators for the actual loop.

    Of course, pretty_ostream_iterator is also reusable if you want to do more customized formatting of a container.

    There's also a helper functor which you can use to specify a non-standard delimiters type (though unfortunately nested collections will always use the standard delimiters unless you specialize the class specifically for your collection).

    It also uses std::enable_if instead of of boost::enable_if, this is available on VC2010 and g++ 4.3 (if compiling with the -std=c++0x flag), so there's no dependency on boost.

    Finally, all the declarations have been made so it should work with both char and wchar_t, and non-standard allocator and traits types.

  • User profile image
    KerrekSB

    That is genius, brilliant! If you post the solution on SO, I will accept it as the answer! I haven't read it closely yet, but I'm excited to find out how you did this.

    One thing, though: Can we add associative container support to print a map like "{1: hello, 2: world, 3: foobar}"? Oh, I see that it works for maps, but not for unordered_maps. Does the code require explicit predeclaration of all supported container types? Perhaps that could be wrapped into a macro for the client code...

    Maybe we can use SFINAE to determined automagically whether a class supports ::begin() and ::end()?!

    Edit: I think I have made a trait class to detect the presence of iterators!

     

    template<typename T>
    struct mycont_helper
    {
    private:
      template<typename C> static char test(typename C::iterator*);
      template<typename C> static int  test(...);
    public:
      static const bool __value = sizeof(test<T>(0)) == sizeof(char);
    };
    
    template<typename T>
    struct mycont : public std::integral_constant<bool, mycont_helper<T>::__value>
    { };

    Usage: mycont&lt;T&gt;::value will be true for containers and false otherwise.

  • User profile image
    Sven Groot

    Like Marcelo's version, you must specialize the is_container template to inherit from true_type for each container type that you wish to use. I did a couple in the example, but you can easily add others. If you want to customize the delimiters, you similarly should specialize the delimiters template for that type.

    So all it would take to support unordered_map is:

    template<typename Key, typename Ty, typename Hash, typename Pred, typename Alloc>
    struct is_container<std::unordered_map<Key, Ty, Has, Pred, Alloc> > : public std::true_type { };

    The predefinitions aren't required for support. They are just there so that whatever header you put this is can declare is_container for list, map, vector, set, etc. without having to include <vector>, <list>, <set>, <map>, etc. if the user doesn't need them, which speeds up compilation times.

    I'm not sure if using SFINAE to discover begin() and end() is possible, but doing that would have the disadvantage that it would also match std::string, which is probably not what you want.

    EDIT: Your trait may work, but you probably want to check for const_iterator instead, and it will have the problem of also matching string, like I said.

  • User profile image
    KerrekSB

    @Sven Groot: Thanks, but I think I just discovered a way to use SFINAE to detect the presence of iterators (see my edit above), so hopefully I can completely avoid mentioning any explicit container types altogether.

    Bonus question: Can we SFINAE between "*iterator == pair<K,V>" and "*iterator == T"?

    Edit: I see your point about the string class, but wouldn't the string's operator<< be more specialized?

  • User profile image
    Sven Groot

    As I said, it will match string and you should check const_iterator instead. Even if you get it to exclude basic_string I think the danger of your method is that it always has the possibility of matching something that defines a begin(), end() and const_iterator but shouldn't be treated as a container.

    To distinguish between pair and others, you'd probably need to use the value_type typedef of a container.

  • User profile image
    KerrekSB

    Alright, I think we may be onto something. If we check for the presence of value_type first, and then also for the existence of begin()/end() _and_ const_iterator, what else could go wrong?

    Edit:

    I've tested a bit and it seems that with my SFINAE is_container trait everything works well, even in the presence of strings. This is great. Should we publish it somewhere? You should definitely post this on SO so I can give you an "accept". Perhaps we could send a copy to STL? Smiley
  • User profile image
    Sven Groot

    I've put it on SO as you requested. My gut feeling still says that trying to automatically detect containers based on the members of a type isn't the right thing to do, though.

  • User profile image
    KerrekSB

    Sure, if you find a situation were this breaks stuff, we should try to think about it, but for now I'm finding this tremendously useful.

    The only problem I can see is if you try to directly stream-out an object of a class for which you haven't defined an operator and which have iterators -- if you did have an overloaded operator, it would take precedence, and if you didn't and don't want it to be used like this, then you shouldn't write "cout << x". So... I really can't think of a way in which our templates would break an existing program. Please do tell if you have an example!

  • User profile image
    Sven Groot

    Yeah, it's more of a feeling. Determining the nature of a type just by what members it has doesn't feel right to me, somehow. It doesn't feel like "proper OO", if there is such a thing. Wink

    By the way, the modified code you posted on SO has a couple of identifier (the #ifndef guard for the header file and the __value member of the helper struct) that start with double underscores. Names that begin with a double underscore (or a single underscore and a capital) are reserved for compiler and library implementations by the standard, so you shouldn't be using them in your code.

  • User profile image
    KerrekSB

    Oh, thank you! I wasn't sure how to name various things, please let me know if anything else should be cleaner.

    By the way, you were missing the last template parameter in the operator with the print_container_helper argument. I'll update my modified code (and add an example of custom delimiters), but I wanted to let you know.

    I'd also like to use some template aliases for char- and wchar_t delimiter classes a la "template<typename T> using sdelims = delimiters<T, char>. Shame my GCC4.4 doesn't seem to understand.

    Finally, I want to get a generic outputter for std::tuple, too, like we have for pair; now trying to work through variadic templates...

    Edit: I just added a C array wrapper, check out my updated code on SO!

  • User profile image
    Sven Groot

    I have thought of a scenario where your version of the is_container trait runs into trouble.

    If for example I derive my own type from std::basic_string, that type will now use be printed as a container because the template operator<< is now more specific than string's operator<<, which is probably not what you want.

    Now I know you shouldn't derive from basic_string (it doesn't have a virtual destructor), but in general, if you have a type that has its own operator<<, and then derive from that type and the derived type matches your is_container trait, it will use the template operator<< while what you probably want is for it to use the base class operator<<.

  • User profile image
    KerrekSB

    Interesting. Indeed, you're not supposed to derive from most STL classes, but I see your point... a derived class with iterators whose base class already implements an output operator. Hm, well, I guess I'm not too worried about that, but perhaps there's some is_base-typetrait magic that could detect such cases? For that matter, is there a typetrait that checks whether a particular member function exists?

  • User profile image
    punkouter

    Sven, kerrek, first of all, I'd like to say that this is a ver good discussion and very insightful. Very useful Indeed. Sven, I agree with you that it doesn't feel right to check the availability of members. I understand that you just want to be safe with the pretty printer by ensuring that it is a container that you're passing in. However, doing so may not be in line with the spirit of STL itself. But first, let me explain how I see STl. I see STL holds the dynamic language duck typing in a statically typed environment. "if it walk, swim, quake like a duck then it's a duck" The same with the problem you guys are facing. If a 'thing' support a begin and end function and it returns an iterator, or const_iterator then it is a container as far as e function cares. As it can operate under such contract. This is not conceptualize a defect. Its an outcome of how tempting works. There is no guarantee that the begin method is the begin method mentioned in the IContainer method for instance. Hence, there is never a guarantee that a begin method means the begin method that the original implementor thinks. Again the contract permits it to be like that. So, if I were to analyze what should've been done in the case of Sven solution, I'd suggest to leave it like that and put a note at the documentation. This will ensure the most flexible solution. But it punishes user that use it wrongly. If you want to be safe, and doing it properly, then I'd suggest that you actually restrict T to be derived from an interface such as IContainer. However, doing so means you have to change all the standard containers to implement IContainer which is not feasible. Other than those two, you are risking on hacking the solution and from my experience it's best not to hack if it's possible especially if your code is going to be used by other people.

Conversation locked

This conversation has been locked by the site admins. No new comments can be made.