Python's in in c++ - Part 2: Template Specializations

In part 1 I have presented expression templates which allowed creation of Python's in construct in c++. In this post I will present some template machinery, which made my in implementation quite efficient.

In part 1, it was shown that finding element in collection is done by find_impl function. Its code is presented below:

template<typename Element, typename Collection>
bool find_impl(const Element& e, const Collection& c) {
 return finder<Element, Collection, has_member_find<Collection>::value>()(e, c);
}

It only creates instance of finder template class and calls its function call operator. The finder class is parametrized by:

• type of object searched in collection
• type of collection
• boolean flag, whether collection has efficient member function find

If given collection supports efficient lock-up, then its member function find is used by proper specialization of finder template. In other case, std::find algorithm is used. Code for both specializations is presented below:

template<typename Element, typename Collection, bool HasMemberFind = false>
class finder {
public:
 bool operator()(const Element& e, const Collection& c) const {
  using namespace std;
  return end(c) != find(begin(c), end(c), e);
 }
};

template<typename Element, typename Collection>
class finder {
public:
 bool operator()(const Element& e, const Collection& c) const {
  using namespace std;
  return end(c) != c.find(e);
 }
};

The tricky part was to create has_member_find template, because it has to deal with concrete types and templates - for instance standard collections. For concrete types has_member_find is a metafunction always returning false. User can define specialization for its own concrete types with efficient find member function. For templates has_member_find inherits is value from template_has_member_find template, which handles templates and for most of them is also a metafunction returning false. The template_has_member_find template is specialized for all standard associative containers to be a metafunction returning true. Code for both templates is presented below:

// Has a template for collection member function find?
template<template<typename...> class TCollection>
struct template_has_member_find : std::false_type {};

template<>
struct template_has_member_find<std::set> : std::true_type {};

template<>
struct template_has_member_find<std::multiset> : std::true_type {};

template<>
struct template_has_member_find<std::map> : std::true_type {};

template<>
struct template_has_member_find<std::multimap> : std::true_type {};

template<>
struct template_has_member_find<std::unordered_set> : std::true_type {};

template<>
struct template_has_member_find<std::unordered_multiset> : std::true_type {};

template<>
struct template_has_member_find<std::unordered_map> : std::true_type {};

template<>
struct template_has_member_find<std::unordered_multimap> : std::true_type {};


// Has a concrete type member function find?
template<typename Collection, typename... Args>
struct has_member_find : public std::false_type {};

template<template<typename...> class Collection, typename... Args>
struct has_member_find<Collection<Args...>> : template_has_member_find<Collection> {};

These are all building blocks, which were used to port Python's in keyword into c++. There are two main problems with presented solution:

1. After testing if some object is in collection, You have to make second pass over collection to find searched object's position.
2. If collection is a random access and it is sorted, searching can be done more efficient by std::binary_search algorithm.

The first issue will be addressed in the third part of this miniseries.

Presented code can be found on GitHub in 1.0.0 tag.