Лучший способ отсортировать узел дерева?

Question

Допустим, я создал некоторый код с использованием класса node:

#include <string>
#include <vector>
using namespace std;

class node
{
    vector<node> children;
    string name;
};

и предположил, что структура данных имеет относительно большой размер в памяти (например, 50 МБ) и не отсортирована.

Существует ли достаточно эффективный способ сортировки всех узлов (рекурсивно) на основе name , отличных от , путем простого создания нового отсортированного дерева в памяти и последующего удалениястарая копия?

Разъяснения относительно сортировки:
Вектор children просто сортируется на основе name каждого элемента.Ничто иное не влияет на сортировку.

(т. Е. Для этого потребуется поменять местами два объекта без их глубокого копирования - возможно ли это в C ++ 03 и более ранних версиях? Как насчет позже?)

Answer 1

(т. Е. Для этого потребуется поменять местами два объекта без глубокого копирования их - это возможно в C ++ 03 и ранее? Как насчет позже?)

std::swap является стандартной функцией. Все стандартные типы обеспечивают операцию swap в качестве функции-члена. swap очень распространено и необходимо для всех видов алгоритмов. Стандарт std::sort будет использовать swap для обмена узлами, поэтому вам не нужно делать глубокие копии. Вам просто нужно реализовать swap().

class node
{
    vector<node> children;
    string name;
    void swap(node& other) {
        name.swap(other.name);
        children.swap(other.children);
    }
    void sort() {
        std::sort(children.begin(), children.end(), [&](const node& lhs, const node& rhs) {
            return lhs.name < rhs.name;
        });
        std::for_each(children.begin(), children.end(), [&](node& child) {
            child.sort();
        });
    }
};

Answer 2

Хотя я думаю, что in silico является правильным (то есть std::vector<T> не может быть членом T, поскольку T не завершено), давайте пока проигнорируем это. Вместо этого, я думаю, что ваш вопрос о том, как переместить объект:

std::sort(children.begin(), children.end(),
               predicate);

(с подходящим предикатом) будет обменивать позиции двух узлов, std::swap() используя их. Это создаст глубокое копирование и два задания глубокого копирования. Простое решение - заставить std::sort() использовать пользовательскую функцию подкачки, которая просто меняет дочерние векторы:

class node {
    ...
public:
    void swap(node& other) {
        this->name.swap(other.name);
        this->children.swap(other.children);
    };

void swap(node& n0, node& n1) {
    n0.swap(n1);
}

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

Answer 3

Вы можете рекурсивно пройти по дереву и использовать std :: sort () на каждом узле, чтобы переупорядочить узлы. Смотрите метод sort (), который я добавил к узлу.

#include <algorithm>
#include <string>
#include <vector>

class node
{
    typedef node storage_t;
    typedef std::vector<storage_t> children_t;
    children_t children;
    std::string name;

    struct by_name_fn {
        bool operator()(node const& lhs, node const& rhs) const
        {
            return lhs.name < rhs.name;
        }

        bool operator()(node const* lhs, node const* rhs) const
        {
            return lhs->name < rhs->name;
        }
    };

    void sort()
    {
        std::sort(children.begin(), children.end(), by_name_fn());
        typedef children_t::iterator iter_t;
        for (iter_t i = children.begin(), e = children.end(); i != e; ++i) {
            (*i).sort();
        }
    }
};

Это, однако, будет выполнять множество операций копирования. Таким образом, вам, вероятно, потребуется изменить структуру узла, чтобы он содержал ссылку, а не значение его дочерних элементов. Это означает, что typedef для storage_t должен быть либо узлом *, либо каким-либо общим указателем в зависимости от того, что подходит для остальной части вашей программы. Вам также необходимо изменить строку (* i) .sort () на (* i) -> sort ().