Output iterator's value_type

Question

The STL commonly defines an output iterator like so:

template<class Cont>
class insert_iterator
: public iterator<output_iterator_tag,void,void,void,void> {
    // ...

Why do output iterators define value_type as void? It would be useful for an algorithm to know what type of value it is supposed to output.

For example, a function that translates a URL query "key1=value1&key2=value2&key3=value3" into any container that holds key-value strings elements.

template<typename Ch,typename Tr,typename Out>
void parse(const std::basic_string<Ch,Tr>& str, Out result)
{
    std::basic_string<Ch,Tr> key, value;
    // loop over str, parse into p ...
        *result = typename iterator_traits<Out>::value_type(key, value);
}

The SGI reference page of value_type hints this is because it's not possible to dereference an output iterator. But that's not the only use of value_type: I might want to instantiate one in order to assign it to the iterator.

What alternative approach is there for constructing a value to output with the output iterator? Two approaches I considered:

• Accept a functor parameter that would return an object of the correct type. I still want to have a version of the algorithm that doesn't take that function object parameter though.
• Require that the output container holds pair<string,string>, or else a type convertible from that. I wonder if I can do without this requirement, perhaps allow any element that can construct from two std::string s.

Answer 1

The real value type of the iterator could well be the iterator itself. operator* may easily just return a reference to *this because the real work is done by the assignment operator. You may well find that *it = x; and it = x; have exactly the same effect with output iterators (I suppose special measures might be taken to prevent the latter from compiling).

As such, defining the real value type would be just as useless. Defining it as a void, on the other hand, can prevent errors like:

 typename Iter::value_type v = *it; //useless with an output iterator if it compiled

I suppose this is just the limit of the concept of output iterators: they are objects which "abuse" operator overloading, so as to appear pointerlike, whereas in reality something completely different is going on.

Your problem is interesting, though. If you want to support any container, then the output iterators in question would probably be std::insert_iterator, std::front_insert_iterator and std::back_insert_iterator. In this case you could do something like the following:

#include <iterator>
#include <vector>
#include <string>
#include <map>
#include <iostream>

//Iterator has value_type, use it
template <class T, class IterValue>
struct value_type
{
    typedef IterValue type;
};

//output iterator, use the container's value_type
template <class Container>
struct value_type<Container, void>
{
    typedef typename Container::value_type type;
};

template <class T, class Out>
void parse_aux(Out out)
{
    *out = typename value_type<T, typename Out::value_type>::type("a", "b");
}

template <template <class> class Out, class T>
void parse(Out<T> out)
{
    parse_aux<T>(out);
}

//variadic template in C++0x could take care of this and other overloads that might be needed
template <template <class, class> class Out, class T, class U>
void parse(Out<T, U> out)
{
    parse_aux<T>(out);
}

int main()
{
    std::vector<std::pair<std::string, std::string> > vec;
    parse(std::back_inserter(vec));
    std::cout << vec[0].first << ' ' << vec[0].second << '\n';

    std::map<std::string, std::string> map;
    parse(std::inserter(map, map.end()));
    std::cout << map["a"] << '\n';

    //just might also support normal iterators
    std::vector<std::pair<std::string, std::string> > vec2(1);
    parse(vec2.begin());
    std::cout << vec2[0].first << ' ' << vec2[0].second << '\n';
}

It would still only get you this far. I suppose one could take this further, so it can also manage, say, a std::ostream_iterator<printable_type>, but at some point it would get so complex that it takes a god to decipher the error messages, should something go wrong.

Answer 2

The purpose of the value_type of an iterator is to define the type that is returned when that iterator is dereferenced. For output iterators, the only legitimate use of the dereference operator is when it is used in conjunction with the assignment operator--in the form of *output_iterator = value. The type that is returned when dereferencing an output iterator does not necessarily have any direct relationship with the types that can be stored via the output iterator. The only needed relationship is that there be some way of assigning the latter types to the former type.

Moreover, the output iterator can store values of multiple types, and these types do not have to have any relationship with one another. Take for example the null_output_iterator described in Discarding the output of a function that needs an output iterator. That iterator can accept for storage any type of value.