По-моему, единственный вариант с ожидаемым O(1) — хэш-таблица. Если данные известны, можно подобрать perfect hash function и тогда O(1) будет гарантирован.
Мм, хэш-таблица даёт возможность поиска по ключу. Что же использовать тут в качестве ключа? Номер в массиве? тогда вставка будет увеличивать все ключи большие этого на 1 — не вариант. Тогда что?
Да вот я тоже перечитал вопрос, вижу, что само значение в качестве ключа использовать вроде как не предполагается, предполагается вроде как вставить и получить некоторый «номер в списке» («номерок» :), по которому затем можно получить обратно значение. Хотя где будет хранится этот «номерок»?
Если так, то можно сделать тупо увеличивающийся массив — сначала выделяем, например, 512 элементов, запоминаем номер следующего пустого (0), при вставке вставляем и сдвигаем указатель на позицию, когда больше вставлять некуда — realloc до 1024 элементов и т. д. Удаление только вот не предусматривается, хотя можно и удаление сделать, со связанным списком пустых элементов.
По сути это тоже хэш, только с особой функцией вычисления ключа :) Дело в том, что ограничение O(1) вариантов-то не дает — только хэш. Или вот такой вот хитрый массив, хотя хэш — это и есть массив, потому он и O(1).
Если само значение использовать для ключа, то это сильно зависит от значения. Ключ хэша должен быть целым числом, равномерно распределенным по размеру хэш-таблицы. В простейшем случае если входные значения уже равномерно распределены, но по большему интервалу, можно просто делить их на размер хэш-таблицы и брать остаток. Если брать значение указателя, то, во-первых, зачем? Чтобы получить потом по нему обратно значение? Но ведь у нас уже есть указатель на него. В условии упоминаются еще целые числа, но опять-таки надо знать характер распределения этих чисел. Хотя можно и не заморачиваться, а взять какую-нибудь хорошо перемешивающую функцию, скорее всего, подойдет.
1) Время их работы амортизировано, а значит некоторые отдельные операции могут быть долгими (автору требуется гарантированное время работы O(1))
2) доступ к произвольному элементу по его номеру в списке — как это реализовать на ФК? «Из коробки» ФК предоставляют только доступ к минимальному элементу.
в припадке «боже, что я несу?» убежал читать томик Кормена.
Так вот, второе издание, глава 11 («Хэш-таблицы»), параграф 11.1 («Таблицы с прямой адресации») подтверждает говорит, что «Каждая из приведенных операций [поиск, вставка и удаление] очень быстрая: время их работы равно O(1)».
Но, конечно, всё не так просто, применимость зависит от характера данных. А то фрагментация страшная, уникальность для индексации обеспечить…
Подозреваю, что это совсем не то, что вы искали. Но сам я противоречий условиям вопроса не нашел )
