Как правильно организовать непростой шаблон двоичного дерева?

[nowaalex]

Прошу только минимальных разъяснений или файлов .h.
Задача такая:

template <typename T, ( функция, которая будет сортировать элементы по указанному признаку ), ( модель аллокации памяти )>
class Tree
{
      тут insert, конструктор, деструктор и итератор;
};

typename T - тип данных, который будет храниться в дереве.
следующее - к примеру, если мы хотим добавлять в дерево строки, то это, к примеру, будет что-то типа

struct eqstr
{
  bool operator()( const char* s1, const char* s2 ) const
  {
    return !strcmp( s1, s2 );
  }
};

Если символы, то просто > или < вместо strcmp.
И модель аллокации памяти:
1 вариант:
Самый простой: когда мы вообще не знаем, сколько элементов будет в дереве. Тоесть САМАЯ ОБЫЧНАЯ организация, которая есть везде в интернете.
2 вариант: Дерево как массив, а роль указателей *left и * right играют числовые индексы. Мы знаем, сколько МАКСИМУМ элементов будет в дереве и поэтому можем расположить дерево в памяти "одним куском".

Вопрос: я очень приблизительно слышал про traits and policies и вообще про то, как такое можно сделать; подскажите, пожалуйста, хоть немного. Решения "в лоб" с кучей if-else ов и булевыми переменными в шаблоне, пожалуйста, не предлагайте.

[still_alive]

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

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

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

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

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

[pu4koff]

Всё это реализовано в STL, почитайте про него, посмотрите как там всё это организовано и реализовано и вперёд.

[nowaalex]

И еще один маленький вопрос)

Когда дерево хранит char или int, к примеру, операция вставки делается просто: ( *elem )->data = data. А если мы хотим передать char *, под который нужно выделить память? Как тогда быть?

To pu4koff
Дело в том, что это дерево потом будет функционально расширяться и там будут такие методы, каких нету в std::set или std::map. Поэтому свое создать необходимо.

template<typename T, class Functor>
bool Tree<T, Functor>::insert( const T& element )
{
    __Tree ** elem = &Root;
    Functor functor;

    while( *elem )
    {
        switch( functor( element, ( *elem )->element ) )
        {
        case -1:
            return false;
        case 0:
            elem = &( ( *elem )->left );
            break;
        case 1:
            elem = &( ( *elem )->right );
            break;
        }
    }

    ( *elem ) = new( __Tree );
    ( *elem )->element = element;
    ( *elem )->left = ( *elem )->right = NULL;
    __size++;

    return true;
}

Такой код работает с char *, но корректен ли он?

[still_alive]

Сообщение от pu4koff

Всё это реализовано в STL, почитайте про него, посмотрите как там всё это организовано и реализовано и вперёд.

Из STL, конечно многое можно почерпнуть. Но все не так просто. Как думаете, почему map построено только на сбалансированных двоичных деревьях и не предоставляет хэш-таблиц? Приходится использовать не совсем стандартизированные вещи из boost и ждать С++0х.

Сообщение от nowaalex

Когда дерево хранит char или int, к примеру, операция вставки делается просто: ( *elem )->data = data. А если мы хотим передать char *, под который нужно выделить память? Как тогда быть?

А зачем передавать char*? Не надо этого делать. Для массивов и строк нужны отдельные классы, вот их объекты и передавать. А голые char*, int* и тд чреваты ошибками.
Вы же не хотите потом копаться в исключениях, ошибках доступа к памяти, не говоря уже о возможных утечках и ужасном коде? http://liveworkspace.org/code/ae6726...02bebcae31010e
Не стоит встраивать поддержку таких типов, которые требуют где-то изменения логики работы. То есть работаем с char* так же, как если бы это был просто char.

[pu4koff]

Сообщение от still_alive

Из STL, конечно многое можно почерпнуть. Но все не так просто. Как думаете, почему map построено только на сбалансированных двоичных деревьях и не предоставляет хэш-таблиц? Приходится использовать не совсем стандартизированные вещи из boost и ждать С++0х.

Я С++ в целом и STL в частности считаю ужасными, корявыми костылями и потому не вижу причин в том, чтобы не добавить еще какие-то свои костыли
Еще про шаблоны интересно и не совсем понятно пишет Александреску (книга называется что-то вроде "Современное программирование на С++").

[nowaalex]

To pu4koff
А сначала посоветовали)))

Не хочу развивать холивар, но всё же:
Почему вы не любите C++ и STL( согласен, последний не всегда можно использовать и бывает удобнее написать что-то своё ) и любите ли Вы чистый С?

Если же нет, то что Вы любите?

[pu4koff]

Сообщение от nowaalex

To pu4koff
А сначала посоветовали)))

Ну так STL сделан в тру (истинном) С++ стиле и на него одно время все равнялись. Сейчас многие хотят от плюсов больше, чем он может предложить и от этого появляется куча проблем.

Сообщение от nowaalex

Не хочу развивать холивар, но всё же:
Почему вы не любите C++ и STL( согласен, последний не всегда можно использовать и бывает удобнее написать что-то своё ) и любите ли Вы чистый С?

Если же нет, то что Вы любите?

В настоящий момент мне не нравится ни один из языков программирования, ни одна ОС и я убеждён, что на рынке программного обеспечения творится ужас, а под видом удобных программ подсовывают не пойми что. Большую часть времени программисты тратят на борьбу с языком, ОС, библиотеками,... в миллионный раз пишут какие-то непонятные велосипеды, конвертеры для скрещивания чужих велосипедов, ... Я за другую концепцию всего и вся. Поэтому я в данный момент программистом и не работаю

[still_alive]

Сообщение от pu4koff

Я С++ в целом и STL в частности считаю ужасными, корявыми костылями и потому не вижу причин в том, чтобы не добавить еще какие-то свои костыли

Как показывает практика, в этом мнении вы не одиноки

Сообщение от pu4koff

Еще про шаблоны интересно и не совсем понятно пишет Александреску (книга называется что-то вроде "Современное программирование на С++").

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

Сообщение от pu4koff

В настоящий момент мне не нравится ни один из языков программирования

Даже из функциональных?)
Лично я когда пишу на С++ - я получаю удовольствие от процесса программирования. А когда на Python и Erlang - от быстрого и ненапряжного решения задачи) Если смешать - будет действовать как водка с пивом

[pu4koff]

Сообщение от still_alive

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

Я пожалуй несколько неправильно выразился... Понятно оно понятно, на уровне рассматриваемых примеров всё понятно, но вот с самостоятельным проектированием при решении своих задач и выстраиванием описанных "красивостей" у меня лично не сложилось на момент прочтения его книги. Но обучаемость - это конечно штука индивидуальная, а книга в целом интересная и полезная, собственно поэтому я про неё и вспомнил.

Сообщение от still_alive

Даже из функциональных?)

Ой... С функциональными языками у меня вообще как-то всё тяжко. Не проникся я их философией, мышление постоянно на уровне переменных, объектов, а с этим грузом далеко не уедешь. Жду вот выхода мозга из спячки, кучу планов настроил, в том числе и погружение в функциональные языки.

Сообщение от still_alive

Лично я когда пишу на С++ - я получаю удовольствие от процесса программирования.

Я по началу тоже с горящими глазами писал классы, какие-то иерархии выстраивал. А потом мне тупо надоело думать над банальными вещами (как, например, возврат массива из метода, чтобы не завязываться на STL или другую библиотеку) и написание каких-то непонятных посредников между библиотеками, чтобы их подружить между собой, т.к. у каждой библиотеки свой строковый тип, свои правила работы с исключениями и т.д. и т.п. Столько лет языку, а стройности нет, не оттачивается он с годами, а засоряется. Старые косяки не убираются, а добавляются новые фичи, а с ними и грабли.

Сообщение от still_alive

Если смешать - будет действовать как водка с пивом

Я по этой причине хочу Nemerle "пощупать", да всё руки не доходят. Он правда не на базе С++, а C# за основу взят, но это тоже интересно
ЗЫ. Это всё конечно лирическое отступление, надеюсь модераторы сильно за это не обидятся