[c++]шаблонная функция шаблонного класса

elenangel

Хочу упрятать кастования static_cast и reinterpret_cast внутрь шаблонной функции предка, чтобы в потомке обращаться к полям-указателям предка функциями, возвращающими указатель на потомка и ссылку на указатель на потомка. Необходимо для переиспользования кода дерева - есть базовый узел, есть имплементация дерева у которого тип узла - параметр шаблона. В узле указатели на предков-потомков типа Предок* разумеется, мне нужно их использовать как Потомок*, при этом доступ к ним через геттеры, возвращающие ссылку.
Упрощённый пример кода, который я хочу и который не компилируется:

template <typename T>

class Node

{

public:

    typedef Node<T> Self;

    typedef Self NodeType;

    typedef NodeType* NodePtr;



    T value;



    template <typename PtrType>

    PtrType& next

    {

        return reinterpret_cast<PtrType&>(nextNode);

    }



    template <typename PtrType>

    PtrType next const

    {

        return static_cast<PtrType>(nextNode);

    }

private:

    NodePtr nextNode;

};





template <typename T>

class NodeEx : public Node<T>

{

public:

    typedef NodeEx<T> Self;

    typedef Node<T> Parent;

    typedef Self NodeType;

    typedef NodeType* NodePtr;

    int additionalData;

    void test

    {

        NodePtr t = this, n = 0;

        t->next<NodePtr> = n;

    }

};



int main

{

    NodeEx<double> x;

    x.test;

    return 0;

}

не компилируется вот эта строка, g++

t->next<NodePtr> = n;

говорит



nodetest.cpp:39:26: error: expected primary-expression before ‘)’ token

         t->next<NodePtr> = n;

                          ^

apl13

Хочу упрятать кастования static_cast и reinterpret_cast внутрь шаблонной функции предка, чтобы в потомке обращаться к полям-указателям предка функциями, возвращающими указатель на потомка и ссылку на указатель на потомка.

Maurog

Упрощённый пример кода, который я хочу и который не компилируется:

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

Maurog

дык

в режиме телепатии: http://ideone.com/FZkaYc
поставь слово template перед вызовом шаблонного метода next

elenangel

обновил пост

elenangel

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

Maurog

недавно вот узнал как ссылку на массив из функции возвращать, теперь это

некоторые вещи лучше не знать вообще ~~до самой смерти~~ :grin:

elenangel

ужос



template <typename PtrType>

    PtrType (&children[ChildMax];



...



template <class T>

template <typename PtrType>

PtrType (&RedBlackTreeNode<T>::children[RedBlackTreeNode<T>::ChildMax]

{

    return reinterpret_cast<PtrType (&)[ChildMax]>(nodeChildren);

}

apl13

Чего?

elenangel

синтаксис у плюсов

apl13

Ну, типа, немного здорового бойлерплейта нам не повредит, нет? Сахар для девочек!

Whoman-in-white

а зачем тебе вообще такая сложная схема нужна? не проще ли засунуть все нужные данные в структуру и подставить ее как параметр шаблона, вместо этого непонятного наследования?

Whoman-in-white

можно использовать Curiously recurring template pattern чтобы убрать параметр шаблона из вызова next

 

template <typename T>

class Node

{

public:

    typedef Node<T> Self;

    typedef Self NodeType;

    typedef NodeType* NodePtr;



    T value;

  

    NodePtr& next {

        return nextNode;

    }

  

    NodePtr next const {

        return nextNode;

    }

private:

    NodePtr nextNode;

};



template <typename T, class DerivedT>

class NodeConverter : public Node<T>

{

public:    

    DerivedT*& next {

        return reinterpret_cast<DerivedT*&>(Node<T>::next;

    }

  

    DerivedT next const {

        return static_cast<DerivedT*>(Node<T>::next;

    }

};



template <typename T>

class NodeEx : public NodeConverter <T, NodeEx<T>>

{

public:

    typedef NodeEx<T> Self;

    typedef Node<T> Parent;

    typedef Self NodeType;

    typedef NodeType* NodePtr;

    int additionalData;

    void test

    {

        NodePtr t = this, n = 0;

        t->next = n;

    }

};

Whoman-in-white

code:
template <typename PtrType>
PtrType (&children[ChildMax];
...
template <class T>
template <typename PtrType>
PtrType (&RedBlackTreeNode<T>::children[RedBlackTreeNode<T>::ChildMax]
{
return reinterpret_cast<PtrType (&)[ChildMax]>(nodeChildren);
}

а что здесь написано?

elenangel

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



template <class T, class Compare = std::less<T>, class TreeNodeType = RedBlackTreeNode<T> >

class RedBlackTree;

а потом реюз этого



template <class T, class Compare = std::less<T> >

class OrderStatisticTree : public RedBlackTree<T, Compare, OrderStatisticTreeNode<T> >

при этом



template <class T>

class OrderStatisticTreeNode : public RedBlackTreeNode<T>

{

public:

    size_type& size;

    size_type size const;

private:

    size_type nodeSubtreeSize;

};



template <class T>

class RedBlackTreeNode

{

public:

    typedef T value_type;

    typedef RedBlackTreeNode<T> NodeType;

    typedef NodeType * NodePtr;



public:

    enum NodeColor {Red, Black};

    enum ChildIndex { ChildFirst = 0, Left = ChildFirst, Right = ChildFirst+1, ChildMax = ChildFirst+2 };

public:

    typedef NodePtr ChildrenNodeArray[ChildMax];

private:

    T nodeValue;

    ChildrenNodeArray nodeChildren;

    NodePtr nodeParent;

    NodeColor nodeColor;

...

    T& value;

    const T& value const;



    NodePtr& left;

    NodePtr left const;



    NodePtr& right;

    NodePtr right const;



    NodePtr& parent;

    NodePtr parent const;

...

};

если оставить RedBlackTreeNode как есть, с фукнциями left right parent то при инстанцировании потомка вылезают проблемы с приведением типов указателей в алгоритмах

elenangel

прототип фукнции, возвращающей ссылку на массив из ChildMax указателей типа PtrType
и имплементация, которая эту ссылку кастит из массива из указателей NodePtr nodeChildren[ChildMax]

apl13

Curiously recurring template pattern

Вот я не мог вспомнить, как он называется.

elenangel

Curiously recurring template pattern

вот сто пудов, я еще помнил, что какая-то такая штука была, чтобы из рекурсии вырваться, но не вспомнил как она устроена и как называется.

elenangel

я опять забыл, как тут раскраску синтаксиса прикрутить?

Dasar

Может лучше так?:



template<typename T, typename NodeType>

class _Node

{

public:

    typedef NodeType* NodePtr;



    NodePtr& next

    {

        return nextNode;

    }



    NodePtr next const

    {

        return nextNode;

    }

private:

    NodePtr nextNode;

};



template<typename T>

class Node: public _Node<T, Node<T> >

{

};





template<typename T>

class NodeEx: public _Node<T, NodeEx<T> >

{

public:

    typedef NodeEx<T> Self;

    typedef Node<T > Parent;

    typedef Self NodeType;

    typedef NodeType* NodePtr;

    int additionalData;

    void test

    {

        NodePtr t = this, n = 0;

        t->next = n;

    }

};



int main

{

    NodeEx<double> x;

    x.test;

    return 0;

}

elenangel

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

Whoman-in-white

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

elenangel

std::array

он в с++03 есть? а то надо совместимость блюсти.
и как насчет эффективности?
с выносом функциональности согласен конечно.

Whoman-in-white

совместимость с каким компилятором? так-то это часть нового стандарта, но вроде в студии то ли с 8ой, то ли с 10ой он присутствует, про другие компиляторы не знаю. а зачем с с++03 совместимость?
эффективность такая же, как и у статического массива, динамическая память не выделяется, размер должен задаваться константой на этапе компиляции.
еще, ты планируешь увеличивать количество потомков? в красно-черном дереве вроде это не получится же, не? почему бы структуру не сделать для потомков, вместо массива? или std::pair использовать? или просто возвращать указатель на первый элемент массива?

elenangel

мне это придется собирать для продакшена под древние RedHat'ы, там может быть чуть ли не gcc <3 версии

elenangel

массив, а не два поля left и right использую потому, что все красно-чёрные алгоритмы сокращаются почти в 2 раза за счёт симметрии - вместо двух веток для left и right можно вычислить индексы вначале и использовать одну ветку алгоритма.

elenangel

увеличивать количество потомков? в красно-черном дереве вроде это не получится же, не?

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

Whoman-in-white

ну можно все равно возвращать указатель на первый элемент массива. Размер же известен массива.

elenangel

ну это будет капитуляция перед c++

Serab

пишу на плюсах уже 3 года

good for you

, а всё время натыкаюсь на что-то, чего раньше не знал.

это шутка, да?

Whoman-in-white

капитуляция перед с++ - это тот синтаксис для возвращения массивов, который ты используешь) а вернуть указатель - выглядит вполне нормально. Самое интересное, что дальнейший синтаксис в обоих вариантах будет одинаковый

Maurog

Самое интересное, что дальнейший синтаксис в обоих вариантах будет одинаковый

очень смелое утверждение



namespace Detail

{

  template <typename T, std::size_t N>

  char (&ArraySizeDetector(T (&)[N][N];

}



#define STATIC_ARRAY_SIZE(a) (sizeof(Detail::ArraySizeDetector(a

Whoman-in-white

это опять что значит? :crazy:

блин, короче проще свой array написать, тем более там не нужны же никакие итераторы и т.п., только size и operator[]

apl13

он в с++03 есть? а то надо совместимость блюсти.

Ну вроде, он не настолько сложен, можно самому слепить на коленке, а?

elenangel

да, но зачем?

elenangel

в итоге после всего посоветованного у меня получился вот такой код для узлов деревьев, большое всем спасибо!



template <typename T, class NodeTypeT>

class BaseRedBlackTreeNode

{

public:

    typedef T value_type;

    typedef NodeTypeT NodeType;

    typedef NodeType* NodePtr;

public:

    enum NodeColor {Red, Black};

    enum ChildIndex { ChildFirst = 0, Left = ChildFirst, Right = ChildFirst+1, ChildMax = ChildFirst+2 };

public:

    typedef NodePtr ChildrenNodeArray[ChildMax];

    typedef NodePtr const ChildrenNodeConstArray[ChildMax];

private:

    ChildrenNodeArray nodeChildren;

    NodePtr nodeParent;

    NodeColor nodeColor;

    T nodeValue;

public:

    BaseRedBlackTreeNode( T v = T

                NodePtr l = 0,

                NodePtr r = 0,

                NodePtr p = 0,

                NodeColor c = Black );

    T& value { return nodeValue; }

    const T& value const { return nodeValue; }

    NodeColor& color { return nodeColor; }

    NodeColor color const { return nodeColor; }

    bool isRed const { return nodeColor == Red; }

    bool isBlack const { return nodeColor == Black; }

    void paintItRed { nodeColor = Red; }

    void paintItBlack { nodeColor = Black; }



    NodePtr& left { return nodeChildren[Left]; }

    NodePtr left const {return nodeChildren[Left]; }

    NodePtr& right { return nodeChildren[Right]; }

    NodePtr right const { return nodeChildren[Right]; }

    NodePtr& parent { return nodeParent; }

    NodePtr parent const { return nodeParent; }

    ChildrenNodeArray& children { return nodeChildren; }

    ChildrenNodeConstArray& children const { return nodeChildren; }

};





template <class T>

class RedBlackTreeNode : public BaseRedBlackTreeNode<T, RedBlackTreeNode<T> >

{

public:

    typedef RedBlackTreeNode<T> Self;

    typedef BaseRedBlackTreeNode<T, Self> Parent;

    typedef T value_type;

    typedef RedBlackTreeNode<T> NodeType;

    typedef NodeType * NodePtr;

    typedef typename Parent::NodeColor NodeColor;

public:

    RedBlackTreeNode( T v = T

                NodePtr l = 0,

                NodePtr r = 0,

                NodePtr p = 0,

                NodeColor c = NodeType::Black );

};





template <class T>

class OrderStatisticTreeNode : public BaseRedBlackTreeNode<T, OrderStatisticTreeNode<T> >

{

private:

    typedef OrderStatisticTreeNode<T> Self;

    typedef BaseRedBlackTreeNode<T, OrderStatisticTreeNode<T> > Parent;



public:

    typedef typename Parent::value_type value_type;

    typedef Self NodeType;

    typedef NodeType * NodePtr;

    typedef typename Parent::NodeColor NodeColor;

    typedef typename Parent::ChildIndex ChildIndex;

    typedef size_t size_type;



public:

    OrderStatisticTreeNode( T v = T

                NodePtr l = 0,

                NodePtr r = 0,

                NodePtr p = 0,

                NodeColor c = Parent::Black );



    size_type& size;

    size_type size const;

private:

    size_type nodeSubtreeSize;

};

Maurog

я так понимаю, данные вопросы являются следствием
если вы руками реализуете красно-черное дерево, то вы делаете что-то не так :grin:

скачайте реализацию или заюзайте уже существующую!

Whoman-in-white

да, но зачем?

потому что в используемом тобой синтаксисе для возвращения массивов без поллитры не разобраться

elenangel

я так понимаю, данные вопросы являются следствием запрос на супер-контейнер

именно

если вы руками реализуете красно-черное дерево, то вы делаете что-то не так

Почему же? Контейнер не хуже других, но отсутствует в stl. Я уже даже из него сделал обертку в виде мапы, и заменил в рабочем проекте мапу на свою - пару ошибок выловил ну и убедился что мапа работает - совсместимость на уровне кода оказалась 100%.

скачайте реализацию или заюзайте уже существующую!

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

elenangel

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

Maurog

скопипастить

все отлично копипастится, реализаций пруд-пруди
первая ссылка из гугла
http://kaba.hilvi.org/pastel/pastel/sys/redblacktree.htm
далее просто допиливаем как пожелаем
кстати, очень рекомендую для подобных Node-овых контейнеров поддерживать внешние аллокаторы.с их помощью можно прилично ускорить работу этих контейнеров

elenangel

хм. действительно.
но я гуглил не Augmented Red Black Tree, а просто Red Black Tree и выдача была куда как плачевнее.
не думал, что есть готовая имплементация не просто красно-чёрного дерева, а еще и прямо дополненного как мне надо.
короче пипец. можно было не мучиться.

Serab

ну это будет капитуляция перед c++

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

Whoman-in-white

чет я не понял, вообще в плюсах же запрещено возвращать статические массивы по значению?

elenangel

так я же по ссылке

Оставить комментарий