Представление графа с помощью смарт-указатели. Реализация алгоритма Kosaraju по


Ближайшие из Java-фон, и будучи довольно новыми для C++, а также анализ кода, я пытаюсь привыкнуть к концепции с++11/14. Я читал современные эффективные с++ Скотт Мейерс, чтобы усвоить понятия, но я хотел бы услышать обратную связь о выполнении(ы) ниже. Я хочу также добавить, что алгоритм нахождения сильно связных компонент произведений, и я испытал его. Однако, прежде чем двигаться дальше, я хочу убедиться, что я пишу правильный код на C++.

Класс вершинного:

enum status:int{unvisited,visiting,visited};
template <class T>
class vertex
{
    using vertex_sp = std::shared_ptr<vertex<T>>;
    using vertex_wp = std::weak_ptr<vertex<T>>;
    using neighbors = std::vector<vertex_wp>;
    public:
        static int time;

        explicit vertex(T l) : label_(l), pre_(0), post_(0), status_(status::unvisited) {}
        const T& get_label() const { return label_; }
        const neighbors& get_neighbors() const { return neighbors_; }
        bool is_unvisited() const { return status_ == unvisited; }
        bool is_visiting() const { return status_ == visiting; }
        bool is_visited() const { return status_ == visited; }
        int get_pre() const { return pre_; }
        int get_post() const { return post_; }

        void add_neighbor(const vertex_sp& v) { neighbors_.emplace_back(v); }
        void set_unvisited() { status_ = unvisited; }
        void set_status(status s)
        {
            status_ = s;
            if (s == visiting) pre_ = ++time;
            if (s == visited) post_ = ++time;
        }

        friend std::ostream& operator<<(std::ostream& out, const vertex_wp& v) { return out << v.lock()->label_; }
        friend std::ostream& operator<<(std::ostream& out, const vertex_sp& v) { return out << v->label_; }

        template <class E> friend class graph;
        template <class E> friend class edge;
     private:
        T label_;
        neighbors neighbors_;
        int pre_, post_;
        status status_;
};

Edge Класса:

template <class T>
class edge
{
    using vertex_sp = std::shared_ptr<vertex<T>>;
 public:
    edge(const vertex_sp& from, const vertex_sp& to, const int cost=1): 
    from_(from), to_(to), cost_(cost) {}
    const vertex_sp& get_from() const { return from_; }
    const vertex_sp& get_to() const { return to_; }
    int get_cost() const { return cost_; }
    friend std::ostream& operator<<(std::ostream& out, const edge& v) { return out << "(" << v.from_ << "," << v.to_ << "," << v.cost_ << ")"; }

     template <class E> friend class graph;
 private:
     const vertex_sp& from_;
     const vertex_sp& to_;
     const int cost_;
};

Графа Класс:

enum class type:int{directed,undirected};

template <class T>
class graph
{
     using vertex_sp = std::shared_ptr<vertex<T>>;
     using vertices  = std::unordered_set<vertex_sp>;
     using edges     = std::vector<edge<T>>;
     using adj_list  = std::unordered_map<vertex_sp, edges>;
public:
     graph() = default;
     explicit graph(const type t=type::undirected): type_(t) {}

     const vertices& get_vertices() const { return vertices_; }
     const edges& get_edges() const { return edges_; }
     const edges& adj(const vertex_sp& v) const { return adj_.at(v); }
     const adj_list& get_adj_list() { return adj_; }

     void add_edge(const vertex_sp& from, const vertex_sp& to, const int cost=1)
     {
         from->add_neighbor(to);
         vertices_.insert(from), vertices_.insert(to);
         edges_.emplace_back(from, to, cost);
         adj_[from].emplace_back(from, to, cost);

         if (type_ == type::undirected)
         {
            to->add_neighbor(from);
            edges_.emplace_back(to, from, cost);
            adj_[from].emplace_back(to, from, cost);
         }
      }

     std::unique_ptr<graph<T>> get_transpose()
     {
        for (const auto& v : vertices_) { v->neighbors_.clear(); }
        auto graph_t = std::make_unique<graph<T>>(type_);
        for (const auto& edge : edges_)
        {
            if (edge.from_ && edge.to_)
            {
                edge.from_->set_status(unvisited);
                edge.to_->set_status(unvisited);
                graph_t->add_edge(std::move(edge.to_), std::move(edge.from_), edge.cost_);
            }
         }
         return graph_t;
      }
private:
     vertices vertices_;
     edges edges_;
     adj_list adj_;
     type type_;
};

Реализация Kosaraju:

template <class T>
int vertex<T>::time = 0;

template <class T>
void time_stamps(const vertex_sp<T>& vertex_ptr, stack<vertex_sp<T>>* s)
{
    auto *u = vertex_ptr.get();
    u->set_status(visiting);

    for (const auto& v : vertex_ptr->get_neighbors())
    {
        auto v_sp = v.lock();                                               
        if (v_sp->is_unvisited())                                           
        {
           time_stamps(v_sp, s);
        }
     }

     u->set_status(visited);
     s->push(vertex_ptr);
   }

template <class T>
void dfs(const vertex_sp<T>& vertex_ptr, vector<T>* partial)
{
    auto *u = vertex_ptr.get();
    u->set_status(visiting);
    partial->emplace_back(u->get_label());

    for (const auto& v : vertex_ptr->get_neighbors())
    {
        auto v_sp = v.lock();
        if (v_sp->is_unvisited())
        {
            dfs(v_sp, partial);
        }
     }

     u->set_status(visited);
 }

template <class T>
vector<vector<T>> get_scc(const graph_up<T>& graph_ptr)
{
    vector<vector<T>> sccs;
    stack<vertex_sp<T>> times;
    for (const auto &v : graph_ptr->get_vertices())
    {
        if (v->is_unvisited())
        {
            time_stamps(v, &times);
        }
     }
    auto graph_t_ptr = graph_ptr->get_transpose();

    while (!times.empty())
    {
        const auto& curr = times.top();
        times.pop();

        vector<T> partial;
        if (curr->is_unvisited())
        {
            dfs(curr, &partial);
            sccs.emplace_back(partial);
        }
     }
     return sccs;
}

Моими главными задачами являются:

  1. Я пишу на C++, как Java-код.
  2. Я использую общий указатель, где уникальный указатель будет достаточно. Я думал об этом некоторое время, прежде чем использовать общий указатель и выбрал общий указатель, потому что я держу несколько указателей на вершины, поскольку они копируются в несколько контейнеров и, таким образом, имея в долевой собственности.
  3. Я не эффективной реализации графа, я читал, что СТД::Шаг 0 накладные расходы, поэтому я решил использовать, что вместо того, чтобы создавать дополнительные копии.
  4. Будучи новой для перегрузки операторов, мой использует выше правильно? Я правильно используя ключевое слово friend?
  5. Какие советы у вас у всех над улучшением стиле C++ в целом, в основном о том, как я могу улучшить эффективность или более важно понимать, когда динамическое распределение необходимо и для простых объектов достаточно (я хочу, чтобы я не злоупотребляя динамическое выделение памяти).

Заранее спасибо!



591
1
задан 20 марта 2018 в 04:03 Источник Поделиться
Комментарии
1 ответ

Есть несколько вопросов, которые я вижу:

Во-первых: вы используете много тип псевдонимы (using T =ака typedefы). Это может считаться только личные предпочтения, но я все равно упоминать об этом. Необходимости постоянно возвращаться к вашему типу псевдонимы для основной вещи, как std::shared_ptr<T>, std::weak_ptr<T> и std::vector<T> делает для очень медленного чтения. Это происходит потому, что исходные имена типа легко распознаются любым человеком, имеющим некоторый опыт в C++ и его стандартной библиотеки. Ты вместе с пользовательскими именами типа, не имеют этого преимущества фамильярности.

Смарт-указатели по ссылке

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

Е. Г.:

template <class T>
void dfs(const vertex_sp<T>& vertex_ptr, ...) { /* just using vertex_ptr */ }

против:

void add_neighbor(const vertex_sp& v) { neighbors_.emplace_back(v); }

В общем, вы хотите пройти (умные) указатели по значению при передаче собственности и std::move их в место, которое вы собираетесь хранить их. Е. Г. в neighbors_ вектор в этом случае, но и edgeс конструктором и, вероятно, нескольких других местах.

Передача собственности, передача по значению имеет дополнительное преимущество, если вы постоянно используете std::move, что он может избежать одну дополнительную копию, когда функция вызывается с временным. Для std::shared_ptr<T> это позволяет избежать дорогостоящего атомарного инкремента/декремента цикл (дорого из-за межъядерная синхронизации).

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


  • проходим по указателю T*

  • проходите мимо opt_ref<T> С:

    шаблон
    используя opt_ref = СТД::дополнительно>;


Последний может также быть выполнено с boost::optional<T&> если вы не возражаете, используя толчок. (Некоторые рассуждения и истории получает пояснили в C++ и не могу отказаться от сырых указателей ... пока).

Используя smart_ptr.получить()

Вы используете .get() функция-член std::shared_ptr<T> внутри time_stamps и dfs: просто не. Используя operator-> будет иметь точно такое же представление о версии и на отладочных сборках, с большинством реализаций стандартной библиотеки, добавить дополнительную утверждение о том, что указатель не null. Т. е. вы получите небольшую дополнительную безопасность сети без каких-либо потерь производительности в версии.

Параметр исходный указатель, на которые требуются-передача ссылок

Второй параметры time_stamps и dfs передаются по сырой указатель. Вообще единственный случай, когда вы хотите использовать сырые указатели как параметры как необязательные ссылки (см. выше). Это не один из таких случаев: просто использовать обычный (L-значение, константной) ссылке.

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

vector<T> append_something(vector<T> v)
{
auto lv = std::move(v); // need to move to local variable to ensure compiler
// will move from it by itself, and from C++14
// onwards be forced to do copy-elision
lv.emplace_back(/* something */);
return lv;
}

vector<T> v;
while (/* something */)
{
v = append_something(std::move(v));
}

Перечисление с конкретными описатель хранения

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

Кроме того, вы сделали type перечислимые ограниченные (enum class) пока вы этого еще не сделали для status перечисление. Я бы рекомендовал вам сделать последний слишком ограничено.

Собственности

Объявлении weak_ptr псевдоним, что означает, что вы собираетесь использовать его, но вы никогда не делать. Самый простой улучшение, как представляется, использовать его для from узле edge класс.

Вы храните ссылки на смарт-указатели внутри пограничного класса. Вы почти наверняка не хотите сделать это и в магазине по стоимости взамен.

Внутри get_scc вы получаете ссылку на top Вашего times стек и затем сразу же поп-это: с помощью этой ссылки, потом это неопределенное поведение. Я рекомендую это незначительные изменения:

auto curr = std::move(times.stop());
times.pop();

Смешанная


  • Вы явно задать компилятор для создания default конструктор для graph а потом ниспровергнуть его недобросовестный единственный параметр только другой конструктор. Я предлагаю дать свой type_ член переменной значение по умолчанию, вместо. Затем вы можете удалить значение параметра по умолчанию с вашего пользовательского конструктора.

  • В operator<<(..., const vertex_wp&) ты безоговорочно разыменование возвращаемое значение std::weak_ptr::lock. Это может привести к неопределенному поведению, когда указывал на объект больше не существует. Я предлагаю присвоить локальной переменной первой (auto p = v.lock();).

  • Для других operator<<(..., const vertex_sp&) вы также ссылается безоговорочно: я предлагаю сделать так, условно, как на выше. В качестве альтернативы можно вывести что-то вроде "(null)"или все, что подходит вашей ситуации лучше.

  • Вы использовать get_ несовместимо. Большую часть времени он указать не разрушительное действие: вернуть что-то только для чтения свойство объекта. Но в случае get_transpose() это определенно деструктивное действие. Для возвращения только для чтения информации, я вообще предпочитаю использовать только существительные без каких-либо get префикс, потому что "вам" (на английском языке), как правило, означает что-нибудь отобрать. Для изменяющихся (т. е. разрушительные) действия, я предпочитаю форма глагола, которая описывает изменение.

  • Вы используете _t в качестве суффикса для переменной (graph_t): этот суффикс используется в качестве конвенции в стандартной библиотеке для типа имена. Вы можете хотеть избежать этой путаницы.

  • Вы заготовления государственных алгоритма в глобальных переменных и в рамках графика. Е. Г. в (класс уровня) глобальной переменной vertex<T>::time и pre_, post_ и status_ переменные-члены. Вы можете хранить этот вне графика вместо. Е. Г. в качестве вершины структуры для члена переменных, хранящихся в unordered_map, индексированные вершины (как adj_list). Это сделает ваши занятия данных очень прост обладатели данных, без какого-либо конкретного алгоритма поведения. Т. е. разделение проблем. Кроме того, это сделает ваш алгоритм чтения касаемо обработки структуры данных. Это, в свою очередь, потенциально открывает двери для распараллеливания (предполагая, что этот алгоритм подходит для этого).

Ваши вопросы


  1. Большинство моих замечаний разряда тех, что мне придется дать людям с C++, как их основной язык. Я не вижу никакого Java-измы, которые я привыкла видеть.

  2. Если ваш график является циклической, то вы можете использовать std::unique_ptr<T> для to узлы edge и исходный указатель для from узлы. Этак потоки собственности в одном направлении. Но я знаком только с использованием этой модели в древовидные структуры, где края хранятся как указатели внутри узлов. Т. е. ребенок указателей будет std::vector<std::unique_ptr<node<T>>> в то время как родительский указатель будет один исходный указатель node<T>*. Это безопасно, потому что в данной модели детей разрушаются до родителей (в том числе детского указатель на его родителя). Кроме того, при использовании по умолчанию, компилятор сгенерированный деструктор это деструктор вызов глубину, равную глубине дерева, которое может переполнять стек для несбалансированного или очень большие деревья. Это тривиально, чтобы использовать вместо рекурсии вместо итерации, но вы должны быть осведомлены о нем.

  3. std::move это сложно: самой функции, в основном просто аннотация для компилятора и как таковой действительно нет накладными расходами. Однако то, что она делает сделать, это сказать компилятору, чтобы рассмотреть при разрешении перегрузки функции принимают параметр R-значение ссылки. Эти функции обычно предполагается проанализировать ход-вместо копии, но не гарантируют этого. Т. е. в некоторых случаях конструктор перемещения или перемещения оператора присваивания могут быть недоступны, в этом случае вы все равно получите копию. Даже когда конструктор перемещения настоящее время это еще не бесплатно. Обычно чуть больше, чем замена нескольких указателей (от 1 до 3 для большинства типов в большинство стандартных реализаций библиотеки), который по-прежнему дешевые, просто не бесплатно. Но в некоторых особых случаях (например, переезд из массива, встроенных или std::array) бывает, что контейнеры не могут переместить их памяти. В этих случаях отдельные члены перешли. Поворачивая, что иначе быть O(1) операция (указатель подкачки) в О(N) операций.

  4. Я предполагаю, что вы имеете в виду ваше потокового operator<< реализации: это действительно общий подход для реализации этого оператора. Хотя вы, возможно, желаете перегрузки, беря себе объект по ссылке, а не указатель на него. Давайте код, используя эту сделку с указателями вместо этого.

  5. Я предлагаю вам посмотреть Херб Саттер “течь свободы в C++... по умолчанию.” презентация на CppCon 2016. Это основная тема, занимающихся вопросами безопасности памяти в присутствии структур данных в возрастающей сложности. В том числе решения, в форме библиотеки, разработанные им на хранение цикловых графиков без необходимости shared_ptr.

1
ответ дан 20 марта 2018 в 10:03 Источник Поделиться