Реализация структуры данных Trie в C ++ 11 с использованием интеллектуальных указателей - продолжение

Ссылка на мой первый вопрос .

Я следовал рекомендациям @ JDługosz. Как это выглядит? Есть ли у вас дополнительные рекомендации? Лучше (если возможно) заменить shared_ptr на unique_ptr? Как можно расширить его, чтобы использовать набор символов Unicode?

#pragma once

#include <iostream>
#include <memory>
#include <string>

namespace forest {
    class trie {
    private:
        struct Node {
            std::shared_ptr<Node> children[26];
            bool end = false;
        };
        std::shared_ptr<Node> root = std::make_shared<Node>();
    public:
        void insert(const std::string & key) {
            std::shared_ptr<Node> n = root;
            for (auto c : key) {
                int index = c - 'a';
                auto& slot = n->children[index];
                if (!slot) slot = std::make_shared<Node>();
                n = slot;
            }
            n->end = true;
        }
        bool search(const std::string & key) {
            std::shared_ptr<Node> n = root;
            for (auto c : key) {
                int index = c - 'a';
                auto& slot = n->children[index];
                if (!slot) return false;
                n = slot;
            }
            return n && n->end;
        }
    };
}
11 голосов | спросил xorz57 6 PMpFri, 06 Apr 2018 17:25:49 +030025Friday 2018, 17:25:49

2 ответа


3

Указатели

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

Я согласен с Фрэнком в указаниях. При вызове кода, который работает с объектом, все равно, как объект принадлежит, поэтому для его принятия аргумент типа shared_ptr означает, что он не может принимать объекты, принадлежащие unique_ptr или являющиеся непосредственными членами более крупных структур, или в стеке и т. д. Таким образом, эти аргументы передаются в качестве ссылки .

В стандартном руководстве указатели всегда не владеют . Вы отмечаете их владельцем <gt; для обозначения иначе.

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

Node* n = &root;
for (auto c : key) {
    int index = to_index(c);
    auto& slot = n->children[index];
    if (!slot)  slot = make_unique<Node>();
    n= slot.get();
}

дублированный код обхода

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

Если это единственные две функции, которые у вас есть, это, вероятно, не стоит усилий. Но если у вас больше (удалить, найти ближайшее совпадение и т. Д.), Тогда вы должны это сделать.

26

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

static constexpr size_t nodesize = 1+'z'-'a';
std::unique_ptr<Node> children[nodesize];

плохая клавиша

int index = c - 'a';  // note signed result wanted
if (index<0 || index>=nodesize)  throw invalid_argument("oops");

Обе функции передают строку таким же образом, поэтому сделайте эту общую функцию.

int index = to_index(c);

Переносимость кодирования символов

Было отмечено, что буквы не обязательно смежны в наборе символов источника. Однако, если вы пишете (оригинал) EBCDIC , у вас проблемы с худшей ситуацией, и вы не сможете для ввода символов { } в исходный файл. (Я обсуждал C ++ на примитивном типе программного обеспечения форума, работающего на системе EBCDIC, которой не хватало [ ] и некоторые другие, и это не просто.

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

Итак, часть спецификации состоит в том, что входные строки всегда будут в UTF-8 или (достаточны для наших целей) совместимы с ASCII.

А как насчет во время компиляции? Стандартный говорит , что значение символьного символа 'a' находится в наборе символов исполнение , а не набор символов источника, что является хорошим. За исключением того, что набор символов выполнения пока неизвестен до запуска, так как он может это сделать?

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

static constexpr size_t nodesize = 1+u8'z'-u8'a';
ответил JDługosz 7 AMpSat, 07 Apr 2018 02:59:57 +030059Saturday 2018, 02:59:57
11

Вводная дезинфекция

Ваши функции принимают параметр std::string как таковой, они должны «хорошо себя вести» для любого возможного std::string. Обратите внимание, что хорошее поведение не означает, что он должен «работать», просто чтобы он ничего не сломал.

В частности, что произойдет, если я передам эту функцию в строку "Hello"? 'H' - 'a' is -25, ruh roh!

Есть несколько разных способов решить эту проблему.

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

  • Вы можете избавиться от функции, если удаляется необработанный символ.

  • Просто разверните children до 256 вместо 26, чтобы все допустимые значения char обрабатываются должным образом. Конечно, ваш трюк будет в 5 раз больше, но это довольно незначительная деталь, так как он растет логарифмически.

edit . Этот последний подход также заставляет trie работать с необработанными данными вместо символов, что делает его кодировкой-агностиком (что дает вам поддержку в Unicode)

Избегайте использования shared_ptr, если это абсолютно необходимо

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

в вашем случае, std::unique_ptr<> абсолютно нормально.

Корень не требуется динамически выделять

Он создается при строительстве безоговорочно, и уничтожается при уничтожении безоговорочно. Кроме того, он не использует стирание типа (полиморфизм). Таким образом, нет причин для того, чтобы он не был нормальным членом trie.

std::shared_ptr<Node> root = std::make_shared<Node>();

становится:

Node root;

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

const Node* n = &root;

Но это нормально, потому что это предпочтительнее, как только вы перейдете к unique_ptr в любом случае.

Изменить: В этой заметке:

Необработанные указатели не являются злыми

std::shared_ptr<Node> n = root;

Мы склонны научить людей, что «вы никогда не должны использовать необработанные указатели». Но я нахожу это крайне наивным. Правило real : «У вас никогда не должно быть указателей с собственностью».

Абсолютно ничего плохого в использовании исходных указателей пока не понятно, что:

  • Указатель только ссылается на выделенный объект, не владея им.
  • Время жизни присвоения указателя объекту полностью ограничено временем жизни любого объекта, принадлежащего DOES.

В вашем коде с помощью shared_ptr, используя следующее, было бы 100% нормально, и намного лучше, на мой взгляд:

const Node* n = root.get();

Отметить не мутирующие функции как const.

Ваша функция search() не должна каким-либо образом изменять trie, поэтому вы должны пометить ее как const:

bool search(const std::string & key) const {

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

nitpick: private: здесь избыточно.

По умолчанию пространство имен класса является закрытым. Интересный факт: это единственная разница между class и struct

nitpick: избыточная нуль-проверка

в вашей функции поиска, когда я прочитал последнюю строку:

return n && n->end;

Мое впечатление было «О!n может быть возможно null в некоторых случаях », что привело меня к поиску сценария, где это может произойти. Это вводит в заблуждение читателя.

Оборонительное программирование может быть полезно время от времени, но это просто чрезмерно.

ответил Frank 6 PMpFri, 06 Apr 2018 17:54:15 +030054Friday 2018, 17:54:15

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132