Python's in in c++ - Part 3: Testing and finding in one pass

In two parts: 1 and 2 I have shown simple implementation of Python's in keyword in c++. I have mentioned, that there are two issues with the presented solution:

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

The second problem requires compile-time check if the collection is sorted or prior knowledge. Both solutions are trade-offs, so I will not tackle this problem.

To deal with the first inefficiency I had merged finder and in_impl template classes into one template class with two specializations and common base class. These changes lead to the removal of find_impl function, which was no longer needed. To obtain iterator type for any collection I have created iterator_type metafunction.

The iterator_type metafunction is simple metafunction, which for arrays return pointer type and for other types, it uses decltype keyword to calculate the type of iterator for given collection type. Users can specialize iterator_type metafunction for their own classes. Source code of that utility metafunction is presented below.

template<typename Collection>
struct iterator_type {
 typedef decltype(std::end(Collection())) type;
};

template<typename T, size_t S>
struct iterator_type<T[S]> {
 typedef T* type;
};

Common base class for specializations of the new in_impl template class is called in_impl_base, and its purpose is to gather common code for both specializations. It is: storing iterators to a position of searched element and end of the collection, calculating whether the element is in the collection and returning position of the element. The source code presented below.

template<typename Collection>
class in_impl_base {
public:
 typedef typename iterator_type<Collection>::type iterator;

 in_impl_base(const iterator& position, const iterator& end)
  : position_(position), end_(end) {}

 explicit operator bool() const {
  return end_ != position_;
 }

 iterator position() const {
  return position_;
 }
private:
 iterator position_;
 iterator end_;
};

Specializations of the in_impl template class differ only by the value of HasMemberFind template parameter and means of obtaining a position of the searched element. If HasMemberFind equals to true, then Collection::find member function is used. In the other case, the std::find algorithm is applied. To simplify type name used in in_left and in_right classes, there is also template alias in_implementation defined. It is used by both above-mentioned classes instead of old in_impl class. Described code is presented below.

template<typename Element, typename Collection, bool HasMemberFind = false>
class in_impl : public in_impl_base<Collection> {
public:
 in_impl(const Element& e, const Collection& c)
  : in_impl_base<Collection>(std::find(std::begin(c), std::end(c), e), std::end(c)) {}
};

template<typename Element, typename Collection>
class in_impl<Element, Collection, true> : public in_impl_base<Collection> {
public:
 in_impl(const Element& e, const Collection& c)
  : in_impl_base<Collection>(c.find(e), std::end(c)) {}
};

template<typename Element, typename Collection> using in_implementation = in_impl<Element, Collection, has_member_find<Collection>::value>;

To test new features, I have changed the check function. By calling print it uses proper specialization of printer template class and prints value stored in the collection under obtained position. The body of the main function remained unchanged. Testing utilities are presented below.

template<typename ValueType>
struct printer {
 printer(const ValueType& val) {
  std::cout << "\t\tvalue = " << val << std::endl;
 }
};

template<typename Key, typename Value>
struct printer<std::pair<Key, Value>> {
 printer(const std::pair<Key, Value>& val) {
  std::cout << "\t\tvalue = (" << val.first << ", " << val.second << ")" << std::endl;
 }
};

template<typename ValueType> void print(const ValueType& val) {
 printer<ValueType> p = val;
}

template<typename C>
void check(const int e, const C& c) {
 if(auto pos = e in c) {
  std::cout << "\t" << e << " is in given collection: " << typeid(c).name() << std::endl;
  print(*pos.position());
 }
 else {
  std::cout << "\t" << e << " is not in given collection: " << typeid(c).name() << std::endl;
 }
}

These are all changes made to make a port of Python's in keyword into c++. It turned to be even slightly more powerful than its Python's predecessor as it can test element existence and obtain its position in one pass over the collection. Modified source code can be found on GitHub in 1.5.0 tag.

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.

Python's in in c++ - Part 1: Expression Templates

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.

My adventures with Ubuntu on Hyper-V. Part 3.

As I was forced to revisit my Hyper-V and Ubuntu configuration earlier this week, today I have decided to try run Ubuntu in fullscreen one more time. After searching the Internet I have found working solution on Ask Ubuntu. On my configuration it required two steps:

1. Installing linux-image-extra-virtual package
   

   sudo apt-get install linux-image-extra-virtual

2. Updating GRUB's configuration file (/etc/default/grub) by changing one line:
   

   GRUB_CMDLINE_LINUX_DEFAULT="quiet splash video=hyperv_fb:1680x1050" 

3. Updating GRUB' configuration by executing the command:
   

   sudo update-grub

After rebooting Ubuntu I can finally use it in fullscreen mode!

Windows Universal Apps

I had plenty of work with my PhD studies and my job so I had not had time to install Visual Studio Express. But on the Build conference, Microsoft showed new Windows' features. Updated Visual Studio can create universal apps for both: Windows 8.1 and Windows Phone 8.1! Although I have not had time to tinker with it long enough, I have managed to create a universal hub app, build it and run on Windows Phone Emulator. And it worked! But after looking into Solution Explorer:

 I have noticed that the Universal Windows Apps are not something entirely new. They are based on an idea, which was known at least from the time when Visual Studio 2013 was published! It was presented on MSDN: share common code and use a separate project for presentation only. Updated Visual Studio mostly eases create of the separate project and shared library and debugging code for the Windows Phone. Although it is not a revolution but an evolution of ideas known for some time, it is welcomed. Maybe it would allow consistent experience across different Windows platforms and faster apps delivery!

My adventures with Ubuntu on Hyper-V. Part 2.

Yesterday I upgraded Windows 8 and installed Visual Studio Express 2013 Update 2 RC. Today I tried to run Ubuntu on Hyper-V. It worked but without an Internet connection... The first thing which I have done, it was to search the Internet to see if upgrading Windows could break something with Hyper-V. I have found nothing...

Searching for problems with Hyper-V itself and changing network setting also was no good. I was ready to give up when I have remembered that I have also installed Visual Studio with Windows Phone Emulator. Running Emulator for the first time created a virtual network adapter and after its creation, I was able to reconfigure Hyper-V and restore Internet connection in Ubuntu. Why without running the emulator it was impossible to configure networking in Hyper-V is still a mystery for me... The installer could have created a network adapter during the installation process and not delay this step to first execution of emulator...