Joining keys/values from C++ STL associative containers

Question

I have a join function that operates on STL strings. I want to be able to apply it to to a container like this:

getFoos(const std::multimap<std::string, std::string>& map) {
    return join_values(",", map.equal_range("foo"));

In other words, find all matching keys in the collection and concatenate the values into a single string with the given separator. Same thing with lower_bound() and upper_bound() for a range of keys, begin()/end() for the entire contents of the container, etc..

The closest I could get is the following:

template <typename T>
struct join_range_values : public T::const_iterator::value_type::second_type {
    typedef typename T::const_iterator::value_type pair_type;
    typedef typename pair_type::second_type value_type;

    join_range_values(const value_type& sep) : sep(sep) { }

    void operator()(const pair_type& p) {
     // this function is actually more complex...
     *this += sep;
     *this += p.second;
    }
private:
    const value_type sep;
};

template <typename T>
typename T::const_iterator::value_type::second_type join_values(
    const typename T::const_iterator::value_type::second_type& sep,
    const std::pair<typename T::const_iterator, typename T::const_iterator>& range) {
    return std::for_each(range.first, range.second, join_range_values<T>(sep));
}

(I realize that inheriting from std::string or whatever the key/value types are is generally considered a bad idea, but I'm not overloading or overriding any functions, and I don't need a virtual destructor. I'm doing so only so that I can directly use the result of for_each without having to define an implicit conversion operator.)

There are very similar definitions for join_range_keys, using first_type and p.first in place of second_type and p.second. I'm assuming a similar definition will work for joining std::set and std::multiset keys, but I have not had any need for that.

I can apply these functions to containers with strings of various types. Any combination of map and multimap with any combination of string and wstring for the key and value types seems to work:

typedef std::multimap<std::string, std::string> NNMap;
const NNMap col;
const std::string a = join_keys<NNMap>(",", col.equal_range("foo"));
const std::string b = join_values<NNMap>(",", col.equal_range("foo"));

typedef std::multimap<std::string, std::wstring> NWMap;
const NWMap wcol;
const std::string c = join_keys<NWMap>(",", wcol.equal_range("foo"));
const std::wstring d = join_values<NWMap>(L",", wcol.equal_range("foo"));

typedef std::multimap<std::wstring, std::wstring> WWMap;
const WWMap wwcol;
const std::wstring e = join_keys<WWMap>(L",", wwcol.equal_range(L"foo"));
const std::wstring f = join_values<WWMap>(L",", wwcol.equal_range(L"foo"));

This leaves me with several questions:

1. Am I missing some easier way to accomplish the same thing? The function signature especially seems overly complicated.
2. Is there a way to have join_values automatically deduce the template parameter type so that I don't need to call it with join_values<MapType> every time?
3. How can I refactor the join_values and join_keys functions and functors to avoid duplicating most of the code?

I did find a slightly simpler solution based on std::accumulate, but it seems to require two complete copy operations of the entire string for each element in the range, so it's much less efficient, as far as I can tell.

template <typename T>
struct join_value_range_accum : public T::const_iterator::value_type::second_type
{
    typedef typename T::const_iterator::value_type::second_type value_type;
    join_value_range_accum(const value_type& sep) : sep(sep) {}

    using value_type::operator=;
    value_type operator+(const typename T::const_iterator::value_type& p)
    {
        return *this + sep + p.second;
    }
private:
    const value_type sep;
};

typedef std::multimap<std::string, std::string> Map;
Map::_Pairii range = map.equal_range("foo");
std::accumulate(range.first, range.second, join_value_range_accum<Map>(","));

Answer 1

The STL algorithms typically work with iterators, not containers, so I would suggest something like the following.

template <typename T, typename Iterator>
T join(
    const T sep,
    Iterator b,
    Iterator e)
{
    T t;

    while (b != e)
        t = t + *b++ + sep;

    return t;
}

Then, you need an iterator that will pull out keys or values. Here's an example:

template <typename Key, typename Iterator>
struct KeyIterator
{
    KeyIterator(
        Iterator i)
        :_i(i)
    {
    }

    KeyIterator operator++()
    {
        ++_i;
        return *this;
    }

    bool operator==(
        KeyIterator ki)
    {
        return _i = ki._i;
    }

    typename Iterator::value_type operator*()
    {
        return _i->first;
    }
};

How to use:

string s = join(",", KeyIterator(my_map.begin()), KeyIterator(my_map.end()));

Answer 2

Just FYI for anyone interested, I came to the following solution based on keraba's input.

I did have to make some changes, specifically:

1. Making the T template parameter for the separator string a dependent type name so that the compiler would infer it automatically (allowing quoted literals to be automatically converted into string objects)
2. Using a functor derived from string to get around the fact that the dependent name declared in the iterator is const, so a local temporary defined in join() ends up being const and therefore unmodifiable.

---

template <typename I>
struct MapKeyIterator : public I
{
    typedef typename I::value_type::first_type value_type;
    MapKeyIterator(I const &i) : I(i) { }
    value_type const & operator*() const { return (*this)->first; }
};

template <typename I>
struct MapValueIterator : public I
{
    typedef typename I::value_type::second_type value_type;
    MapValueIterator(I const &i) : I(i) { }
    value_type const & operator*() const { return (*this)->second; }
};

template <typename I>
struct join_functor : public I::value_type
{
    typedef typename I::value_type value_type;
    join_functor(value_type const &sep) : sep(sep) { }
    void operator()(value_type const &s)
    {
     *this += s;
     *this += sep;
    }
private:
    const value_type sep;
};

template <typename I>
typename I::value_type join(typename I::value_type const &sep, I beg, I const &end)
{
    return std::for_each(beg, end, join_functor<I>(sep));
}

template <typename I>
typename I::value_type::first_type join_keys(typename I::value_type::first_type const &sep, I const &beg, I const &end)
{
    return join(sep, MapKeyIterator<I>(beg), MapKeyIterator<I>(end));
}
template <typename I>
typename I::value_type::first_type join_keys(typename I::value_type::first_type const &sep, std::pair<I, I> const &ip)
{
    return join(sep, MapKeyIterator<I>(ip.first), MapKeyIterator<I>(ip.second));
}
template <typename I>
typename I::value_type::second_type join_values(typename I::value_type::second_type const &sep, I const &beg, I const &end)
{
    return join(sep, MapValueIterator<I>(beg), MapValueIterator<I>(end));
}
template <typename I>
typename I::value_type::second_type join_values(typename I::value_type::second_type const &sep, std::pair<I, I> const &ip)
{
    return join(sep, MapValueIterator<I>(ip.first), MapValueIterator<I>(ip.second));
}

This allows for:

join_keys(",", map.equal_range("foo"));
join_values(",", map.equal_range("foo"));
join_values(",", map.begin(), map.end());

as well as:

join(",", set.lower_bound("f"), set.upper_bound("g"));

with containers based on either std::string or std::wstring.

This is still fairly complex, but it solves items 2 and 3 from my original post and it does seem to fit much better with the design of the STL.