Technique for factoring find like methods?

Question

I am looking for a technique to factor find like methods. The problem is the following. I need a find method on a container that does not need to modify the container contents to do the search. However there should be a const and a non-const version of it since, it could lead to the modification of the container in the case an iterator is returned instead of a const_iterator. In those two cases, the code will be exactly the same, only the accessors will be evaluated to constXXX or XXX and the compiler will do the job. Hoewer from a design and maintaining point of view it does not look smart to have those two methods implemented two times. (And I would really like to avoid using a macro for that...) What I mean is also very well illustrated by that piece of code from the gcc implementation of the stl in stl_tree.h:

template<typename _Key, typename _Val, typename _KeyOfValue, 
  typename _Compare, typename _Alloc>
  typename _Rb_tree<_Key, _Val, _KeyOfValue,
          _Compare, _Alloc>::iterator
  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
find(const _Key& __k)
{
  iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
  return (__j == end()
      || _M_impl._M_key_compare(__k,
                _S_key(__j._M_node))) ? end() : __j;
}

template<typename _Key, typename _Val, typename _KeyOfValue,
       typename _Compare, typename _Alloc>
typename _Rb_tree<_Key, _Val, _KeyOfValue,
          _Compare, _Alloc>::const_iterator
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
find(const _Key& __k) const
{
  const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
  return (__j == end()
      || _M_impl._M_key_compare(__k, 
                _S_key(__j._M_node))) ? end() : __j;
}

You can see that the prototypes of the methods are different but the code written in the implementation is actually the same.

I came up with two possible solutions: the first one is with a const_cast and the other one is with a helper templated struct. I have produced a simple example of those two approaches here:

#include <iostream>
using namespace std;

struct Data
{
  typedef int*       iterator;
  typedef const int* const_iterator;

  int m;

  Data():m(-3){}
};

struct A : public Data
{
  const_iterator find(/*const Key& k */) const
  {
    A *me = const_cast < A* > ( this );
        return const_iterator( me->find(/*k*/) );
  }

  iterator find(/*const Key& k */){
    return &m; }
};

//the second one is with the use of an internal template structure:

struct B : public Data
{

  template<class Tobj, class Titerator>
    struct Internal
   {
      Titerator find( Tobj& obj/*, const Key& k */ ){
        return &(obj.m); }
    };

  const_iterator find( /*const Key& k */ ) const
  {
    Internal<const B, const_iterator> internal;
    return internal.find( *this/*, k*/ );
  }

  iterator find( /*const Key& k */ )
  {
    Internal<B,iterator> internal;
    return internal.find( *this/*, obs*/ );
  }
};


int main()
{
  {
    A a;
    a.find();
    A::iterator it = a.find();
    cout << *it << endl;


    const A& a1(a);
    A::const_iterator cit = a1.find();
    cout << *cit << endl;
  }

  {
    B b;
    b.find();
    B::iterator it = b.find();
    cout << *it << endl;


    const B& b1(b);
    B::const_iterator cit = b1.find();
    cout << *cit << endl;
  }
}

It is probably a very well known problem, and I would like to know if some c++ guru comes up with a good design pattern to fix that problem. And especially I would like to know if someone sees a problem (in particular in terms of performances) with one of those two approaches. As the first one is far more easy to understand I would prefer it, especially after having reading that: Constants and compiler optimization in C++ that seems to allow me to do not fear to write a const_cast and break my performances.

Thank you in advance, cheers,

Manuel

Answer 1

There might not be very good solutions. Both const overloads and iterator/const_iterator are rather clumsy tools to work with.

In the first case, it might be better to let the const version do the work and the non-const version do the casting. That way the compiler would be able to check if your algorithm indeed doesn't modify the container.

Casting a const_iterator to iterator might be a bit awkward, as it would depend on the implementation details. But you could make a private helper to encapsulate this in a single place.

struct A : public Data
{
  iterator find(/*const Key& k */)
  {
    const A *me = this;
    return remove_const_from( me->find(/*k*/) );
  }

  const_iterator find(/*const Key& k */) const{
    return &m; }

    private:
        //could be also static, but in the general case, *this might be needed
        iterator remove_const_from(const_iterator p)
        {
            //in this case just a const_cast
            return const_cast<int*>(p);
        }
};

In the second case, you could reduce the verbosity a bit by using template functions and their ability to deduce at least the argument types.

struct B : public Data
{
    struct Internal //eventually, could be just a free function?
   {
      template<class Titerator, class Tobj>
      static Titerator find( Tobj& obj/*, const Key& k */ ){
        return &(obj.m); }
    };

  const_iterator find( /*const Key& k */ ) const
  {
    return Internal::find<const_iterator>( *this/*, k*/ );
  }

  iterator find( /*const Key& k */ )
  {
    return Internal::find<iterator>( *this/*, obs*/ );
  }
};