Конструктор копирование в Trie (префиксное дерево)

@ProJyZ · Регистрация: 11.06.2023

Author24 — интернет-сервис помощи студентам

Дорогие форумчане, с наступающим 2024 годом всех!

Но пусть праздники и близки, увы, отдохнуть получается не у всех.

Итак, в чём суть проблемы: нужно написать хеш-таблицу и префиксное дерево(trie), закинуть много чисел в них, а затем провести поиск ста ключей(50% - есть в структурах, 25% - нет и они больше 100'000'000 или меньше 10'000'000(но положительны!) и 25% - нет, но они все в в полуинтервале [10'000'000; 100'000'000). Числа в структурах в этом же диапазоне)

И всём было прекрасно - структуры поиска написаны, всё работает, но! случилась беда - я тупой

. А если конкретнее, то просто не понимаю как именно написать конструктор копирования(оператор присваивания копированием так же) для trie

Сама структура поиска(на comparations не обращайте внимание они нужны для анализа сравнений при поиске ключей):

C++

class trie {
private:
    bool isLeaf;
    trie* childrens[10];
 
public:
    trie() :isLeaf(false) {
        for (int i = 0; i < 10; i++) {
            childrens[i] = nullptr;
        }
    }
 
    ~trie() {
        for (int i = 0; i < 10; i++) {
            if (childrens[i]) delete childrens[i];
        }
    }
 
    //TODO: copy and move constructor
    trie(trie& tr) {}
    trie(trie&& tr) {}
    //TODO:  copy and move operator=
    trie& operator= (trie& tr){}
    trie& operator= (trie&& tr){}
 
    void insert(const char* key) {
        trie* curr = this;
        for (key; *key >= '0' && *key <= '9'; key++) {
            if (curr->childrens[*key - '0'] == nullptr) {
                curr->childrens[*key - '0'] = new trie;
            }
            curr = curr->childrens[*key - '0'];
        }
        curr->isLeaf = true;
    }
 
    bool remove(trie*& curr, const char* key) {
        if (!this) return false;
        if (*key >= '0' && *key <= '9') {
            if (curr && curr->childrens[*key - '0'] && remove(curr->childrens[*key - '0'], key + 1) && !curr->isLeaf) {
                bool haveChildrens;
                for (int i = 0; i < 10; i++) {
                    if (curr->childrens[i]){ haveChildrens = true; break; }
                    haveChildrens = false; 
                }
                if (!haveChildrens) {
                    delete curr;
                    curr = nullptr;
                    return true;
                }
                else {
                    return false;
                }
            }
            else {
                return false;
            }
        }
 
        if (!(*key >= '0' && *key <= '9') && curr->isLeaf) {
            bool haveChildrens;
            for (int i = 0; i < 10; i++) {
                if (curr->childrens[i]) { haveChildrens = true; break; }
                haveChildrens = false;
            }
            if (!haveChildrens) {
                delete curr;
                curr = nullptr;
                return true;
            }
            else {
                curr->isLeaf = false;
                return false;
            }
        }
        return false;
    }
 
    bool find(const char* key, int& comparations) {
        if (!this) {comparations++; return false;}
        comparations++;
        trie* curr = this;
        for (key; *key >= '0' && *key <= '9'; key++) {
            comparations+=2;
            curr = curr->childrens[*key - '0'];
            if (!curr) { comparations++; return false; }
            comparations++;
        }
        comparations++;
 
        return curr->isLeaf;
    }
};

Как заполняю trie:

C++

void fillTrie(trie& tr) {
    std::ifstream file("test_numbers.txt");
    int number;
    std::stringstream numStr;
    while (!file.eof()) {
        file >> number;
        numStr << number;
        tr.insert(numStr.str().c_str());
        numStr.clear();
        numStr.str("");
    }
    file.clear();
    file.seekg(0, std::ios_base::beg);
    file.close();
}

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

)

@nmcf · 31.12.2023, 13:28

Что не ясно-то? Создаёшь копию этой структуры с обходом и выделением памяти.

@vlisp · 31.12.2023, 19:35

Сначала деструктор правильно сделай. Это важнее.

Алексей1153 · 31.12.2023, 21:27

Сообщение от ProJyZ

trie(const trie& tr)

Сообщение от ProJyZ

trie& operator= (const trie& tr)

- пропущен const

Сообщение от ProJyZ

while (!file.eof()) {

- и тут тоже ошибка

Сообщение от ProJyZ

childrens

а тут очепятка - это слово - уже множественное, s не не надо

@ProJyZ · 31.12.2023, 21:45 **[ТС]**

Сообщение от Алексей1153

пропущен const

Пасиба.

Сообщение от Алексей1153

и тут тоже ошибка

Эм, и в чём же? Если файл не кончился(у меня весь файл из чисел), то возвращается false, который нужно переделать в true, чтобы цикл продолжился? А когда файл закончился, что всё наоборот. У меня написано точно так же как и у Вас.

Сообщение от Алексей1153

а тут очепятка - это слово - уже множественное, s не не надо

Пасиба.

Сообщение от vlisp

Сначала деструктор правильно сделай. Это важнее.

Поясните в чём неправильность деструктора? Он полностью очищает память, которую ест структура при insert. А если и добавлений не было, то структура не потребила память, а значит сама спокойно удалилась. Делитать нулы не имеет смысла.

@DrOffset · 31.12.2023, 22:13

Сообщение от ProJyZ

Эм, и в чём же?

eof() Добавляет лишнюю строку

Сообщение от ProJyZ

C++

1 2	while (!file.eof()) { file >> number;

C++

1	while (file >> number)

@vlisp · 01.01.2024, 01:20

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

@ProJyZ · 01.01.2024, 02:12 **[ТС]**

vlisp, так погодите. Смотрите, в корневом узле лежит массив указателей. Они, возможно, указывают на динамическую память, а возможно нет(помним, что указатели на trie). Условимся, что один точно указывает, тогда, при вызове деструктора он будет удалëн посредством вызова дэлит для него, а значит все указатели в его массиве указателей тоже будут очищены, если что-то содержали. Дэлит - вызывает деструктор и передаëт память системе. То есть, сначала динамический trie будет очищен деструктором, а у него деструктор дэлитит всех его детей, а затем память передастся системе. Нафига мне уничтожать узлы с самого низа, если с++ делает всë за меня? Попробуйте протестировать данную структуру на утечку(это несложно) - еë нет. А если корневой узел создан динамически, то это уже проблемма программиста его удалить, но в таком случае деструктор тоже спокойно удалит всех детей.

предположим, что я удаляю корневой узел, а в самом дереве лежит 00, тогда это выглядит так:
delete trie root-> ~trie root -> delete trie 0 -> ~trie 0 -> delete trie 0-> ~trie 0
Затем идëм обратно отдавая память системе. Вот и всë. У меня же не сязный список, а скорее многомерный массив. Если простейшими структурами описывать

@igorrr37 · 01.01.2024, 22:20

Конструктор копии можно сделать таким же рекурсивным как и деструктор

C++

#include <iostream>
#include <vector>
#include <cassert>
#include <string_view>
#include <algorithm>
#include <utility>
#include <string>
#include <cctype>
 
// узел префиксного дерева
struct node
{
    node() = default;
    node(node const& nd) : leaf_(nd.leaf_)
    {
        for (int i = 0; i < nd.vp_.size(); ++i)
        {
            if (nd.vp_[i])
            {
                vp_[i] = new node{ *nd.vp_[i] };
            }
        }
    }
    void insert(std::string_view sv)
    {
        int ind = sv[0] - '0';
        if (!vp_[ind])
        {
            vp_[ind] = new node{};
        }
        std::string_view svNext = { sv.begin() + 1, sv.end() };
        if (!svNext.empty())
        {
            vp_[ind]->insert(svNext);
        }
        else
        {
            vp_[ind]->leaf_ = true;
        }
    }
    std::vector<node*> find(std::string_view sv) const
    {
        std::vector<node*> vret;
        int ind = sv[0] - '0';
        if (vp_[ind])
        {
            vret.push_back(vp_[ind]);
            std::string_view svNext = { sv.begin() + 1, sv.end() };
            if (!svNext.empty())
            {
                auto v = vp_[ind]->find(svNext);
                if (v.empty())
                {
                    vret.clear();
                }
                else
                {
                    vret.insert(vret.end(), v.begin(), v.end());
                }
            }
            else if(!vp_[ind]->leaf_)
            {
                vret.clear();
            }
        }
        return vret;
    }
    ~node()
    {
        for (auto& p : vp_)
        {
            delete p;
            p = nullptr;
        }
    }
    bool leaf_ = false;
    std::vector<node*> vp_{ 10, nullptr };
};
 
// префиксное дерево
struct trie
{
    trie() = default;
    trie(trie const& tr)
    {
        if (tr.root_)
        {
            root_ = new node{ *tr.root_ };
        }
    }
    trie& operator=(trie const& tr)
    {
        if (&tr != this)
        {
            this->~trie();
            trie tTmp = tr;
            std::swap(root_, tTmp.root_);
        }
        return *this;
    }
    void insert(std::string_view sv)
    {
        if (!verify(sv))
        {
            throw 1;
        }
        if (!sv.empty())
        {
            if (!root_)
            {
                root_ = new node{};
            }
            root_->insert(sv);
        }
    }
    // если не найдено - возвращает пустой вектор
    std::vector<node*> find(std::string_view sv) const
    {
        std::vector<node*> vret;
        if (root_ && !sv.empty() && verify(sv))
        {
            vret = root_->find(sv);
        }
        return vret;
    }
    bool erase(std::string_view sv)
    {
        bool bret = false;
        if (!sv.empty() && verify(sv))
        {
            auto v = find(sv);
            if (!v.empty())
            {
                bret = true;
                v.back()->leaf_ = false;
                for (int i = v.size() - 1; i >= 0; --i)
                {
                    if (!v[i]->leaf_ && std::all_of(v[i]->vp_.begin(), v[i]->vp_.end(), [](auto p) { return !p; }))
                    {
                        node* pNodePrev = (i >= 1 ? v[i - 1] : root_);
                        auto it = std::find(pNodePrev->vp_.begin(), pNodePrev->vp_.end(), v[i]);
                        *it = nullptr;
                        delete v[i];
                        v[i] = nullptr;
                    }
                    else
                        break;
                }
            }
        }
        return bret;
    }
    ~trie()
    {
        delete root_;
        root_ = nullptr;
    }
private:
    bool verify(std::string_view sv) const
    {
        return std::all_of(sv.begin(), sv.end(), [](char c) { return std::isdigit(c); });
    }
    node* root_ = nullptr;
};
 
int main() 
{
    trie tra;
    tra.insert("12");
    tra.insert("124");
    trie trb, trc;
    trb.insert("22");
    trb = trc = tra;
    std::cout << "erase: " << std::boolalpha << trb.erase("12") << "\n";
    std::cout << "erase: " << std::boolalpha << trb.erase("124") << "\n";
    std::cout << "erase: " << std::boolalpha << trb.erase("22") << "\n";
    trb.insert("124");
    trb.insert("12");
    std::cout << "erase: " << std::boolalpha << trb.erase("12") << "\n";
    std::cout << "find: " << std::boolalpha << !trb.find("12").empty() << "\n";
    std::cout << "erase: " << std::boolalpha << trb.erase("124") << "\n";
    std::cout << "erase: " << std::boolalpha << trb.erase("125") << "\n";
}

@TheCalligrapher · 01.01.2024, 22:27

Сообщение от ProJyZ

Эм, и в чём же?

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

Сообщение от ProJyZ

Если файл не кончился(у меня весь файл из чисел)

Проверка статуса eof так, как вы ее делаете, не имеет никакого отношения к тому, кончился файл или нет.

Объясните, почему вы решили, что написанное вами while (!file.eof()) { - это "если файл не кончился". Распишите логическую цепочку: как от второго вы перешли к первому.

@ProJyZ · 02.01.2024, 02:37 **[ТС]**

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

C++

trie(const trie& tr) {
        for (int i = 0; i < 10; i++) {
            this->children[i] = nullptr;
        }
        const trie* tri = &tr;
        this->isLeaf = false;
        copyInTrav(tri, this);
    }

А вот доп. функция:

C++

void copyInTrav(const trie* curr, trie* thisCurr) {
        for (int i = 0; i < 10; i++) {
            thisCurr->children[i] = nullptr;
        }
        if (curr->isLeaf) {
            thisCurr->isLeaf = true;
            return;
        }
        for (int i = 0; i < 10; i++) {
            if (!curr->children[i]) continue;
            thisCurr->children[i] = new trie;
            copyInTrav(curr->children[i], thisCurr->children[i]);
        }
        return;
    }

Можно сделать оптимальней, но у меня времени совсем нет на поиск лучших вариантов и переделки.

Сообщение от TheCalligrapher

Объясните, почему вы решили, что написанное вами while (!file.eof()) { - это "если файл не кончился". Распишите логическую цепочку: как от второго вы перешли к первому.

Наверное, потому что так пишут все курсы? То, что так лучше не писать я понял уже из сообщения DrOffset, а Ваше ещё больше уверило меня в этом. Спасибо

Заодно, если Вам несложно, то могли бы Вы предложить варианты как проверять файл на законченность, если содержание файла неизвестно?

Алексей1153 · 02.01.2024, 06:27

Сообщение от ProJyZ

Наверное, потому что так пишут все курсы?

бежать подальше от таких всех курсов. Это где такие?

Сообщение от ProJyZ

мне нельзя использовать STL

хм, а это что

Сообщение от ProJyZ

std::ifstream

Сообщение от ProJyZ

std::stringstream

Добавлено через 1 минуту

Сообщение от ProJyZ

как проверять файл на законченность, если содержание файла неизвестно

попытаться прочитать очередную запись. Если не удалось - файл закончился

@TheCalligrapher · 02.01.2024, 11:29

Сообщение от ProJyZ

Заодно, если Вам несложно, то могли бы Вы предложить варианты как проверять файл на законченность, если содержание файла неизвестно?

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

Именно так и делается ввод-вывод в стандартной библиотеке С и С++: файл читается до тех пор, пока операции ввода-вывода успешно выполняются. Ключевой момент здесь то, что такая проверка делается после каждой операции ввода-вывода

C++

    while (file >> number) {
        numStr << number;
        ...
    }

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

@nmcf 7803 / 6567 / 2988 Регистрация: 14.04.2014 Сообщений: 28,705
	31.12.2023, 13:28	2
	Что не ясно-то? Создаёшь копию этой структуры с обходом и выделением памяти. 0

@vlisp 1046 / 967 / 153 Регистрация: 10.08.2015 Сообщений: 5,221
	31.12.2023, 19:35	3
	Сначала деструктор правильно сделай. Это важнее. 0

Алексей1153 фрилансер 5848 / 5379 / 1103 Регистрация: 11.10.2019 Сообщений: 14,380
	31.12.2023, 21:27	4
	Сообщение от ProJyZ trie(const trie& tr) Сообщение от ProJyZ trie& operator= (const trie& tr) - пропущен const Сообщение от ProJyZ while (!file.eof()) { - и тут тоже ошибка Сообщение от ProJyZ childrens а тут очепятка - это слово - уже множественное, `s` не не надо 1

@ProJyZ 7 / 7 / 0 Регистрация: 11.06.2023 Сообщений: 21
	31.12.2023, 21:45 [ТС]	5
	Сообщение от Алексей1153 пропущен const Пасиба. Сообщение от Алексей1153 и тут тоже ошибка Эм, и в чём же? Если файл не кончился(у меня весь файл из чисел), то возвращается false, который нужно переделать в true, чтобы цикл продолжился? А когда файл закончился, что всё наоборот. У меня написано точно так же как и у Вас. Сообщение от Алексей1153 а тут очепятка - это слово - уже множественное, s не не надо Пасиба. Сообщение от vlisp Сначала деструктор правильно сделай. Это важнее. Поясните в чём неправильность деструктора? Он полностью очищает память, которую ест структура при insert. А если и добавлений не было, то структура не потребила память, а значит сама спокойно удалилась. Делитать нулы не имеет смысла. 0

@vlisp 1046 / 967 / 153 Регистрация: 10.08.2015 Сообщений: 5,221
	01.01.2024, 01:20	7
	Удаляешь верхний уровень , допуская утечку памяти. Главная ошибка в программировании на с++. 0

@ProJyZ 7 / 7 / 0 Регистрация: 11.06.2023 Сообщений: 21
	01.01.2024, 02:12 [ТС]	8
	vlisp, так погодите. Смотрите, в корневом узле лежит массив указателей. Они, возможно, указывают на динамическую память, а возможно нет(помним, что указатели на trie). Условимся, что один точно указывает, тогда, при вызове деструктора он будет удалëн посредством вызова дэлит для него, а значит все указатели в его массиве указателей тоже будут очищены, если что-то содержали. Дэлит - вызывает деструктор и передаëт память системе. То есть, сначала динамический trie будет очищен деструктором, а у него деструктор дэлитит всех его детей, а затем память передастся системе. Нафига мне уничтожать узлы с самого низа, если с++ делает всë за меня? Попробуйте протестировать данную структуру на утечку(это несложно) - еë нет. А если корневой узел создан динамически, то это уже проблемма программиста его удалить, но в таком случае деструктор тоже спокойно удалит всех детей. предположим, что я удаляю корневой узел, а в самом дереве лежит 00, тогда это выглядит так: delete trie root-> ~trie root -> delete trie 0 -> ~trie 0 -> delete trie 0-> ~trie 0 Затем идëм обратно отдавая память системе. Вот и всë. У меня же не сязный список, а скорее многомерный массив. Если простейшими структурами описывать 0

@TheCalligrapher Вездепух 12792 / 6669 / 1795 Регистрация: 18.10.2014 Сообщений: 16,881
	01.01.2024, 22:27	10
	Сообщение от ProJyZ Эм, и в чём же? Проверка статуса `eof` для потока в стандартных библиотеках С и С++ предназначена для "постмортемного" анализа, почему завершилось чтение (если вы захотите сделать такой анализ). Это пост-статус. Пост-статус не пригоден в качестве пред-условия для "чтения файла до конца" (как у вас). Это просто не будет работать правильно. Сообщение от ProJyZ Если файл не кончился(у меня весь файл из чисел) Проверка статуса `eof` так, как вы ее делаете, не имеет никакого отношения к тому, кончился файл или нет. Объясните, почему вы решили, что написанное вами `while (!file.eof()) {` - это "если файл не кончился". Распишите логическую цепочку: как от второго вы перешли к первому. 1

Алексей1153 фрилансер 5848 / 5379 / 1103 Регистрация: 11.10.2019 Сообщений: 14,380
	02.01.2024, 06:27	12
	Сообщение от ProJyZ Наверное, потому что так пишут все курсы? бежать подальше от таких всех курсов. Это где такие? Сообщение от ProJyZ мне нельзя использовать STL хм, а это что Сообщение от ProJyZ std::ifstream Сообщение от ProJyZ std::stringstream Добавлено через 1 минуту Сообщение от ProJyZ как проверять файл на законченность, если содержание файла неизвестно попытаться прочитать очередную запись. Если не удалось - файл закончился 1