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

Question

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

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

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

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

Есть ли разумно эффективный способ для меня, чтобы сортировать все узлы (рекурсивно) на основе 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

Вы можете рекурсивно обхода дерева и использовать зЬй :: 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 of storage_t как на узел *, так и на общий указатель, основанный на том, что подходит для остальной части вашей программы. Вам также потребуется изменить строку (* i) .sort() на (* i) -> sort().

Answer 3

Хотя я думаю, что в силикомарганце правильно (т.е. 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() функции. Поскольку это не требуется для правильного поведения, это часто добавляется позже, чтобы повысить производительность.