Wednesday, February 14, 2007

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

1 comment:

Anonymous said...

For white pages, tutorials, certifications and rapidshare links on C++

please visit


Rapidshare C ++ tutorial links

or

C ++ tutorials