Templates for generic code and code flexibility

Question

I have a data which is a std::vector of a "small collection" of items of a given type struct Bunny {};.

I was vague about "small collection" because for now it's a collection of two of them, and so I'm just using the following alias

using Bunnies = std::array<Bunny,2>; // probably it'd be better to make it a struct, so that the compiler
                                     // could typecheck, but I think this is not relevant to my question

(Probably using a std::pair<Bunny,Bunny> would be ok too, but I think std::array<…,2> carries with it the idea that the entities must be homogeneous in type.)

That data, std::vector<Bunnies> is the input to a function:

auto fun(std::vector<Bunnies> input) {

    // This function does no more than reorganizing the `Bunny`s
    // which are in `input` in another, more complex way than just
    // "a `std::vector` of `std::array`s of 2 `Bunny`s".
    // So in my case `auto` is actually a `ResultOfBunnys` or really
    // `Result<Bunny>`.
};

At this point, however, I want to generalize fun, because I'm gonna pass to it not just Bunnys (in the form of a Bunnies), but also other stuff (in the form of some collection).

I guess templates is the way to go for such a generalization. So what could I do? I could do this:

template<typename ObjType>
auto fun(std::vector<std::array<ObjType,2>> input) {

    // do stuff
    // return something
};

but it would hardcode std::array in the function interface. I could do this:

template<typename ObjsType>
auto fun(std::vector<ObjsType> input) {
    using Obj = typename ObjsType::value_type;
    // do stuff
    // return something
};

but this would require that the ObjsType that I pass have a value_type member type. Or I could do this:

template<typename ObjType, typename ObjsType>
auto fun(std::vector<ObjsType> input) {

    // do stuff
    // return something
};

which forces the user to enter a template parameter which is consistent with the one which is deduced via the input argument.

I've been told that the first two options allow less flexibility than the third one. I kind of agree, but I would like to know a bit more about this topic. I don't even know whether there's a book about this things.

Answer 1

This is part of why most of the standard library deals in iterators rather than dealing directly with containers themselves. Iterators were designed from the beginning to support iteration over the data in the container, without your having to worry about the container itself.

So in your case, you're passing an std::vector<T>, where T is a std::array<Bunny, 2>, but that's open to change.

If you start with iterators:

template <class It>
auto fun(It begin, It end) {

    // This function does no more than reorganizing the `Bunny`s
    // which are in `input` in another, more complex way than just
    // "a `std::vector` of `std::array`s of 2 `Bunny`s".
    // So in my case `auto` is actually a `ResultOfBunnys` or really
    // `Result<Bunny>`.
};

...most of what you've discussed simply disappears. There is one point to consider though: how do you get the type the iterator refers to? Fortunately, you're not the first to have run into needing to know that, so the standard library can help. There's an iterator_traits header containing (big surprise) an iterator_traits template that can help you get information about an iterator, without having to know a lot of details. Ultimately, the iterator does have to satisfy its requirements somehow, but it's equipped to deal with the usual variations (e.g,. either a std::vector<T>::iterator or a T *).

So in your case:

template <class It>
auto fun(It begin, It end) {
    using value_type = std::iterator_traits<It>::value_type;
    using return_type = Result<value_type>;

    // define our return value
    return_type result;

    // do the reorganizing, putting the result into `result`

    return result;
};

Some people do find it a bit clumsy to have to pass two parameters instead of one--and I can sympathize with that. If you're sufficiently bothered by that (can can restrict yourself to recent compilers) you may want to look up the new rangeslibrary. Simplifying a lot, this basically lets you take the two iterators, and put them together into a single object, so you only pass one instead of two. In the bigger picture, ranges do a lot more than that, but that's enough for the moment (i.e., enough to deal with any concern over having to pass two parameters instead of one).

If you really need to do something where you need to deal with the container itself rather than just iterating over the data in the container, you may want to look into template template parameters. A template template parameter allows you to pass a template as a parameter to a template. And here I'm talking about the template itself, not an instantiation over a particular type. To use your examples, std::vector<Bunnies> is what I'm referring to as an instantiation over a particular type. In this case, the template itself is just std::vector. So, you can have something like:

template < template<typename, typename> Collection>
class Foo {

...which says that Collection will refer to some template that itself has two template parameters (which most collections do--the contained type, and the Allocator type), so that Foo could deal equally well with an std::vector<T> or an std::list<T> or an std::deque<T>, etc.

#include <vector>
#include <array>
#include <deque>

template <class T>
class Result {

};

// T is some contained type, and Collection is some template that contains T's.
template <typename T, template<typename> typename Collection>
class Foo {
    Collection<T> const c;

public:

};

class Bunny {};

int main(){ 
    using Bunnies = std::array<Bunny, 2>;

    // A Foo containg a an `std::vector<int>`
    Foo<int, std::vector> f;

    // A Foo containing an `std::deque<Bunny>`
    Foo<Bunny, std::deque> g;

    // A Foo containing an `std::list<Bunnies>`
    Foo<Bunnies, std::list> h;

    // Foo is a template that contains a template...
    // so we can create a Foo of Foo--that is, a Foo that contains Foo's.
    Foo<Foo<Bunnies, std::list>, std::deque> i;
}

Also note that when you're dealing with function templates, the compiler can "pull apart" a template into its components (so to speak) so you can do something like this:

template <class T, template<class> class Collection>
Result<T> fun(Collection<T> const &input) {

    return Result<T>(input.front());
}

And when you call it, you just pass a normal collection, and the compiler sorts out which part is the template itself, and which is the type it contains, so you don't have to specify that explicitly:

    std::vector<Bunnies> b { { 0, 1 }, { 1, 2}};
    fun(b); // It will figure out that `Container` is `vector` and T is Bunnies