Здравствуйте, _agg, Вы писали:
_>Так неполучится, да и последовательность в которую вставляю должна быть сортированной, то есть индекс реально можно будет получить только после вставки и сортировки.
Тебе на самом деле не нужна сортировка, тебе нужна структура, которая автоматически обеспечивает отношение порядка. По классике для этого используются разновидности бинарных деревьев, типа красно/черного дерева. Но на списках и хэшах тоже можно не хуже.
Re[5]: Нужна идея сортированной последовательности с доступом по индексу
Здравствуйте, T4r4sB, Вы писали:
TB>Бинарным поиском по связному списку? TB>И как ты возьмёшь середину, например?
У вас в плюсах какая-то линейность мышления или что? Если свзный список, значит обязтально как в букваре из квадратиков и стрелочек? Что мешает хранить параллельно самому списку индекс на его элементы?
Re[6]: Нужна идея сортированной последовательности с доступом по индексу
Здравствуйте, Miroff, Вы писали:
TB>>И как ты возьмёшь середину, например?
M>У вас в плюсах какая-то линейность мышления или что? Если свзный список, значит обязтально как в букваре из квадратиков и стрелочек? Что мешает хранить параллельно самому списку индекс на его элементы?
Если хранить индекс, то зачем нужен список?
_____________________
С уважением,
Stanislav V. Zudin
Re[6]: Нужна идея сортированной последовательности с доступом по индексу
Здравствуйте, Miroff, Вы писали:
M>У вас в плюсах какая-то линейность мышления или что? Если свзный список, значит обязтально как в букваре из квадратиков и стрелочек? Что мешает хранить параллельно самому списку индекс на его элементы?
Эммм, а какая будет сложность вставки в середину тогда?
Re[2]: Нужна идея сортированной последовательности с доступом по индексу
Здравствуйте, T4r4sB, Вы писали:
TB>Здравствуйте, _agg, Вы писали:
_>>Задача с виду проста, нужно вставлять в сортированный контейнер а удалять и получать по индексу. _>>В идеале нужен std::set только с доступом по индексу.
TB>Но ведь получается что при вставке меняются индексы в среднем у половины всего контейнера.
Да, ну и что? Это же не означает, что операции с ними нельзя делать быстрее чем за линейное время.
позволяют делать за время O(logN) не только вставку, поиск и удаление узла по значению ключа, но и аналогичные операции по порядковому индексу. Причём независимо от того какие операции и в каком порядке выполняются (а не как, например, тут
предложили лениво сортировать, что очевидно ужасно работает для чередующихся запросов).
Из накладных расходов — лишь необходимость хранить рядом с каждым элементом дополнительный счётчик под это дело.
То есть не смотря на то, что при вставке элемента в дерево индексы поменяются у O(N) элементов, augmented BST позволяет делать обновление индексов во время вставки/удаления за ту же временную сложность O(logN).
Собственно, std::set хотя везде и реализуется через деревья поиска (потому что требования составлены так, что иначе их или не соблюсти, или это будет очень непрактично), но наружу этот интерфейс деревьев не показывает, хотя в реализации в целом там почти всё нужно есть.
И поэтому приходится копипастить почти такую же реализацию двоичных деревьев поиска к себе в проект, чтобы можно было хранить там размеры поддеревьев и обращаться к ним, и, соответственно, получить возможность доступа по порядковому индексу.
Re[7]: Нужна идея сортированной последовательности с доступом по индексу
Здравствуйте, Stanislav V. Zudin, Вы писали:
SVZ>Если хранить индекс, то зачем нужен список?
Чтоб вставлять и удалять за логарифмическое время. Тебя же никто не заставляет поддерживать индекс и список в постоянно синхронизированном состоянии. Индекс может обновляться в фоновом режиме при актуальном обращении к элементу. В чем прелесть реальных задач, в отличие от книжных алгоримов, ты можешь оптимизировать только то что важно конкретно для твоего сценария, а не сферический средний случай в вакууме.
Re[3]: Нужна идея сортированной последовательности с доступом по индексу
Здравствуйте, Miroff, Вы писали:
SVZ>>Если хранить индекс, то зачем нужен список?
M>Чтоб вставлять и удалять за логарифмическое время. Тебя же никто не заставляет поддерживать индекс и список в постоянно синхронизированном состоянии. Индекс может обновляться в фоновом режиме при актуальном обращении к элементу. В чем прелесть реальных задач, в отличие от книжных алгоримов, ты можешь оптимизировать только то что важно конкретно для твоего сценария, а не сферический средний случай в вакууме.
Не проходит по условиям задачи.
Требуется и хранить данные упорядоченно и без пропуска индексов.
А это означает, что при каждой модификации коллекции придется сперва искать в индексе, а потом его модифицировать.
Вот и получается, что список лишний.
_____________________
С уважением,
Stanislav V. Zudin