Блог

Моя проблема заключается в следующем. Я изучаю C , написав библиотеку graph, и хочу использовать как можно больше общих методов программирования; следовательно, ответ на мой вопрос с помощью «use BOOST» мне не поможет; на самом деле, я пытался просмотреть код BOOST в поисках ответа на свой вопрос, но это был унизительный опыт, поскольку я даже не могу понять, где определены определенные функции; просто слишком высокий уровень C для обучения на нем на моем уровне.

Тем не менее, моя библиотека оформлена следующим образом:

 class edge { ... };

template <class edge_T>
class node { ... };

template <class edge_T, class node_T>
class graph { ... };
  

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

 template <class T>
class weighted_edge : public edge {
   public:
     T weight;

   ...
};
  

Проблема сейчас в том, что я хочу реализовать алгоритм на этой структуре, который вычисляет кратчайшее расстояние между двумя вершинами. Я мог бы легко написать два из них, один для взвешенных ребер и один для невзвешенных, но изменение незначительное: один получит доступ к полю-члену weighted_edge (или производным классам), а другой примет унитарный вес.

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

Одно из решений — использовать функцию-член edge::get_weight() , которая возвращала бы вес (или ‘1’ в невзвешенном случае), но это вынудило бы меня использовать определенный тип веса для невзвешенного класса edge, поэтому это странно пахнет. Я имею в виду, что шаблон должен быть

 template <class T>
class edge {
   public:
     ...
     virtual T get_weight(void) { return T(1); } 
}
  

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

BGL использует get() функцию для получения веса; Я мог бы написать функцию, которая возвращает 1 или weight в edge_T зависимости от edge , но меня беспокоит то, что происходит, когда один выводится из weighted_edge или,,,? Если кто-то пишет:

 template <class T>
inline T get_weight(edge amp; e) { return T(1); }

template <class T>
inline T get_weight(weighted_edge amp; e) { return T(e.weight); }
  

что произойдет, если передать производный класс? Существует ли механизм C , который выбирал бы «более близкий» базовый класс из этих двух?

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

 template <class T>
inline T get_weight(edge const amp; e)
{ return T(1); }

template <class T>
inline T get_weight(weighted_edge const amp; e)
{ return T(e.weight); }
  

Таким образом, когда я пишу алгоритм кратчайшего пути, он может запрашивать вес любого из этих двух классов или любых производных от них, что важно для меня, потому что позже я, возможно, захочу добавить свойства к базовым классам ребер (например, цвета и т.д.). Следовательно, Когда я пишу

 class my_edge : public edge { ... };

my_edge e;
  

и при использовании get_weight(e) я получу поведение для невзвешенного края. Создание шаблонов для типа edge здесь не помогло бы, потому что оно не смогло бы использовать предписанное поведение для всех классов, происходящих от edge , и отличать это от поведения для weighted_edge .

_{Заранее: я предполагаю, что вы подумали о создании getWeight() виртуального метода в базовом edge классе (и заставили реализацию по умолчанию возвращать 1). Я осведомлен об ограничениях гибкости этого подхода, просто хотел проверить.}

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

Обычный способ get_weight выбрать правильную реализацию — использовать специализацию шаблона (обратите внимание, что показанный вами код специализируется на типе возвращаемого значения; по определению, этот тип никогда не будет выведен компилятором):

 namespace detail
{
    template <class Edge> struct get_weight_impl;

    template <> struct get_weight_impl<edge>
    {
        typedef typename result_type int;

        result_type operator()(const edgeamp; e) const
            { return result_type(1); }
    };

    template <> struct get_weight_impl<weighted_edge>
    {
        typedef typename result_type int;

        result_type operator()(const weighted_edgeamp; e) const
            { return result_type(e.weight); }
    };
}
  

Обновление 1 Вы могли бы использовать result_of<edge::weight> (boost / TR1) или decltype(edge::weight) (C 0x), чтобы избежать жесткого кодирования result_type typedefs. Это было бы истинной индукцией.

Обновление 2 Чтобы получить перегрузку для weighted_edge constamp; «обслуживания» производных типов ребер, а также применить немного магии type_trait:

http://ideone.com/AqmsL

 struct edge {};
struct weighted_edge : edge          { virtual double get_weight() const { return 3.14; } };
struct derived_edge  : weighted_edge { virtual double get_weight() const { return 42; } };

template <typename E, bool is_weighted>
struct edge_weight_impl;

template <typename E>
struct edge_weight_impl<E, false>
{
    typedef int result_type;
    int operator()(const Eamp; e) const { return 1; }
};

template <typename E>
struct edge_weight_impl<E, true>
{
    // typedef decltype(E().weight()) result_type; // c  0x
    typedef double result_type;

    result_type operator()(const Eamp; e) const 
    { 
        return e.get_weight();
    }
};

template <typename E>
    typename edge_weight_impl<E, boost::is_base_of<weighted_edge, E>::value>::result_type 
        get_weight(const Eamp; e)
{
    return edge_weight_impl<E, boost::is_base_of<weighted_edge, E>::value>()(e);
}

int main()
{
    edge e;
    weighted_edge we;
    derived_edge de;

    std::cout << "--- static polymorphism" << std::endl;
    std::cout << "edge:t"          << get_weight(e) << std::endl;
    std::cout << "weighted_edge:t" << get_weight(we) << std::endl;
    std::cout << "derived_edge:t"  << get_weight(de) << std::endl;

    // use some additional enable_if to get rid of this:
    std::cout << "bogus:t"         << get_weight("bogus") << std::endl;

    std::cout << "n--- runtime polymorphism" << std::endl;

    edge* ep = amp;e;
    std::cout << "edge:t"          << get_weight(*ep) << std::endl;
    weighted_edge* wep = amp;we;
    std::cout << "weighted_edge:t" << get_weight(*wep) << std::endl;
    wep = amp;de;
    std::cout << "bogus:t"         << get_weight(*wep) << std::endl;
}