Functors with state - 4 (alternative solution using stable_partition)

The is the fourth installment in this series - Functors with state - 1.

Here, what we shall try to do is meet the requirements with a different algorithm. This algorithm does not suffer from the problem that remove_if does as explained in here - Functors with state - 2. But can we be real sure that it is only associated with remove_if and not any of the other algorithms using state maintaining function objects? Well, lets leave that for now.

In this alternate solution, I shall exploit the std::stable_partition algorithm that will help us partition the vector contents based on a predicate test and give the iterator to the element at the partition point. Here is the code that shows how to achieve it.

[CODE]

#include<algorithm>
#include<vector>
#include<iostream>

template<typename T>
struct IsEvenIndex{
               private:
                               mutable/*static*/ typename std::vector<T>::size_type index;
               public:
                               bool operator()(const T& t) const{
                                               if (index%2==0){
                                                               ++index;
                                                               return true;
                                               }else{
                                                               ++index;
                                                               return false;
                                               }
                               }
};

//template<typename T>
//typename std::vector<T>::size_type IsEvenIndex<T>::index=0;

template<typename T>
void PrintVector(const std::vector<T>& t){
               std::cout << std::endl << "Printing vector contents" << std::endl;
               for(typename std::vector<T>::size_type i=0; i<t.size(); ++i){
                               std::cout << t[i] << '\t';
               }
               std::cout << std::endl << std::endl;
}

int main(){
               std::vector<int> myintVector;
               std::vector<int> myanotherintVector;
               for(int i=1; i<=10; ++i){
                       myintVector.push_back(i*10);
               }
               PrintVector(myintVector);
               //std::vector<int>::iterator itend = std::remove_if(myintVector.begin(), myintVector.end(), IsEvenIndex<int>(myotherintVector));
               std::vector<int>::iterator itend = std::stable_partition(myintVector.begin(), myintVector.end(), IsEvenIndex<int>());
               
               PrintVector(myintVector);
               myanotherintVector.assign(itend, myintVector.end());
               myintVector.erase(itend, myintVector.end());
               PrintVector(myintVector);
               PrintVector(myanotherintVector);
}

[OUTPUT]

Printing vector contents
10 20 30 40 50 60 70 80 90 100
Printing vector contents
10 30 50 70 90 20 40 60 80 100
Printing vector contents
10 30 50 70 90
Printing vector contents
20 40 60 80 100


Also, note here that we don't use a static state variable anymore. Just because of the fact that stable_partition does not suffer from the issue that remove_if suffers from due to the call to find_if, passing the predicate by value.

There is another way where we can improve our original code with the static state variable. To remove the static declaration what we do is change the predicate a little as follows:

[CODE]

template<typename T>
struct IsEvenIndex
{
        private:
                 mutable typename std::vector<T>::size_type index;
                 typename std::vector<T>::size_type & index_ref;
                 std::vector<T>& refVec;
        public:
                 bool operator()(const T& t) const
                 {
                          if ( 1 & index_ref++ ) // if it is odd, increment after statement
                          {
                                   return false;
                          }
                          else
                          {
                                   refVec.push_back( t );
                                   return true;
                          }
                 }

        explicit IsEvenIndex(std::vector<T>& vec)
        : refVec(vec), index(0), index_ref( index )
        {}
};

Testing is an exercise and dissecting the logic is what I shall leave for my blog readers and close the topic here with a few references:

1. Codeguru thread where I came across this problem
2. Article that suffices the reasoning
3. Herb Sutter - Extending the standard library

Quiz : function pointers as template arguments

Yesterday, I came across a piece of template code that took me a little by surprise (because I had not come across something like this before) but I was able to put my reasoning through. I will share the code first:

[CODE]

#include <iostream>

template<typename T>
void foo(const T&)
{
               std::cout << "const";
}

template<typename T>
void foo(T&)
{
               std::cout << "non-const";
}

void bar() { }

int main()
{
               foo(bar);
}

The question was - what would the program print? Will the argument "bar" resolve as a parameter to the first template having argument type "const F&" or to the second template having non-const argument type "F&"?

The easiest way to check for the resolution is to ask for explicit template instantiation of the "foo" function template. How? Here is how:

[CODE]

int main()
{
               typedef void (*f_ptr)(); //create a typedef for functions like bar
                                                               //taking no arguments and having return type as void.
               foo<const f_ptr>(bar); //1
               foo<f_ptr>(bar); //2
}

After that, just remove one of the "foo" templates. So, the code to check for compilation is this:

[CODE]
#include<iostream>

template<typename T>
void foo(T&)
{
               std::cout << "non-const";
}

void bar() { }

int main()
{
               typedef void (*f_ptr)(); //create a typedef for functions like bar
                                                               //taking no arguments and having return type as void.
               foo<const f_ptr>(bar); //1
               foo<f_ptr>(bar); //2
}


If you removed the second template, code compiles fine. But if you kept the second one and removed the first one, you will see that the compilation fails for mis-match in the argument type in statement "//2".

Problem solved. Isn't it? What does this tell about the argument "bar" ? It tells that it is a constant. And hence the call in the initial sample code would resolve to the template instance having the argument type declared const. It is in a way similar to any other type constants, for example 5, 100, 2000 are integral constants, they are literals. And when you declare something as say int i; here i is a variable that can be modified. but 5, 100, or 2000 cannot be. In our initial code, both the templates were capable of instantiating the right function for the argument. In both's presence, the argument match has to be exact and hence instantiation happens from the const one but in its absense the instantiation can happen even with the non-const one as the call can help the template to instantiate over type const f_ptr instead of just f_ptr (which is the case for the const one).

Functions pointers when being passed by taking the address of the function directly is a value of const function pointer type.