C++: const-методы класса. Как не дублировать код

Из последнего задания: "особое внимание уделить избавлению от copy-paste, как, например, в методах "find" из HashImpl".

Методов find в классе HashImpl, реализующем хранение произвольных данных по хеш-ключам, есть два:

1) const Item* find (KeyType key) const
2) Item* find (KeyType key)

Первый вариант будет вызываться для константного объекта, а второй - для неконстантного. Проблема следующая: код этих методов звучит не просто как "return & mHash[key]", а реализует какой-никакой, а все же алгоритм поиска. Да и хешей там два - первичный и вторичный, что еще немножко усложняет ситуацию. Внутри методов используются всякие вспомогательные указатели на внутренние данные класса, которые в константном методе должны быть константными, а в неконстантных - соответственно, неконстантными.

Отсюда формулируем вопрос: как избежать дублирования кода для константной (const) и неконстантной версий одного и того же метода, реализующего нетрививальный алгоритм? Примечание: константный объект может пользоваться только методами, объявленными с квалификатором const, и не может использовать неконстантные указатели и неконстантные ссылки на свои данные - в частности, не может их возвращать.

Нарытые варианты решения:

1. Вызывать константный метод из неконстантного.
Чем плох: константный метод вернет константный указатель, с которого затем придется снимать константность, используя const_cast, что небезопасно и отстой. Код будет выполняться на целевой платформе (это такой девайс с черт-знает каким процессором и черт-знает какой организацией памяти). Вполне вероятно, что константный объект окажется в физически защищенном от записи сегменте памяти, и, при попытке записи чего-либо по его адресам, мы получим жопу. Не наш метод.

2. Объявлять хеш-таблицы как mutable, чтобы иметь право изменять их в константном методе
Чем плох: mutable - грязный хак. Если программист серьезно размышляет об использовании mutable - ему надо выйти проветриться (цитатирую Мишу Нореля). Короче, тоже не наш метод.

3. Использовать неконстантные указатели "через один указатель"
Объясняю популярно. Если в классе Foo есть поле mData типа Bar, то из константного метода нельзя сделать return & mData.getItem(key). Но зато если эту же mData объявить как Bar*, выделяя память для него в конструкторе, то из константной функции можно сделать return & (mData->getItem(key)).
Чем плох: не удовлетворяет требованиям к классу: необходимо использовать статическую инициализацию. И класс-то вовсе не класс, а шаблон, один из параметров которого - размер хеш-таблицы. Опять облом.

4. Хранить рядом с данными указатель на них, и возвращать item через него (см. метод 3)
Ну, типа объявить в классе Foo два поля: Bar mData и Bar* mDataPtr, присвоив последнему mDataPtr = & mData в конструкторе.
Чем плох: См., во-первых, метод 1. Если объект будет размещен в защищенной от записи памяти, то при записи по указателю mDataPtr будет жопа. Во-вторых, sizeof всех объектов увеличится на 4 байта. Если объектов будет миллион, то мы проебем 4 метра памяти, что для целевой платформы может быть нехорошо.

5. Написать еще одну константную функцию для поиска
Да-да, пишем третью функцию:

void findHadler (KeyType key, KeyType & resKey) const

Такой метод можно вызывать из обоих версий find. Он вернет ключ, по которому хранится искомый item. А потом константный find может вернуть const Item* p = & mData[resKey], а неконстантный - Item* p = & mData[resKey].
Чем плох: Добавляются лишние вызовы, немножко падает производительность, дыр-пыр-тыр, бла-бла-бла. Все это, по сравнению с проблемами предыдущих вариантов - суть мелочи, поэтому я остановился именно тут.

Итого: я не люблю C++, среди много-прочего, как раз за такие вот мансы. Ну, типа, придумали мы слово const - и теперь ловим сопутствующие проблемы. Зато (sic!) мы получаем неибацца свободу выбора решений таких проблем...

А свободу, как известно, не купишь :)