Привет всем, кого ещё интересует судьба моих контейнеров
trie_map & trie_set, v0.11 (MSVC 7.1)
Первая версия, в которой всё появившееся ранее работает и при этом не вызывает отвращения.
Подробнее:
проект переведён с лицензии GPL на Boost Software License, как более приемлемой для библиотечного шаблонного кода;
код полностью пересмотрен и кое-где исправлен;
в наиболее интересных местах добавлены комментарии;
bit_comparator'ы теперь реализованы в виде функторов (для большей гибкости и схожести с предикатами STL);
реализованы все конструкторы, полагающиеся ассоциативным контейнерам STL, шаблон метода insert range и методы bit_comp (аналог key_comp) и get_allocator;
метод optimize, реинициализирующий внутренний вектор shortcut, для более эффективного поиска/вставки. Также, после каждой вставки, optimize вызывается автоматически по эмпирическому условию;
полностью реализованы partimator'ы: все возможные шаблоны итераторов частичного совпадения и шаблоны методов [r]begin, [r]end для них. Пример работы — см. patcont.cpp;
появилась возможность указывать, какого размера будет shortcut, при специализации контейнера, что позволяет гибче управлять соотношением производительность/память:
trie_map<std::string,unsigned,bit_comparator<std::string,16> > map16;
// sizeof(map16.shortcut) == (1<<16)*sizeof(unsigned)
trie_map<std::string,unsigned> map0;
// sizeof(map0.shortcut) == (1<<0)*sizeof(unsigned) // по умолч. длина префикса =0
Вроде ничего не забыл.
Кратко о предыдущих версиях:
v0.07
lower_bound, upper_bound, equal_range и count получили второй параметр со значением по умолчанию (длина префикса в битах);
insert с параметром hint (подсказка для вставки за O(1)) выкинут за ненадобностью;
введёны новые типы итераторов — partial match iterators (partimators ) — const_partimator, partimator. Позволяют обходить дерево не полностью, заходя только в нужные поддеревья и проверяя совпадение с маской (как здесь
);
бит-компараторы для следующих типов ключей: standard finite std::string (тестировался только этот), simple infinite (char*) string, finite (char*) string with ASCIIZ semantics;
внутренний вектор shortcut — для константного доступа к узлу при поиске/вставке для префикса заранее заданной длины;
в качестве примера эмуляции хеш-таблицы (см. здесь
) реализован специальный класс DelusionString с соответствующим bit_comparator (см. bit_comp.h);
v0.05
trie_set и trie_map
вынос интерфейса bit_comparator из ключа
поддержка стандартных allocator'ов
реализация всех методов ассоциативных контейнеров (кроме некоторых конструкторов и erase)
слегка увеличена скорость
trie_map & trie_set, v0.13 (MSVC 7.1, GCC 3.2, Comeau 4.3)
Ничего особо нового, только теперь компилируется с вышеперечисленными компиляторами (указаны минимальные номера версий, доступных для проверки). Comeau C++ тестировался онлайн. Кстати, только он в режиме strict выдал варнинг на отсутствие return *this; в _Myt &operator=(const _Myt&) в trie_generic. Остальные компилеры предательски молчали, MSVC в /W4, а GCC, соответственно, в -pedantic -Wextra.
Удивительно ещё то, что GCC собрал релиз, выполняющийся быстрее на треть (32%), в сравнении с MSVC с max speed optimizations.
Насчёт дальнейшего развития: это ещё не всё, но имеются некоторые алгоритмические трудности. Будут идеи, свободное время — будут новые версии.
Здравствуйте, R.K., Вы писали:
RK>Привет всем!
RK>trie_map & trie_set, v0.13 (MSVC 7.1, GCC 3.2, Comeau 4.3) RK>Ничего особо нового, только теперь компилируется с вышеперечисленными компиляторами (указаны минимальные номера версий, доступных для проверки). Comeau C++ тестировался онлайн. Кстати, только он в режиме strict выдал варнинг на отсутствие return *this; в _Myt &operator=(const _Myt&) в trie_generic. Остальные компилеры предательски молчали, MSVC в /W4, а GCC, соответственно, в -pedantic -Wextra. RK>Удивительно ещё то, что GCC собрал релиз, выполняющийся быстрее на треть (32%), в сравнении с MSVC с max speed optimizations. RK>Насчёт дальнейшего развития: это ещё не всё, но имеются некоторые алгоритмические трудности. Будут идеи, свободное время — будут новые версии.
Ждем
Было бы неплохо сделать более полный тест скорости работы класса.
Здравствуйте, _nn_, Вы писали:
__>Здравствуйте, R.K., Вы писали:
RK>>Насчёт дальнейшего развития: это ещё не всё, но имеются некоторые алгоритмические трудности. Будут идеи, свободное время — будут новые версии.
__>Ждем
все интерфейсные функции и классы помещены в namespace pat, особенности реализации — в pat::impl;
добавлен функтор-Decision HammingDistance, выполняющий функции отбора ключей, дистанция Хемминга которых в сравнении с образцом не более заданной величины (см. здесь
), пример — в patcont.cpp;
в классы partimator'ов добавлены методы для реализации обхода дерева в ширину (см. функтор FixedLength в partial.h, в принципе можно комбинировать и остальные функторы):
— bool leaf() — true, если партиматор указывает на лист;
— [const_][reverse_]iterator|partimator [r]begin|end([const Decis2&]) — для получения вложенного итератора|партиматора.
Пример работы см. build_re.cpp (аналогично этому
Немного о планах (в приблизительном порядке невозрастания реализуемости;):
хотелось бы доделать erase, однако это не так уж тривиально;
есть мысли реализовать контейнеры, аналогичные суффиксным деревьям (время добавления очередного суффикса константно) на уже имеющейся основе, но это уже довольно значительный уход от парадигмы стандартных контейнеров STL и неслабая возня с шаблонами;
[почти] нереальные фантазии о не-бинарных деревьях цифрового поиска PATRICIA.
__>Было бы неплохо сделать более полный тест скорости работы класса.
Добил-таки erase(iterator), впрочем, и он меня тоже, но об этом потом. Ирейз получился красивый, константный и жутко быстрый. Зацените код:
void erase(iterator delIt)
{
// retrieve Algorithm structure from iterator
Algorithm pal(delIt);
// q back-point to p, p & q may point to same node
Node *q=pal.getQ(),*p=pal.getP();
// pBrother - sibling of pconst unsigned
pBrotherId=1ul^pal.getQid(),
pBrotherTag=q->getXtag(pBrotherId);
Node *pBrother=q->getXlink(pBrotherId);
// take parent of qconst unsigned qParentId=q->getParentId();
Node *qParent=q->getParent();
// if parent of q existif (qParent)
{
// replace q with p-brother
qParent->setXlinktag(qParentId,pBrother,pBrotherTag);
if (!pBrotherTag)
pBrother->setParentid(qParent,qParentId);
}
// if p & q isn't equalif (q!=p)
{
// make q identical to p
q->setAllButValue(*p);
Node *pParent=p->getParent();
// correct parent of p if existif (pParent)
pParent->setXlinktag(p->getParentId(),q,0);
// correct childs of pfor (unsigned i=0;i!=2;++i)
{
if (!p->getXtag(i))
p->getXlink(i)->setParentid(q,i);
}
}
// special case: del rootif (p==root_)
root_=q==p?0:q;
// sic transit gloria mundi
delNode(p);
// decrease size
--size_;
#ifdef PAT_SHORTCUTS
// fix shortcuts
optimize();
#endif
}
Как вы уже, наверное, заметили, метод возвращает void, хотя стандартный должен вернуть iterator на следующий после удаляемого элемент. Но увы, эффективно найти этот итератор не позволяет сама природа PATRICIA trie: каждый узел является одновременно и веткой и листом. Таким образом, на каждое хранимое значение существуют два указателя: как на поддерево (обычный указатель на детей) и как на лист (обратная ссылка, в Кнуте обозначается штриховой стрелкой). Благодаря этому, кстати, и становятся возможными partimator'ы с заходом только в нужные поддеревья.
Подумав, как можно было бы исправить ситуацию, я понял, что trie не сможет обеспечить валидность итераторов после удаления узла. Ещё через пару минут сообразил, что итераторы инвалидируются также после вставки узла. Получается, что условия по сохранности итераторов, которые обеспечивают стандартные ассоциативные контейнеры (итератор на элемент контейнера живёт пока жив элемент под итератором), нельзя выполнить для контейнеров, основанных на PATRICIA trie. Единственное исключение — итераторы, возвращаемые end() и rbegin() — их правильность распространяется на всё время жизни контейнера. Также после вставки/удаления не сохраняются партиматоры, но для них нет никаких гарантий даже для end() и rbegin(). Вот так, немного грустно, но суббота была непоправимо испорчена с полдня.
Неизбежные следствия: невозможно эффективно реализовать erase(iterator first,iterator last), нельзя просто пробежаться по контейнеру и удалить ненужные элементы, придётся начинать или с begin() или с end() после каждого удаления. Впрочем, я ещё попробую подумать над вычислением в erase() следующего итератора: тут не всё так запущено, я думаю...
Ещё, чуть не забыл: в связи с тем, что при удалении обновляются несколько разных узлов, необходимо пересчитывать вектор shortcut (методом optimize()), что требует немало времени (для 16-битных префиксов нужно обновить 2^16 элементов). По тестам выходит, что скорость удаления в этом случае понижается в ~20 раз. Поэтому в будущем лучше отказаться от этой небольшой (8-10%) оптимизации, тем более, что в одной из следующих версий, надеюсь, образуются не-бинарные деревья — и шоткаты станут совсем ненужны.
В качестве бонуса к erase() набросал небольшой адаптер unique_priority_queue для trie_set и set. Функциональность у него ровно такая же, как и у std::priority_queue (основанного на хипе), но сохраняются только уникальные значения. Естественно, для не-скалярных типов у trie_set наблюдается преимущество в производительности push/pop, по сравнению с std::set (см. результаты теста дальше).
Новые бит-компараторы: для unsigned и int. Вдруг кому пригодятся?
Здравствуйте, _nn_, Вы писали:
__>Здравствуйте, R.K., Вы писали:
__>>>Было бы неплохо сделать более полный тест скорости работы класса.
RK>>Это да... Вот только с чем сравнивать будем?
__>Между компиляторами и с std::map/std::set
ОК. Ловите результаты для P4-3.0, 1G RAM (исходники см. speed_test.cpp и speed_test_pq.cpp):
MSVC 7.1 (PAT_SHORTCUTS) File: 93 М (russian words)
*** pat::trie_set
Timer: 34.4867 sec.
Size: 404463
*** pat::trie_set<pat::DelusionString>
Timer: 29.6441 sec.
Size: 404463
MSVC 7.1 (w/o PAT_SHORTCUTS) File: 93 М (russian words)
*** pat::trie_set
Timer: 37.3867 sec.
Size: 404463
Timer erase: 0.297726 sec.
*** std::set
Timer: 54.5871 sec.
Size: 404463
Timer erase: 0.302945 sec.
*** std::hash_set
Timer: 28.5497 sec.
Size: 404463
*** std::hash_set: to std::vector + std::sort
Timer: 1.42755 sec.
Size: 404463
Full hash timer: 29.9773 sec.
GCC 3.4.4 (PAT_SHORTCUTS) File: 93 М (russian words)
*** pat::trie_set
Timer: 25.2501 sec.
Size: 404463
*** pat::trie_set<pat::DelusionString>
Timer: 23.0039 sec.
Size: 404463
GCC 3.4.4 (w/o PAT_SHORTCUTS) File: 93 М (russian words)
*** pat::trie_set
Timer: 27.9667 sec.
Size: 404463
Timer erase: 0.476102 sec.
*** std::set
Timer: 45.1105 sec.
Size: 404463
Timer erase: 0.482932 sec.
*** std::hash_set
Timer: 16.078 sec.
Size: 404463
*** std::hash_set: to std::vector + std::sort
Timer: 1.94486 sec.
Size: 404463
Full hash timer: 18.0229 sec.
---------------- [unique_]priority_queue
MSVC 7.1 File: 93 М (russian words)
*** std::priority_queue
Timer: 66.5425 sec.
*** pat::unique_priority_queue
Timer: 31.2714 sec.
*** pat::unique_priority_queue<std::set>
Timer: 43.163 sec.
GCC 3.4.4 File: 93 М (russian words)
*** std::priority_queue
Timer: 88.7093 sec.
*** pat::unique_priority_queue
Timer: 31.46 sec.
*** pat::unique_priority_queue<std::set>
Timer: 42.5287 sec.
Здравствуйте, _nn_, Вы писали:
__>Здравствуйте, R.K., Вы писали:
RK>>
RK>>MSVC 7.1 (w/o PAT_SHORTCUTS) File: 93 М (russian words)
RK>>*** pat::trie_set
RK>>Timer: 37.3867 sec.
RK>>Size: 404463
RK>>Timer erase: 0.297726 sec.
RK>>*** std::set
RK>>Timer: 54.5871 sec.
RK>>Size: 404463
RK>>Timer erase: 0.302945 sec.
RK>>*** std::hash_set
RK>>Timer: 28.5497 sec.
RK>>Size: 404463
RK>>*** std::hash_set: to std::vector + std::sort
RK>>Timer: 1.42755 sec.
RK>>Size: 404463
RK>>Full hash timer: 29.9773 sec.
RK>>GCC 3.4.4 (w/o PAT_SHORTCUTS) File: 93 М (russian words)
RK>>*** pat::trie_set
RK>>Timer: 27.9667 sec.
RK>>Size: 404463
RK>>Timer erase: 0.476102 sec.
RK>>*** std::set
RK>>Timer: 45.1105 sec.
RK>>Size: 404463
RK>>Timer erase: 0.482932 sec.
RK>>*** std::hash_set
RK>>Timer: 16.078 sec.
RK>>Size: 404463
RK>>*** std::hash_set: to std::vector + std::sort
RK>>Timer: 1.94486 sec.
RK>>Size: 404463
RK>>Full hash timer: 18.0229 sec.
RK>>
__>
__>Что-то я недопонял тест, hash_set получается выходит намного быстрее чем pat::trie_set ?
Да. Но hash_set предполагается сравнивать с trie_set<DelusionString>:
MSVC 7.1 (PAT_SHORTCUTS) File: 93 М (russian words)
*** pat::trie_set
Timer: 34.4867 sec.
Size: 404463
*** pat::trie_set<pat::DelusionString>
Timer: 29.6441 sec.
Size: 404463
GCC 3.4.4 (PAT_SHORTCUTS) File: 93 М (russian words)
*** pat::trie_set
Timer: 25.2501 sec.
Size: 404463
*** pat::trie_set<pat::DelusionString>
Timer: 23.0039 sec.
Size: 404463
Ибо именно DelusionString с соответствующим бит-компаратором (и с включённым PAT_SHORTCUTS) эмулирует работу hash_table. Естественно, в результате получается множество, сортированное по хеш-значениям ключей, т.е. хорошо перемешанное, зато временные показатели добавления будут близки к хешированию, что мы и наблюдаем в тестах Для GCC это менее заметно, видимо реализация hash_set там лучше, чем в VC.
Вот только возможности trie-контейнеров по различным способам перебора элементов намного превышают стандартные, а уж тем более hash-контейнеры, это можно увидеть в предыдущих моих сообщениях.
Кстати, забыл одну вещь: в версии 0.19 появилась возможность хранить элементы в обратном порядке ключей назначением контейнеру pat::reverse_bit_comparator (что-то вроде std::greater вместо std::less), например:
__>>Что-то я недопонял тест, hash_set получается выходит намного быстрее чем pat::trie_set ?
RK>Да. Но hash_set предполагается сравнивать с trie_set<DelusionString>:
Все встало на места
Что-то я не нахожу файлы тестов, куда вы их выложили ?
Я хочу сравнить trie_map/set с hash_/map/set от STLPort.
Здравствуйте, _nn_, Вы писали:
__>Здравствуйте, R.K., Вы писали:
__>>>Что-то я недопонял тест, hash_set получается выходит намного быстрее чем pat::trie_set ?
RK>>Да. Но hash_set предполагается сравнивать с trie_set<DelusionString>:
__>Все встало на места
__>Что-то я не нахожу файлы тестов, куда вы их выложили ? __>Я хочу сравнить trie_map/set с hash_/map/set от STLPort.
Вдогонку было бы неплохо использовать один стиль именования, а то у вас их несколько.
Лучше все в стиле STL
Кстати лучше не начинать имена с подчеркивания — _Myt, _Pairib, а еще лучше заменить на что-то более информативное, например this_type, pair_type.
Здравствуйте, _nn_, Вы писали:
__>Здравствуйте, _nn_, Вы писали:
__>>Здравствуйте, R.K., Вы писали:
__>>>>Что-то я недопонял тест, hash_set получается выходит намного быстрее чем pat::trie_set ?
RK>>>Да. Но hash_set предполагается сравнивать с trie_set<DelusionString>:
__>>Все встало на места
__>>Что-то я не нахожу файлы тестов, куда вы их выложили ?
В архиве с 0.19 версией:
speed_test.cpp
speed_test_pq.cpp
__>>Я хочу сравнить trie_map/set с hash_/map/set от STLPort.
__>Вдогонку было бы неплохо использовать один стиль именования, а то у вас их несколько.
Всего два: мой текущий (я их сменил уже с полдесятка;) и STL. Там где стиль вылезает на поверхность в виде интерфейсов — там "like STL".
__>Лучше все в стиле STL
Со-омнительно... мне он не нравится
__>Кстати лучше не начинать имена с подчеркивания — _Myt, _Pairib, а еще лучше заменить на что-то более информативное, например this_type, pair_type.
Здравствуйте, R.K., Вы писали:
RK>Здравствуйте, _nn_, Вы писали:
__>>Здравствуйте, _nn_, Вы писали:
__>>>Здравствуйте, R.K., Вы писали:
__>>>>>Что-то я недопонял тест, hash_set получается выходит намного быстрее чем pat::trie_set ?
RK>>>>Да. Но hash_set предполагается сравнивать с trie_set<DelusionString>:
__>>>Все встало на места
__>>>Что-то я не нахожу файлы тестов, куда вы их выложили ?
RK>В архиве с 0.19 версией: RK>speed_test.cpp RK>speed_test_pq.cpp
Я не заметил что 0.17 была скачена
Тогда скоро будут тесты с STLPort
__>>>Я хочу сравнить trie_map/set с hash_/map/set от STLPort.
__>>Вдогонку было бы неплохо использовать один стиль именования, а то у вас их несколько.
RK>Всего два: мой текущий (я их сменил уже с полдесятка;) и STL. Там где стиль вылезает на поверхность в виде интерфейсов — там "like STL".
__>>Лучше все в стиле STL
RK>Со-омнительно... мне он не нравится
Ну дело вкуса
__>>Кстати лучше не начинать имена с подчеркивания — _Myt, _Pairib, а еще лучше заменить на что-то более информативное, например this_type, pair_type.
RK>Это да. Будет время — исправлю.
Ждем-с
для удаления сразу всех значений, ключи которых начинаются с заданного префикса. Работает быстро: сначала находит поддерево с заданным префиксом за логарифмическое время, затем вырезает это поддерево из основного дерева за константное время и, наконец, рекурсивно освобождает память, выделенную под узлы в данном поддереве. Если prefixLen задан по умолчанию ~0ul, вырезается максимум один узел с заданным ключом, т.е. поведение в этом случае стандартное. Метод возвращает кол-во удалённых значений.
Эффективно получать следующий после удалённого итератор я так и не смог, но есть надежда сделать erase(iterator,iterator) через последовательное удаление узлов с одинаковым префиксом, пока не реализовано.
Теперь о самом интересном.
В анонсе суффиксных деревьев
Насчёт времени добавления я немного ошибся: на самом деле сложность индексирования всей строки линейно зависит от её длины; получается, что добавление одного суффикса константно лишь в среднем.
Но это не меняет сути дела: в текущую версию дополнительных контейнеров STL добавлен прототип шаблона контейнера suffix_set, реализующий динамическое суффиксное дерево на основе PATRICIA trie.
Интерфейс suffix_set:
// constructor
suffix_set(
key_type keys, // передается указатель на начало суффиксного буфера (на первый суффикс)
size_type size, // размер окна (одновременно индексируемых суффиксов)const bit_compare &bitComp=bit_compare(),
const allocator_type &alloc=allocator_type());
// в конструкторе сразу добавляется первый узел, он же root
// инвариант для suffix_set: в контейнере должен быть хотя бы один суффикс
// вставляем очередной суффикс (следующий по возрастанию адресов)void push_back();
// удаляем наиболее ранний суффикс (первый по порядку добавления)void pop_front(); // именно этот метод делает suffix_set динамическимbool full() const; // true, если нет места для добавления очередного суффикса
size_type size() const; // возвращает текущее кол-во суффиксов
Подобный интерфейс, привычный для очереди (push_back/pop_front), обусловлен необходимостью последовательного (без пропусков) добавления/удаления суффиксов, а также произвольного доступа (по порядку добавления) к узлам дерева и к соответствующим им суффиксам, которые играют роль ключей.
Для реализации внутреннего хранения узлов цифрового дерева был выбран кольцевой буфер (см. ring_buffer.h), как структура, свойства которой наиболее соответствуют требованиям дерева суффиксов.
Требования к памяти: <индексируемая строка> + <размер окна suffix_set>*sizeof(Node). sizeof(Node) при включенном PAT_ALIGNHACK составляет 16 байт.
Все возможности, доступные в trie_set, доступны и в suffix_set (пока есть const_(iterator|partimator)), за исключением тех, которые основаны на конечности ключей, ибо суффиксы обязаны быть бесконечными. Ещё одно отличие состоит в том, что, во избежание избыточности, в узлах suffix_set не хранятся указатели на суффиксы, но на внешнем интерфейсе это не отражается.
Пример работы с suffix_set см. test_suffix.cpp. На моём P4-2.8 1G RAM файл в 33М полностью индексировался (размер окна == длине файла) за 18 сек., исп. ОЗУ — 570М. Файл 75М с окном 4М динамически индексировался за 60 сек., исп. ОЗУ — 140М.
Основной причиной реализации этого прототипа была необходимость проверить, будут ли работать мои, до сей поры чисто умозрительные, алгоритмы на практике. Так что ещё предстоит довести дерево суффиксов до нормального состояния, обобщив его с trie_* контейнерами, сделать suffix_map (трудно представить, как его можно использовать, но на всякий случай;). Также стоит подумать об уменьшении объема используемого ОЗУ и об алгоритмах, эффективно реализуемых с suffix trie.
(trie_|suffix_)(map|set), v0.29 (MSVC 7.1, GCC 3.2, Comeau 4.3).
Пришлось переписать заново практически всё. По основным пунктам:
Бит-компараторы теперь существуют для std::basic_string<T>, т.е. как минимум для std::string и std::wstring; также для любого указателя вида T*.
Decision-функторы PartialMatch и HammingDistance теперь специализируются типом контейнера, отчего стало возможным применять их с любыми возможными бит-компараторами. При тестировании с суффиксными контейнерами была обнаружена и исправлена ошибка в механизме партиматоров, заодно избавился от довольно глубокой рекурсии. Сейчас в работе итераторов частичного совпадения есть только одно ограничение: функтор HammingDistance оказалось невозможным применять с реверсивными итераторами, потому что он содержит mutable-члены. В остальных случаях — это действительно работает! Проверено.
В результате обобщения всех контейнеров образовался дополнительный внутренний класс impl::assoc_generic, в который вынесены все итераторы ([const_][reverse_](iterator|partimator)) и методы, общие для всех четырёх контейнеров: [r](begin|end), find, (lower_|upper_)bound, equal_range, count.
Из прототипа suffix_set предыдущей версии образовались два новых шаблонных контейнера:
template <
typename Type,
int delta=1, // расстояние в bitT между соседними суффиксамиtypename BitComp=bit_comparator<Type>,
typename Allocator=std::allocator<Type> >
class suffix_set;
template <
typename Type,
typename Datum,
int delta=1, // расстояние в bitT между соседними суффиксамиtypename BitComp=bit_comparator<Type>,
typename Allocator=std::allocator<Type> >
class suffix_map;
Краткое описание всех методов этих шаблонов — в suffix_set.h. Недостаточно потестированные методы, возможны баги: pop_front, pop_back.
Некоторые примеры использования суффиксных деревьев: линейный поиск множества ключей (multi_search.cpp) и преобразование BWT (или лексическая сортировка, сложность также линейная), см. usort3.cpp. Для сравнения приведёна версия 2.33 USORT, применяющая для сортировки обычное дерево PATRICIA (сложность приблизительно O(N*log N)).
Обобщить suffix_map и suffix_set мне так и не удалось. Несмотря на практически полную идентичность интерфейса, контейнеры эти различаются в некоторых внутренних деталях. Также очень не нравится обилие protected-членов в промежуточных классах — есть подозрение, что можно сделать лучше. Если кто-нибудь сможет помочь исправить ситуацию, буду дико благодарен Готов пойти на любые издержки — вплоть до переписывания всего кода (нам не привыкать).
Документацию решил сделать автоматически генерируемой doxygen'ом. Пока, только ради эксперимента, потренировался на algorithm.h. Опять же, замечания приветствуются.