Technique for factoring find like methods?

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

The idiomatic way to share code between const and non-const member functions with the same implementation is to const_cast in the non-const one:

struct foo
{
    const int* bar() const;
    int* bar() 
    {
        const int* p = static_cast<const foo*>(this)->bar();

        // Perfectly defined since p is not really
        // const in the first place
        return const_cast<int*>(p);
    }
};

This works provided the return value of bar is a member object of bar, which is in fact not const when you call the non-const bar (so that const_cast is legal).

You cannot write the non-const version and const_cast in the const one: this is undefined behavior. You are allowed to remove constness only if the object was not const in the first place.

In your example code, since you use bare pointers, you can do:

struct A : public Data
{
  const_iterator find(const Key& k) const
  {
      // The real implementation of find is here
  }

  iterator find(const Key& k)
  {
      // Not the other way around !
      const_iterator p = static_cast<const A*>(this)->find(k);
      return const_cast<iterator>(p);
  }
};

but as soon as you use more complex iterator types, this won't work: indeed, there is no conversion from standard containers' const_iterator to iterator, so you're screwed, unless you use plain pointers.

One solution is to factor out the most you can so that you can const_cast, and manufacture an iterator at the very end.

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*/ );
  }
};