(C++) Template to check whether an object is in a vector/array/list/...?

Question

Is it possible to create a template in C++(11) for a function to check whether an object is contained in either a std::vector, std::array or std::list (and possibly even more container types)?

What I have by now:

typedef std::shared_ptr<Tag> SharedTag;
typedef std::vector<SharedTag> TagList;

bool
Tag::isIn(const TagList& lst) {
    return std::any_of(lst.begin(), lst.end(), [this](const SharedTag& t) {
        return t->name == this->name;
    });
}

Tag is a normal class. The comparison, of course, should be done t == this, which will be an operator== later on. I did not include this here for simplicity.

So, is it possible to write the upper code only once (without the typedef's though,) for std::vector, std::array, std::list(, maybe for std::set) and so on?

I couldn't find a base-type of all these classes,... which would be my first idea...

Can you write your code in terms of iterators? There are categories such as random access iterator, forward iterator etc. — Neil Kirk, Feb 24 '15 at 20:43
@NeilKirk: The internal bits already do that, he seems to simply want a wrapper function — Mooing Duck, Feb 24 '15 at 20:53

Cornstalks · Accepted Answer · 2015-02-24T21:29:30.563

Option 1 (good): just use std::find directly:

std::vector<int> v; // populate v however you want
std::vector<int>::const_iterator i = std::find(v.cbegin(), v.cend(), 42);
if (i != v.end()) {
    // Now you know 42 is in v
} else {
    // Now you know 42 is not in v
}

Option 2 (better): wrap std::find in a helper function:

template <typename Container, typename Value>
bool contains(const Container& c, const Value& v)
{
    return std::find(std::begin(c), std::end(c), v) != std::begin(c);
}

// Example usage:
std::vector<int> v; // populate v however you want
if (contains(v, 42)) {
    // You now know v contains 42
}

Option 3 (best): use the find method of containers that provide one (which is faster for sorted containers, like set), and std::find for containers that don't provide one:

// If you want to know why I added the int and long parameter,
// see this answer here: http://stackoverflow.com/a/9154394/1287251

template <typename Container, typename Value>
inline auto contains(const Container& c, const Value& v, int) -> decltype(c.find(v), bool()) {
    return c.find(v) != std::end(c);
}

template <typename Container, typename Value>
inline bool contains(const Container& c, const Value& v, long) {
    return std::find(std::begin(c), std::end(c), v) != std::end(c);
}

template <typename Container, typename Value>
bool contains(const Container& c, const Value& v) {
    return contains(c, v, 0);
}

// Example usage:
std::set<int> s; // populate s however you want
if (contains(s, 42)) {
    // You now know s contains 42
}

Of course, you could write std::find yourself, but you might as well use it.

score 2 · Answer 2 · answered Feb 24 '15 at 20:43

You may use template:

typedef std::shared_ptr<Tag> SharedTag;

template <typename Container>
bool Tag::isIn(const Container& lst) {
    return std::any_of(lst.begin(), lst.end(), [this](const SharedTag& t) {
        return t->name == this->name;
    });
}

That requires that Container is a container of something convertible to SharedTag.

score 1 · Answer 3 · answered Feb 24 '15 at 20:57

There is no common base-type between those containers. That's just not the way the STL library works, it is based on templates and generic programming principles.

So, if you want to implement the function once for all containers, you would have to make it a template. Here is a basic form:

template <typename TagContainer>
bool Tag::isIn(const TagContainer& lst) {
  return std::any_of(lst.begin(), lst.end(), [this](const SharedTag& t) {
    return t->name == this->name;
  });
};

But this has the problem that you could technically pass anything to this function that isn't actually a container of SharedTag, so, to solve this issue, you could use a trick called Sfinae to enforce that rule:

template <typename TagContainer>
typename std::enable_if< std::is_same< SharedTag, typename TagContainer::value_type >::value,
bool >::type Tag::isIn(const TagContainer& lst) {
  return std::any_of(lst.begin(), lst.end(), [this](const SharedTag& t) {
    return t->name == this->name;
  });
};

Which kind of ugly, but it works.

There is still one problem though. I suspect that your Tag class is a normal non-template class, which means that you are probably implementing it in a cpp file, but templates need to be implemented in the header file (because function templates need to have their implementation visible to the compiler to generate a new concrete version of it for each type that you call it with).

One way to avoid this problem is to provide a number of overloaded non-template functions for each container you want to support, and then, under-the-hood, you call a local function template, and in this case, you don't need the sfinae trick to constrain it, since it is already limited to the set of overloads that you provided. Something like this:

template <typename TagContainer>
bool Tag::isIn_impl(const TagContainer& lst) {
  return std::any_of(lst.begin(), lst.end(), [this](const SharedTag& t) {
    return t->name == this->name;
  });
};

bool Tag::isIn(const std::list<SharedTag>& lst) {
  return isIn_impl(lst);
};

bool Tag::isIn(const std::vector<SharedTag>& lst) {
  return isIn_impl(lst);
};

bool Tag::isIn(const std::set<SharedTag>& lst) {
  return isIn_impl(lst);
};

Note that the isIn_impl is a member function template that should be declared in the header file, in the private section of the class, and can safely be defined in the cpp file, because that cpp file is the only place where that function template is called from.

The obvious issue with that solution is that you have to manually provide every overload that you want to support, which means that it isn't very "scalable" in the future, but in real-life, there probably aren't that many containers that you'd want to support. If you want the full generality, you really have to use the template approach (unless you want to do type-erasure on the container... but that's a bit beyond the scope of what I'm willing to explain here).

Thanks! That's a great explanation, also! – musicmatze Feb 24 '15 at 21:02 — musicmatze, Feb 24 '15 at 21:02

Stefano Sanfilippo · Answer 4 · 2015-02-24T21:18:54.363

You can use a nested variadic template to achieve this. Here is a handy demo: note the magic part, template <template <typename...> class V, typename E>. A variadic template is necessary because vector, list &co. all have a different number of template parameters (allocator, comparator etc.) for which a default value is supplied by the STL.

#include <vector>
#include <string>
#include <memory>
#include <algorithm>
#include <list>
#include <set>
#include <iostream>

class Tag {
public:
    Tag(const std::string &n): name(n) {}

    template <template <typename...> class V, typename E>
    bool isIn(const V<E> &lst) {
        return std::any_of(lst.begin(), lst.end(), [this](const E &t) {
            return t.name == this->name;
        });
    }

private:
    std::string name;
};

typedef std::shared_ptr<Tag> SharedTag;
typedef std::vector<SharedTag> TagList;

int main() {
    Tag t("foo");

    // Set needs some extra bits to work (a `<` operator etc.)
    //std::set<Tag> a = {Tag("foo"), Tag("bar")}; 
    std::vector<Tag> b = {Tag("foo"), Tag("bar")};           
    std::list<Tag> c = {Tag("foo"), Tag("bar")};

    //std::cout << t.isIn(a) << std::endl;
    std::cout << t.isIn(b) << std::endl;
    std::cout << t.isIn(c) << std::endl;
}

(C++) Template to check whether an object is in a vector/array/list/...?

4 Answers4