Технику для факторинга найти как методы?

Question

Я ищу технику, чтобы найти аналогичные методы.Проблема в следующем.Мне нужен метод find для контейнера, который не должен изменять содержимое контейнера для поиска.Однако должна существовать как const, так и неконстантная версия, поскольку это может привести к модификации контейнера в случае, если вместо const_iterator возвращается итератор.В этих двух случаях код будет точно таким же, только методы доступа будут оценены как constXXX или XXX, и компилятор выполнит эту работу.Как бы то ни было, с точки зрения дизайна и поддержки, не представляется разумным, чтобы эти два метода были реализованы два раза.(И я действительно хотел бы избежать использования макроса для этого ...) То, что я имею в виду, также очень хорошо иллюстрируется этим фрагментом кода из gcc-реализации stl в 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;
}

Вы можете видеть, что прототипы методов разные, но код, написанный в реализации, фактически одинаков.

Я предложил два возможных решения: первое с const_cast, а другоес шаблонной структурой помощника.Я привел простой пример этих двух подходов:

#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;
  }
}

Это, вероятно, очень хорошо известная проблема, и я хотел бы знать, если какой-нибудь гуру с ++ придумает хороший шаблон проектирования, чтобы это исправитьпроблема.И особенно я хотел бы знать, видит ли кто-то проблему (в частности, с точки зрения производительности) с одним из этих двух подходов.Поскольку первый гораздо легче понять, я бы предпочел его, особенно после прочтения: Константы и оптимизация компилятора в C ++ , что, кажется, позволяет мне не бояться писать const_cast и ломать мои выступления.

Заранее спасибо, ура,

Мануэль

Answer 1

Идиоматический способ совместного использования кода между константными и неконстантными функциями-членами с одной и той же реализацией заключается в const_cast в неконстантной:

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

Это работает при условии возврата значения bar является объектом-членом bar, который фактически не является константным, когда вы вызываете неконстантный bar (так что const_cast допустим).

Вы не можете написать неконстантныйверсия и const_cast в константном: это неопределенное поведение.Вы можете удалить constness , только если объект не был константным.

В вашем примере кода, поскольку вы используете голые указатели, вы можете сделать:

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

но как только вы используете более сложные типы итераторов, это не сработает: действительно, нет преобразования стандартных контейнеров 'const_iterator в iterator, так что вы облажались, если вы не используете простые указатели.

Одним из решений является выделение как можно большего, чтобы вы могли const_cast, и создание итератора в самом конце.

Answer 2

Там могут быть не очень хорошие решения. Обе константные перегрузки и iterator/const_iterator - довольно неуклюжие инструменты для работы.

В первом случае, возможно, лучше позволить константной версии выполнять работу, а неконстантную - выполнять кастинг. Таким образом, компилятор сможет проверить, действительно ли ваш алгоритм не изменяет контейнер.

Преобразование const_iterator в iterator может быть немного неудобным, так как это будет зависеть от деталей реализации. Но вы могли бы сделать частного помощника для инкапсуляции этого в одном месте.

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

Во втором случае вы можете немного уменьшить детализацию, используя функции шаблонов и их способность выводить по крайней мере типы аргументов.

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