Container Traits

The containers defined in the standard template library all provide very similar functionalities, however they are difficult to use in a generic way because of the way they are templated.

In the STL, there are a few categories of containers which behave similarly and have similar templates:

  • Sequence containers take 2 arguments, the value type and an allocator. Eg. std::vector
  • Associative containers take 3 arguments, the value type, a comparison function and an allocator. Eg. std::multiset
  • Hash containers take 4 arguments, the value type, a hash, an equality test and an allocator. Eg. std::unordered_set
  • Strings take 3 arguments, the character type, character traits and an allocator. Eg. std::wstring

Hash containers are properly called unordered associative containers, but that’s a mouth full so I will just refer to them as hash containers. To simplify the discussion, forward lists and maps will be ignored.

When dealing with containers generically, the most common things we will want to do are add an element, concatenate two containers and rebind the value type. The first two seem like no brainers, but why rebind? Suppose you are doing something like this:

template<class F, class C>
auto my_transform(F&& f, const C& c) -> OutputType // What is this?
{
    OutputType out;
    for (const auto& a : c)
        out.insert(eval(f,a));
        
    return out;
}

That code conceptually works for the associative and hash containers, which use the insert to add elements. However, in order to determine OutputType, we would have to dig into their template parameters which would result in code which is complex at best and unmaintainable at worst.

Enter container traits:

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

Here are the definitions for associative containers:

template<class C>
struct associative_container_traits;

// C: container, T: value type, O: compare, A: allocator
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::set<Args...> :
    public associative_container_traits<std::set<Args...>>
{};

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

Similar code is written for the sequence, hash and string containers, but I will spare you the bore.

Care must be taken to ensure that the template parameters are properly matched in rebind. For example, the compare parameter simply substitutes its template parameter. Ideally, comparators would have their own rebind the way allocators do, however, the current code works with the default std::less so it serves our purposes for now.

With container traits in hand, we can now write the original function, and a few others, in a very generic way:

// Transform elements in a container
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;
}

// flattens a container of containers
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;
}

// concatenates containers within a container
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;
}

I omit the trailing return types because they are very long and unnecessary with c++14 return type deduction.

The functions can be used like this:

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;
}

Output:

word lengths: 10 4 4 2 2 2
number of 'f's: 3
yelling: OFMYISHOVERCRAFTFULLEELS

You can download the complete code for this post here here.

About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s