Программирование простого объектно-ориентированного графа на C ++ - PullRequest
Новая
       11

Программирование простого объектно-ориентированного графа на C ++

5 голосов
/ 17 марта 2012

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

В качестве упражнения я пытался создать очень простой Graph класс на C ++ с STL. В приведенном ниже коде мой Node объект не компилируется , поскольку закомментированная строка приводит к ссылке на ссылку в STL. 

#include <set>

class KeyComparable
{
public:
  int key;
};

bool operator <(const KeyComparable & lhs, const KeyComparable & rhs)
{
  return lhs.key < rhs.key;
}

class Node : public KeyComparable
{
public:
  // the following line prevents compilation
  // std::set<Node &> adjacent;
};

Я бы хотел сохранить ребра в set (key), потому что это позволяет быстро удалять ребра по ключу. Если бы я хранил list<Node*>, это бы нормально работало, но не позволило бы быстро удалить key.

Если я использую std::set<Node>, изменения, сделанные через ребро, изменят только локальную копию (а не смежную Node). Если я использую std::set<Node*>, я не верю, что оператор < будет работать, потому что он будет работать с самими указателями, а не с памятью, которую они индексируют.

Я подумал об обёртывании ссылок или указателей в другом классе, возможно, в моем классе KeyComparable (в соответствии со связанной страницей, это то, как Boost обрабатывает это).

Кроме того, я мог бы хранить std::list<Node*> и std::map<int, iterator>' of locations in the std :: list`. Я не уверен, что итераторы останутся действительными, когда я изменю список.

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

Как вы думаете, лучший способ решить эту проблему? Большое спасибо.

1 Ответ

9 голосов
/ 17 марта 2012

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

Однако выможно по-прежнему использовать std::set с указателями, если вы предоставите set пользовательский функтор сравнения: 

struct NodePtrCompare {
    bool operator()(const Node* left, const Node* right) const { 
        return left->key < right->key;
    }
};

std::set<Node*, NodePtrCompare> adjacent;

И вы все равно получите быстрое удаление на key, как вы хотите.

...