Я тоже не знаю, где это можно применить. Насколько я понимаю, это побочный эффект того, что правила инициализации для ссылок-локальных переменных и ссылок-параметров функций одинаковы. А, скажем, для функции вида void f(const Base&) вызов f( Derived() ) вполне осмысленен.
Чего-то я поспешил, согласно новому стандарту (C++11) здесь нету неопределенного поведения, вот если ++i заменить на i++, то появится. Старый стандарт (С++03) имел более строгие правила, согласно ему это UB.
Насколько я понял, там примерно следующая ситуация: есть переменная size — размер массива, и есть ptr — указатель на первый элемент массива (названия условные). Если size == 0, то ptr — нулевой указатель, если size > 0, то ptr указывает на первый элемент массива длины size. Сначала они бегут по элементам массива от 0 до size – 1 (если указатель равен 0, то и size равен 0, а следовательно тело цикла не выполняется ни разу), а потом вместо проверки if (size > 0) используют совершенно равнозначную ей (при соблюдении вышеописанного инварианта) проверку if (ptr). В принципе ничего такого криминального.
Но мы не используем здесь индекс (структуру данных, по которой можем быстро искать) для нашего графа, а просто заимствуем ваш прием и храним нужные данные прямо в списке ребер. Для данной задачи (вывести все вершины, соединенные с заданной) нам индекс не нужен, достаточно любой структуры, которая может выдать все хранящиеся в ней элементы.
Вы на какие-то странные вещи в своих подсчетах упираете. Говорите, что можете положить в индекс вместо ссылок сами данные, что вам мешает сделать тоже самое для списка ребер (можно создать отдельный список, положив в него только ребра нужного типа)? Упираете на то, что читаете с диска большими блоками, сделайте так, чтобы пока у вас список ребер меньше этого размера блока, он лежал бы одним последовательным куском, а потом несколькими кусками с размером в блок. Можно же использовать для реализации списка ребер практически любую структуру данных, причем можно даже гибко переключать их: если ребер мало — использовать одну, если много — другую.
Давайте какую-то совсем упрощенную модель попробую накидать.
Много букв
Предположим, у нас все вершины и все ребра одного типа, то есть для всех вершин храним какой-то одинаковый набор данных и для ребер тоже какой-то другой свой набор.
Данные о вершинах храним в одном гигантском бинарном файле. Тогда физический адрес вершины — это смещение от начала файла для её блока данных. Если вершину необходимо удалить, то, конечно, мы ничего не смещаем в нашем файле, а просто этот блок данных становится свободным, и в последующем мы запишем в него данные о новых вершинах. Чтобы хранить данные о свободных блоках, прям на них же построим односвязный список (прием, аналогичный тому, что используют аллокаторы памяти). Если свободных блоков нету, то дописываем в конец файла. Так как мы схитрили и сказали, что все вершины одинакового типа (и следовательно, записи об их данных одинакового размера), то сильно страдать от наличия неиспользуемой памяти в середине файла мы будем только в маловероятном сценарии, когда мы добавлять вершины перестали, а начали их только удалять в промышленных масштабах. Как нетрудно заметить, физический адрес вершины при такой схеме никогда не меняется.
С ребрами ровно та же система (один большой файл на всех), для ребра храним его свойства и физические адреса вершин, которые он соединяет, физические адреса ребер тоже никогда не меняются. Также для каждой вершины храним список физических адресов ребер, из неё выходящих. Хранить все эти списки будем в третьем гигантском файле. Каждый отдельный такой список представляет из себя односвязный список блоков фиксированного размера (такая структура называется chunked vector): то есть, например, 20 адресов ребер и указатель на следующий такой блок из 20 ребер. Поскольку у нас снова всего блоки одинакового размера, применяем все ту же технику хранения. Дополнительно для каждой вершины храним физический адрес самого нового (ещё не до конца заполненного блока), с которого, переходя по указателям, можем прочитать весь список ребер (за время, пропорциональное его длине). Для ребра во втором файле храним указатели, по которым оно записаны в обоих списках вершин. Добавление выполняется за константу, удалением чуть более трудоемко (для каждой вершины смотрим самую последнюю добавленную позицию в списке, меняем её местами с удаляемой из этого списка, а потом уже все удаляем), но тоже за константу.
Если хотим, можем отдавать наружу прямо наши смещения, если нет, то запилить отдельные B-деревья, которые будут по ключу выдавать смещение. В такой реализации мы не умеем быстро отвечать на вопрос, соединены ли две вершины между собой ребром, можем для этого запилить большой индекс на всех парах соединенных между собой вершин, можем подумать как модернизировать наш chunked vector (например, превращать его в дерево поиска или хеш таблицу, если ребер становится больше некоторой константы), в общем, варианты есть.
Но все равно остается необходимость поиска данных по ключу, поэтому сами данные будут хранится примерно также — в древообразной структуре. Но это означает, что периодически надо будет структуру дерева менять (page split для B+, балансирование для AVL и RB-tree итп), это значит что физическое смещение записи в файле данных будет меняться.
Почему? Будем в индексе поиска по ключу хранить не сами данные, а ссылки на их физическое расположение, тогда ребалансировка не будет изменять расположение данных.
Когда структура поменяется надо будет найти в индексе записи, ссылающиеся на старые адреса и обновить их. А как найти такие адреса? Только обходом всего индекса.
Ну не всего, если у нас граф, скажем, неориентированный, то мы знаем с какими вершинами наша связана, ровно для них и надо менять. Но, вообще, надо стремиться, чтобы данные своё физического расположения не меняли.
Да, спасибо, я не видел ваш комментарий с презентацией, когда писал свой, и задавал вопрос автору комментария уровнем выше. А что мешает в РСУБД такой же подход использовать? В смысле, что мешает допустить это самое хранение?
А можно нубский вопрос? Почему нельзя сделать так, чтобы переход по индексу не требовал его поиска? То есть индексы у нас лежат в каком-то дереве поиска, мы в нем ищем ключ и на выходе получаем некоторый физический идентификатор, по которому наши данные лежат (не знаю точно, что он из себя представляет, скажем имя файла+позиция от начала). Почему нельзя вместе с индексом положить сразу этот физический идентификатор? Будут проблемы, когда у записи этот идентификатор изменится и нам придется его везде обновлять? Тогда из-за чего такое обновление будет происходить и нельзя ли от этого как-то избавиться?
В таком случае ваше утверждение неверно. Вы не сможете определить монету, даже если вам сказать легче она или тяжелее настоящей. 2 взвешивания — это всего 9 различных возможных исходов, каждому исходу соответствует ровно один ответ (скажем, монета под номером 3 — фальшивая), а вариантов расположения фальшивой монеты — 12.
Кстати, возможно не так очевидно, как для очереди, но дек также можно эмулировать двумя стеками, имея при этом амортизированное O(1) на каждую операцию. Основная идея, собственно, точно такая же: заводим два стека, один символизирует голову, второй — хвост, соответственно при вставке/удалении из головы/хвоста, добавляем или удаляем из нужного стека. Единственная разница, когда стек, из которого нам нужно удалить, оказывается пустым, то мы перемещаем в него из другого стека не все элементы сразу, а только нижнюю половину (можно взять и другую пропорцию).
К слову, если персистентность не нужна (вы всегда работаете только с последней версией структуры), то можно просто эмулировать очередь двумя стеками, это будет работать за амортизированное O(1).
Прорекламирую свою статью про персистентную очередь, выполняющую каждую операцию за фактическое (не амортизационное) O(1), может кому-то будет интересно. Есть ещё альтернативная реализация, использующая 5 или 6 персистентных стеков. Обе реализации обладают свойством иммутабельности, значит могут быть реализованы на функциональном языке программирования (хотя я, конечно, не знаток).
Последовательность (напоминает двусторонний стек — первый зашёл, первый вышел с обоих концов)
Данные о вершинах храним в одном гигантском бинарном файле. Тогда физический адрес вершины — это смещение от начала файла для её блока данных. Если вершину необходимо удалить, то, конечно, мы ничего не смещаем в нашем файле, а просто этот блок данных становится свободным, и в последующем мы запишем в него данные о новых вершинах. Чтобы хранить данные о свободных блоках, прям на них же построим односвязный список (прием, аналогичный тому, что используют аллокаторы памяти). Если свободных блоков нету, то дописываем в конец файла. Так как мы схитрили и сказали, что все вершины одинакового типа (и следовательно, записи об их данных одинакового размера), то сильно страдать от наличия неиспользуемой памяти в середине файла мы будем только в маловероятном сценарии, когда мы добавлять вершины перестали, а начали их только удалять в промышленных масштабах. Как нетрудно заметить, физический адрес вершины при такой схеме никогда не меняется.
С ребрами ровно та же система (один большой файл на всех), для ребра храним его свойства и физические адреса вершин, которые он соединяет, физические адреса ребер тоже никогда не меняются. Также для каждой вершины храним список физических адресов ребер, из неё выходящих. Хранить все эти списки будем в третьем гигантском файле. Каждый отдельный такой список представляет из себя односвязный список блоков фиксированного размера (такая структура называется chunked vector): то есть, например, 20 адресов ребер и указатель на следующий такой блок из 20 ребер. Поскольку у нас снова всего блоки одинакового размера, применяем все ту же технику хранения. Дополнительно для каждой вершины храним физический адрес самого нового (ещё не до конца заполненного блока), с которого, переходя по указателям, можем прочитать весь список ребер (за время, пропорциональное его длине). Для ребра во втором файле храним указатели, по которым оно записаны в обоих списках вершин. Добавление выполняется за константу, удалением чуть более трудоемко (для каждой вершины смотрим самую последнюю добавленную позицию в списке, меняем её местами с удаляемой из этого списка, а потом уже все удаляем), но тоже за константу.
Если хотим, можем отдавать наружу прямо наши смещения, если нет, то запилить отдельные B-деревья, которые будут по ключу выдавать смещение. В такой реализации мы не умеем быстро отвечать на вопрос, соединены ли две вершины между собой ребром, можем для этого запилить большой индекс на всех парах соединенных между собой вершин, можем подумать как модернизировать наш chunked vector (например, превращать его в дерево поиска или хеш таблицу, если ребер становится больше некоторой константы), в общем, варианты есть.
Ну не всего, если у нас граф, скажем, неориентированный, то мы знаем с какими вершинами наша связана, ровно для них и надо менять. Но, вообще, надо стремиться, чтобы данные своё физического расположения не меняли.
Это называется дек (deque).