Iterate through STL sequence and associative containers using same code?

Let's say I'd like to write an algorithm that prints 开发者_如何学Gothe value of each element in a container. The container could be a Sequence or Associative container (e.g. std::vector or std::map). In the case of a sequence, the algorithm would print the value_type. In the case of an associative type, the algorithm would print the data_type. How can I write my algorithm (only once!) so that it works with either one? Pretend that the algorithm is complex and that I don't want to repeat it for both sequence/associative versions.

For example:

template <class Iterator>
void printSequence(Iterator begin, Iterator end)
{
    for (Iterator it=begin; it!=end; ++it)
        std::cout << *it;
}

template <class Iterator>
void printAssociative(Iterator begin, Iterator end)
{
    for (Iterator it=begin; it!=end; ++it)
        std::cout << it->second;
}

template <class Iterator>
void printEither(Iterator begin, Iterator end)
{
    // ????
}

The difference that you have between your two function templates is not a difference between associative containers and sequences but a difference in the part of the type that is stored.

To clarify, std::set is an associative container but would work with your printSequence function; the problem with map is not the fact that it is associative, but that the value_type is a pair an you are only interested on the second part.

The simplest thing to do is to abstract the dereferencing operation.

E.g. used like this:

#include <map>
#include <vector>

template< class X, class Y >
void test( const std::map<X, Y>& mp )
{
    printEither( mp.begin(), mp.end(), MakeMapDerefence( mp ) );
}

template< class Y >
void test( const std::vector<Y>& vec )
{
    printEither( vec.begin(), vec.end(), MakeSimpleDereference( vec ) );
}

Defined like this (there's a fair bit of boiler plate that's probably a boost one-liner):

template< class ReferenceType, class IteratorType >
struct SimpleDereference
{
    ReferenceType operator() ( IteratorType i ) const
    {
        return *i;
    }
};

template< class ReferenceType, class IteratorType >
struct MapDereference
{
    ReferenceType operator() ( IteratorType i ) const
    {
        return i->second;
    }
};

// Helper template function to make an appropriate SimpleDerefence instance
template< class Container >
SimpleDereference< typename Container::const_reference
                 , typename Container::const_iterator >
MakeSimpleDereference( const Container& )
{
    return SimpleDereference< typename Container::const_reference
                            , typename Container::const_iterator >();
}

// Helper template function to make an appropriate SimpleDerefence instance
template< class Container >
SimpleDereference< typename Container::reference
                 , typename Container::iterator >
MakeSimpleDereference( Container& )
{
    return SimpleDereference< typename Container::reference
                            , typename Container::iterator >();
}

// Helper template function to make an appropriate MapDerefence instance
template< class Container >
MapDereference< const typename Container::mapped_type&
              , typename Container::const_iterator >
MakeMapDerefence( const Container& )
{
    return MapDereference< const typename Container::mapped_type&
                         , typename Container::const_iterator >();
}

// Helper template function to make an appropriate MapDerefence instance
template< class Container >
MapDereference< typename Container::mapped_type&
              , typename Container::iterator >
MakeMapDereference( Container& )
{
    return MapDereference< typename Container::mapped_type&
                         , typename Container::iterator >();
}

#include <iostream>
#include <ostream>

template <class Iterator, class Dereference> void printEither(Iterator begin, Iterator end, Dereference deref)
{
    for (; begin != end; ++begin)
    {
        std::cout << deref(begin);
    }
}

I've whipped up an iterator adapter based on Charles' answer. I'm posting it here in case anyone finds it useful:

#include <iostream>
#include <map>
#include <vector>
#include <boost/iterator/iterator_adaptor.hpp>

//------------------------------------------------------------------------------
template <class Iterator>
void print(Iterator begin, Iterator end)
{
    for (Iterator it=begin; it!=end; ++it)
        std::cout << *it << "\n";
}


//------------------------------------------------------------------------------
template <class BaseIterator>
class MapDataIterator :
    public boost::iterator_adaptor<
        MapDataIterator<BaseIterator>,
        BaseIterator,
        typename BaseIterator::value_type::second_type >
{
public:
    typedef typename BaseIterator::value_type::second_type& reference;

    MapDataIterator() {}

    explicit MapDataIterator(BaseIterator base)
    :   MapDataIterator::iterator_adaptor_(base) {}

 private:
    friend class boost::iterator_core_access;
    reference dereference() const
        {return this->base_reference()->second;}
};

//------------------------------------------------------------------------------
int main()
{
    std::vector<int> vec;
    vec.push_back(31);
    vec.push_back(41);
    std::map<int,int> map;
    map[31] = 41;
    map[59] = 26;

    typedef MapDataIterator< std::map<int,int>::iterator > DataIter;
    print( vec.begin(), vec.end() );
    print( DataIter(map.begin()), DataIter(map.end()) );
}

This solution has the added advantage that the algorithm need not be aware of how to dereference the iterators. It is also reusable for any existing algorithm that expects a "data sequence".

I'm surprised this little critter doesn't already exist in Boost.