Writing Portable Code in C++ Using STL

Introduction

The standard of C++ [ISO98] does not specify all the issues in writing portable code. There are some issues, which are left to the implementation of the compiler and library. All of those issues should be handled carefully to make your code portable and this makes writing portable code challenging as well as fun.

One example of this is the size of data type. Standard of C++ doesn't specify the size of data type of built in data type so it is dependent on implementation on specific platform. Therefore any code written on the basis of size of data type is not portable even it is written according to the Standard of language and compiles and runs perfectly fine on some platforms. Let's take a look at this small example to better understand this.

int array[4 - sizeof(int)];

This code is clearly not portable although it may run fine on some platform. If the size of integer is 2 bytes then this code will create the array of 2 integer elements however if the size of integer is 4 bytes then this code is undefined. According to the Standard of C++ "The result of dereferencing a pointer returned as a request for zero size are undefined."

The same situation may arise in case of using standard template library. Standard specify the specification of algorithm but not the implementation detail of the algorithm, so it may be different on different platforms. One such a situation may arise in remove_if algorithm in the standard template library [JOS99].

Details

Lets take a look at first simple example of the usage of remove_if algorithm. This algorithm requires two forward iterators and one predicate.

template<class _FwdIt, class _Pr> inline
_FwdIt remove_if(_FwdIt _First, _FwdIt _Last, _Pr _Pred)

According the Standard of C++ "It is unspecified whether any global function in the C++ Standard Library is defined as inline". So it may or may not be inline on different platforms but this is not our immediate problem.

Predicate can be function object or function pointer. The behavior of remove_if algorithm is slightly different between function object and function pointer although it shouldn't be. Function object can store the state in member variable however function pointer cannot. In case of function pointer predicate, function can maintain its state by taking static variable so simulate the behavior of function object, but you can make two object of function object to store two different states and it is not possible in case of simple functions. And this is the slight difference, which may create different behavior on different implementation.

Here is the example to show the usage of function pointer as a predicate. The Predicate function is used to remove the third element in the vector.

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

bool Remove3rd(int iVal)
{
    return 3 == iVal;
}

int main()
{
    vector<int> vec;

    for (int iIndex = 1; iIndex < 10; ++iIndex)
    {
        vec.push_back(iIndex);
    }

    vector<int>::iterator iter_ = remove_if(vec.begin(), 
             vec.end(), Remove3rd);

    vec.erase(iter_, vec.end());

    copy(vec.begin(), vec.end(), ostream_iterator<int>(cout, " "));

    return 0;
}

The output of this program is

1 2 4 5 6 7 8 9

This is the exactly same output, which we need. Now try to make the same program with function object as a predicate instead of function pointer.

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

template <typename T>
class Remove3rd
{
public:
    bool operator () (T iValue)
    {
        return 3 == iValue;
    }
};

int main()
{
    vector<int> vec;

    for (int iIndex = 1; iIndex < 10; ++iIndex)
    {
        vec.push_back(iIndex);
    }

    vector<int>::iterator iter_ = remove_if(vec.begin(), 
            vec.end(), Remove3rd<int>());

    vec.erase(iter_, vec.end());

    copy(vec.begin(), vec.end(), ostream_iterator<int>(cout, " "));

    return 0;
}

The output of this program is also same. Now lets take the advantage of function object and try to make it more generalized. Currently we can remove only third element from the vector but with the help of one member variable we can make it configurable. And with the help of one more member variable we can store the count how many times operator()() function is being called.

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

template <typename T>
class RemoveNth
{
private:
    T m_tValue;
    T m_iCount;

public:
    RemoveNth(T p_tValue) : m_tValue(p_tValue), m_iCount(0) { }
    bool operator () (T)
    {
        return ++m_iCount == m_tValue;
    }
};

int main()
{
    vector<int> vec;

    for (int iIndex = 1; iIndex < 10; ++iIndex)
    {
        vec.push_back(iIndex);
    }

    vector<int>::iterator iter_ = remove_if(vec.begin(), 
          vec.end(), RemoveNth<int>(3));

    vec.erase(iter_, vec.end());

    copy(vec.begin(), vec.end(), ostream_iterator<int>>(cout, " "));

    return 0;
}

What will be the output of this program? The output of this program depends on the implementation of remove_if algorithm. You might get the output

1 2 4 5 6 7 8 9

or may be you get this output

1 2 4 5 7 8 9

The implementation of remove_if might be calling find_if algorithm first to search element in container, which satisfy the predicate. Its implementation might be something like this.

template<class _FwdIt, class _Pr> inline
_FwdIt remove_if(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
{    
    // remove each satisfying _Pred

    _First = find_if(_First, _Last, _Pred);

    if (_First == _Last)
        return (_First);    // empty sequence, all done

    else
    {    
        // nonempty sequence, worth doing

        _FwdIt _First1 = _First;
        return (remove_copy_if(++_First1, _Last, _First, _Pred));
    }
}

And the signature of find_if algorithm may be something like this

template<class _InIt, class _Pr> inline
_InIt find_if(_InIt _First, _InIt _Last, _Pr _Pred)

Take a look at last parameter of this function predicate is passed by value not by reference in this function and this is exactly required by the standard. Therefore its (predicate's) copy is created which is passed in the find_if algorithm. So this predicate is different than that is passed in the remove_if algorithm. In short one copy of predicate is responsible to remove third element and other copy of predicate is responsible to remove sixth element. Note 9 is not removed from the list means it doesn't remove all elements whose position is multiple of third.

On the other hand if the implementation of remove_if algorithm is something like this then its behavior is different.

template<class _FwdIt, class _Pr> inline
_FwdIt remove_if(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
{    
    // remove each satisfying _Pred

    for (; _First != _Last; ++_First)
        if (_Pred(*_First))
            break;

    if (_First == _Last)
        return (_First);    // empty sequence, all done

    else
    {    
        // nonempty sequence, worth doing

        _FwdIt _First1 = _First;
        return (remove_copy_if(++_First1, _Last, _First, _Pred));
    }
}

Then the output of the program is something like this

1 2 4 5 6 7 8 9

That is equal to the function pointer predicate. The other possible solution is to pass predicate by reference in find_if algorithm, but this is not that standard required. It is not specified in the standard how to implement remove_if algorithm, therefore vendors of library are free to choose any method.

Reference

1. [ISO98] International Standard Programming Language C++ ISO/ICE 14882 1998
2. [JOS99] The C++ Standard Library: A Tutorial and Reference. Nicolai M. Josuttis 1999