CODEWITHSUNDEEP
c++
Cesar
Cesar

Reputation: 399

Template to check if vector and map contains value

I'm a beginner in c++ i was searching for templates that could check if a vector / map independent of their data type, contains a given value, I have found these:

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

template< typename container, typename key >
auto map_contains(container const& c, key const& k)
-> decltype(c.find(k) != c.end())
{
    return c.find(k) != c.end();
}

My doubt is, does using templates to do this kind of verification impact performance somehow?

Upvotes: -1

Views: 183

Answers (1)

Ted Lyngmo
Ted Lyngmo

Reputation: 118097

I have found these

Ok, but do analyze them. They are sub optimal and/or plain wrong.

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

This will return true as long as v is not the first value found. It'll also return true if v is not found at all.

A vector, without any other information, is unsorted, which means that contains will have to search from the first element to the last if the value is not found. Such searches are considered expensive.

If you on the other hand std::sort the vector and use the same Comparator when using std::binary_search, it'll have a quicker lookup. Sorting takes time too, though.

template< typename container, typename key >
auto map_contains(container const& c, key const& k) -> decltype(c.find(k) != c.end())
{
    return c.find(k) != c.end();
}

This looks like it may work for types matching the function template. It should use map::contains instead - if it's meant to be used with maps.

Upvotes: 2

Related Questions