A few years ago, my colleague and I, we had started Python project in our work. We were both hardcore c++ programmers, so it was a new experience. After learning Python's syntax and writing some code, we had compared ours c++ and Python insights. One nice feature in Python is consistency and its keyword
in. If You want to check if some object
o is in collection
C, You only have to write:
if o in C: # code...
Similarly, iterating over any collection in Python is straightforward:
for e in C: # code...
But in c++, it is complicated. Simple iteration has the form:
for(type_of_collection::iterator it=c.begin(); it!=c.end(); ++it) { /* code... */ }
We have been discussing c++'98 back then, so a new for loop was not in standard yet. Today, in c++11, You can write:
for(auto& o : C) { /* code... */ }
But the other use-case for Python's
in keyword has not been addressed by c++ standard. Of course, You can use standard functions and methods, but it is not as consistent as in Python:
std::find(begin, end, value) // for any range
std::set<k>::find(value), std::map<k v="">::find(key) // for associative collections
std::binary_search(begin, end, value) // for sorted, random access collections
Lack of consistency is some kind of trade-off: by using different signatures You can test whether some object is in collection and obtain iterator to it in one pass over the collection. Once more, c++ chooses efficiency instead of simplicity. ;)
Back then I have thought that creating something similar to Python's
in keyword in c++ would be a nice exercise. Sure, by using such construct ''in a Python's way'' You will sacrifice ability to test if element is in collection and obtain iterator to it in one pass over the collection. I was well aware of that trade-off. One evening spent on coding and prototype was ready. Few days ago, I recalled about my old code and decided to modernize it and show it on this blog. Full source code can be found on
GitHub in
1.0.0 tag. Presented code is still a prototype and shouldn't be used in production code.
First, I will show usage of my solution. Although I could have written some unit tests, I decided not to do it. It is prototype and console output will suffice. The only source file looks like this:
#include <iostream>
#include <array>
#include <vector>
/* And includes for other standard collections: list, set, unordered_set, map, unordered_map */
// Has to go after standard headers...
#include "in.hpp"
template<typename C>
void check(const int e, const C& c) {
std::cout
<< "\t" << e << ((e in c) ? " is" : " is not")
<< " in given collection: " << typeid(c).name() << std::endl;
}
int main() {
std::cout << "Checking raw array:" << std::endl;
int array[] = { 3, 2, 7, 10 };
check(50, array);
check(2, array);
check(10, array);
check(1, array);
std::cout << "Checking vector:" << std::endl;
const std::vector vec = { 3, 2, 7, 10 };
check(50, vec);
check(2, vec);
check(10, vec);
check(1, vec);
std::cout << "Checking map:" << std::endl;
const std::map om = { { 3, "three" }, { 2, "two" }, { 7, "seven" }, { 10, "ten" } };
check(50, om);
check(2, om);
check(10, om);
check(1, om);
/* In the same way other standard collections are tested. */
}
There is a lot of code compared to one tiny line with
in ''keyword'' in function
check, which tests whether element is in collection and prints proper message to standard output. But how the
c++'s in is working?
First of all,
in is defined as a macro in
in.hpp file:
#define in << ::mad::cppin::in_ <<
So, the macro only adds calls of
operator << for object
mad::cppin::in_. This object is instance of empty type
in_type, for which two
operator << are defined:
struct in_type {};
template<typename Element>
details::in_left<Element> operator<<(const Element& e, const in_type) {
return details::in_left(e);
}
template<typename Collection>
details::in_right<Collection> operator<<(const in_type, const Collection& c) {
return details::in_right(c);
}
If the
in_ object is on the right hand side of an binary shift expression, then instance of
details::in_left is returned in which value of other parameter of binary shift is stored. Similarly, if the
in_ object is on the left hand side of binary shift operator, the instance of
in_right class is returned. Both classes are defined as follows:
template<typename Element>
class in_left {
public:
in_left(const Element& e) : e_(e) {}
template<typename Collection> friend
in_impl<Element, Collection> operator<<(const in_left<Element>& l, const Collection& c) {
return in_impl<Element, Collection>(l.e_, c);
}
private:
const Element& e_;
};
template<typename Collection>
class in_right {
public:
in_right(const Collection& c) : c_(c) {}
template<typename Element> friend
in_impl<Element, Collection> operator<<(const Element& e, const in_right<Collection>& r) {
return in_impl<Element, Collection>(e, r.c_);
}
private:
const Collection& c_;
};
} // details
The purpose of above presented classes is to store arguments to the binary shift operators and remember side of binary shift operator, on which parameter was. If parameter was on the left side it is considered as an object to be searched for. If it was on the right hand side, then it is treated as a collection to be search in. Both classes define
operator << for remaining part of the in expression. If the binary shift operator is called, the instance of
in_impl class is returned. It is simple application of
the expression templates idiom. The
in_impl class is shown below:
template<typename Element, typename Collection>
class in_impl {
public:
in_impl(const Element& e, const Collection& c)
: c_(c), e_(e) {}
explicit operator bool() const {
return find_impl(e_, c_);
}
private:
const Collection& c_;
const Element& e_;
};
It only stores its arguments and in context of boolean expression (such as if statement) returns result of function
find_impl call. In this function the magic happens, which enables efficient working with different types of collections. The magic will be described in
part 2.
