хочу супер-контейнер

elenangel

размер = n; чтобы был random access по индексу (0..n) за время не хуже O(log n и чтобы вставка в середину тоже была за O(log n); и поиск по значению (ключу) тоже за O(log n). Или даже чтобы было лучше чем O(n) хотя бы по времени и памяти - не первыделять при вставке в середину всю память под элементы как в случае вектора или дека например и мочь найти элемент по номеру не перебирая сначала как в случае мапы. Такое бывает вообще, допустим за счет введения сложный структур данных, которые жрут в k раз больше памяти чем необходимо для хранения n элементов?

Anturag

RB-tree?

evgen5555

удаления нужны?

elenangel

да

elenangel

а как в RB-tree c 100 элементами найти 63-й элемент? и да, в данном случае индекс не является ключом, нужен одновременно доступ по ключу и доступ по индексу.

ppplva

А что такое вставка в середину в RBtree? Если я правильно понял задачу, значения не отсортированы, и порядок вставок в контейнер влияет на порядок элементов.
Посмотри "indexable skip list".

elenangel

мне нужна мапа, сортированная по ключу, у которой кроме поиска по ключу я могу найти заданный элемент по номеру k способом отличным от for(i=0, it = begin; i<k; ++i, ++it);
или же нужен вектор, отсортированный, где двоичным поиском можно найти элемент по ключу, но и можно вставить в середину новый элемент сохранив отсортированность но и не перевыделяя весь массив под вектор.
в принципе какая-то реализация deque может быть практически эффективна, но асимптотика вставки O(n) сохраняется, пусть даже с коэффициентом 1/page_size.

agaaaa

а как в RB-tree c 100 элементами найти 63-й элемент? и да, в данном случае индекс не является ключом, нужен одновременно доступ по ключу и доступ по индексу.

ОМГ какая сложность. Хранишь в каждом узле число элементов в поддереве и всё.

ppplva

Тебе подойдет дерево у которого в вершинах записано сколько всего элементов слева и справа?

vall

трэд не читал, но возможно хватитит augmented rb-tree

elenangel

ага, и при вставке за O(log n) обходишь все элементы за вставленным и апдейтишь за O(n) неправильно понял

elenangel

"indexable skip list".

вот это похоже на правду

elenangel

вряд ли, вставка вынуждена будет обойти соседей вставляемого и проапдейтить им эти значения? или я не понял смысл "количество слева и справа"

agaaaa

ага, и при вставке за O(log n) обходишь все элементы за вставленным и апдейтишь за O(n)

FAIL. Обновлять значения нужно только в тех элементах, которые ты прошёл.

elenangel

да, кажись я неправильно понял, я понял как "хранить индекс элемента с элементом", но таки это не то. так-то да, если хранить количество элементов в поддереве, то похоже прокатит за логарифмическое время.

agaaaa

но таки это не то

В смысле не то? Твоим условиям удовлетворяет.

elenangel

ага, я протупил просто с первым коментом на этот счет

apl13

Не оно?
С памятью, правда, чем быстрее все остальное, тем больше логарифмичнее.

rosali

Если я правильно понял, тебе нужна веревка.

elenangel

в итоге наверно так и сделаю, должно получиться то, что надо. rb-tree + количество элементов в поддеревьях

bleyman

Чем сам делать, посмотри на Judy array. Количество элементов в поддеревьях оно точно хранит, плюс судя по приблизительному описанию автор задрочил эдак с полсотни разных структур данных между которыми оно прозрачно переключается внутри себя для хранения поддеревьев в зависимости от статистики, что крайне благотворно влияет на реальную производительность.

elenangel

Judy array

это ж php?
мне как бы c++ надо.

apl13

Тебе предлагают посмотреть на. Тебе не предлагают использовать.

elenangel

да с утра за минуту не разобрался, вторая ссылка в моем гугле - на php. до работы дошел, теперь читаю.
потому и вопрос был про пхп, а не утверждение.

margadon

Judy array

вещь крутая, хоть и интерфейс у неё специфический очень