Container traits. For explanation, see: http://functionalcpp.wordpress.com/2013/08/22/container-traits/

container_traits.h

/*
 * Copyright (c) 2013, Daniel Park
 * All rights reserved.
 *
 * Permission to modify and redistribute this software is granted to
 * anyone provided the above copyright notice, this condition and the
 * following disclaimer are retained.
 *
 * This software is provided "as is", without and express or implied
 * warranty. In no event shall the author be liable for damages arising
 * from the use of this software.
 */

#pragma once

#include <deque>
#include <list>
#include <set>
#include <string>
#include <unordered_set>
#include <vector>

template <class C>
struct container_traits
{
    // Type value_type
    // void add_element(C&,T)
    // void concat(C&,C)
    // Type rebind<U>
};

template<class C>
struct sequence_container_traits;

template<template<class,class> class C, class T, class A>
struct sequence_container_traits<C<T,A>>
{
    using value_type = T;

    static void add_element(C<T,A>& c, const T& t)
    {
        c.push_back(t);
    }

    static void concat(C<T,A>& lhs, const C<T,A>& rhs)
    {
        lhs.insert(lhs.end(),rhs.begin(),rhs.end());
    }

    template<class U>
    using rebind = C<U,typename A::template rebind<U>::other>;
};

template<class... Args>
struct container_traits<std::deque<Args...>> : public sequence_container_traits<std::deque<Args...>>
{};

template<class... Args>
struct container_traits<std::list<Args...>> : public sequence_container_traits<std::list<Args...>>
{};

template<class... Args>
struct container_traits<std::vector<Args...>> : public sequence_container_traits<std::vector<Args...>>
{};

template<class C>
struct associative_container_traits;

template<template<class,class,class> class C, class T, template<class> class O, class A>
struct associative_container_traits<C<T,O<T>,A>>
{
    using value_type = T;

    static void add_element(C<T,O<T>,A>& c, const T& t)
    {
        c.insert(t);
    }

    static void concat(C<T,O<T>,A>& lhs, const C<T,O<T>,A>& rhs)
    {
        lhs.insert(rhs.begin(),rhs.end());
    }

    template<class U>
    using rebind = C<U,O<U>,typename A::template rebind<U>::other>;
};

template<class... Args>
struct container_traits<std::multiset<Args...>> : public associative_container_traits<std::multiset<Args...>>
{};

template<class... Args>
struct container_traits<std::set<Args...>> : public associative_container_traits<std::set<Args...>>
{};

template<class C>
struct hash_container_traits;

template<template<class,class,class,class> class C, class T, template<class> class H, template<class> class O, class A>
struct hash_container_traits<C<T,H<T>,O<T>,A>>
{
    using value_type = T;

    static void add_element(C<T,H<T>,O<T>,A>& c, const T& t)
    {
        c.insert(t);
    }

    static void concat(C<T,H<T>,O<T>,A>& lhs, const C<T,H<T>,O<T>,A>& rhs)
    {
        lhs.insert(rhs.begin(),rhs.end());
    }

    template<class U>
    using rebind = C<U,H<U>,O<U>,typename A::template rebind<U>::other>;
};

template<class... Args>
struct container_traits<std::unordered_multiset<Args...>> : public hash_container_traits<std::unordered_multiset<Args...>>
{};

template<class... Args>
struct container_traits<std::unordered_set<Args...>> : public hash_container_traits<std::unordered_set<Args...>>
{};

// basic_string
template<class T, template<class> class K, class A>
struct container_traits<std::basic_string<T,K<T>,A>>
{
    using value_type = T;

    static void add_element(std::basic_string<T,K<T>,A>& c, const T& t)
    {
        c.push_back(t);
    }

    static void concat(std::basic_string<T,K<T>,A>& lhs, const std::basic_string<T,K<T>,A>& rhs)
    {
        lhs+=rhs;
    }

    template<class U>
    using rebind = std::basic_string<U,K<U>,typename A::template rebind<U>::other>;
};

eval.h

/*
 * Copyright (c) 2013, Daniel Park
 * All rights reserved.
 *
 * Permission to modify and redistribute this software is granted to
 * anyone provided the above copyright notice, this condition and the
 * following disclaimer are retained.
 *
 * This software is provided "as is", without and express or implied
 * warranty. In no event shall the author be liable for damages arising
 * from the use of this software.
 */

#pragma once

#include <type_traits>
#include <utility>

template<
    class F, class... Args,
    class = typename std::enable_if<!std::is_member_function_pointer<F>::value>::type,
    class = typename std::enable_if<!std::is_member_object_pointer<F>::value>::type
    >
auto eval(F&& f, Args&&... args) -> decltype(f(std::forward<Args>(args)...))
{
    return f(std::forward<Args>(args)...);
}

template<class R, class C, class... Args>
auto eval(R(C::*f)() const, const C& c, Args&&... args) -> R
{
    return (c.*f)(std::forward<Args>(args)...);
}

template<class R, class C, class... Args>
auto eval(R(C::*f)() const, C& c, Args&&... args) -> R
{
    return (c.*f)(std::forward<Args>(args)...);
}

template<class R, class C, class... Args>
auto eval(R(C::*f)(), C& c, Args&&... args) -> R
{
    return (c.*f)(std::forward<Args>(args)...);
}

template<class R, class C>
auto eval(R(C::*m), const C& c) -> const R&
{
    return c.*m;
}

template<class R, class C>
auto eval(R(C::*m), C& c) -> R&
{
    return c.*m;
}

template<class... Args>
using eval_result_type = decltype(eval(std::declval<Args>()...));

main.cpp

/*
 * Copyright (c) 2013, Daniel Park
 * All rights reserved.
 *
 * Permission to modify and redistribute this software is granted to
 * anyone provided the above copyright notice, this condition and the
 * following disclaimer are retained.
 *
 * This software is provided "as is", without and express or implied
 * warranty. In no event shall the author be liable for damages arising
 * from the use of this software.
 */

// Build using -std=gnu++1y

#include <iostream>
#include <functional>
#include <locale>

#include "container_traits.h"
#include "eval.h"

template<class F, class C>
auto my_transform(F&& f, const C& c)
{
    using OutputType = typename container_traits<C>::template rebind<
        decltype(eval(f,std::declval<typename container_traits<C>::value_type>()))>;

    OutputType out;
    for (const auto& a : c)
        container_traits<OutputType>::add_element(out, eval(f,a));

    return out;
}

template<class C>
auto flatten(const C& c)
{
    using OutputType = typename container_traits<C>::template rebind<
        typename container_traits<typename container_traits<C>::value_type>::value_type>;

    OutputType out;
    for (const auto& inner : c)
        for (const auto& a : inner)
            container_traits<OutputType>::add_element(out, a);

    return out;
}

template<class C>
auto chain(const C& c)
{
    using OutputType = typename container_traits<C>::value_type;

    OutputType out;
    for (const auto& a : c)
        container_traits<OutputType>::concat(out, a);

    return out;
}

int main()
{
    // words in reverse lexographic order
    std::multiset<std::string,std::greater<std::string>> words{
        "my","hovercraft","is","full","of","eels"};

    std::cout << "word lengths: ";
    for (std::size_t length : my_transform(&std::string::size,words))
        std::cout << length << " ";
    std::cout << "\n";

    std::cout << "number of \'f\'s: " << flatten(words).count('f') << "\n";

    auto shout = [](char c){return std::toupper(c,std::locale::classic());};
    std::cout << "yelling: " << my_transform(shout,chain(words)) << "\n";

    return 0;
}