Мне надо хранить массив указателей на строки так, чтобы после добавления в массив указателя, строки, на которые указывают указатели были отсортированы. Например, есть такие указатели


после добавления указателя p1, массив будет содержать p1
после добавления  p2 - p2, p1
после добавления  p3 - p2, p3, p1
после добавления  p4 - p2, p3, p4, p1
после добавления  p5 - p2, p3, p4, p1 (так как такое слово уже есть)

потом надо будет обращаться к указателям последовательно, чтобы сохранить строки в файл.
Строк много(~100000), поэтому хочется чтобы вставка указателя в массив происходила быстро. Тоесть, по возможности, чтобы определение того, есть ли такое слово в массиве, было не через линейный поиск, а, скажем, через двоичный поиск.
Хочется использовать STL, но не знаю как это сделать.
Что лучше использовать array, vector или еще что-то?
Функцию добавления, в этом случае, самому писать или такая уже есть?
по возможности, привести кусок кода или написать что за чем делать на словах.

Используй списки а не массив. В списках вставка нового элемента требует О(1) времени, но тогда двоичный поиск применить нельзя.
Иначе если использовать массив, то искать будет быстро а вставлять долго. Еще есть такая структура данных как хеш-таблица, которая позволяет быстро искать если данная строка в массиве  

Это сообщение отредактировал(а) Ozerich - 7.2.2010, 22:42

тоесть, я так понимаю ни список ни массив мне не подходит, так как в первом случае нельзя использовать двоичний поиск, а во втором - долго вставлять.
и непонятно на счет хеш таблицы. Как там можно вставлять данные по алфавиту? Я думал что это в хеш таблице так сделать нельзя.

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

Это сообщение отредактировал(а) roko - 7.2.2010, 23:03

Есть ещё std::set и std::map, в них данные - отсортированы, и поиск происходит по двоичному дереву. Насчёт хэша - это тоже хорошая мысль, в качестве хэш-функции лучше всего использовать CRC-код, 16-битный или 32-битный, вот пример вычисления:


Добавлено через 9 минут и 18 секунд
да, ещё одну фичу не дописал для инициализации таблицы:
Кстати, CRC можно вычислять через статическую таблицу, в инете полно примеров. Ну и кроме того, зачастую намного удобнее и быстрее работать с CRC от строк, чем с самими строками.

BEOWOLF, можете объяснить что делает второй define? Я такого раньше не встречал.
Насколько я понял, функция CRC32IEEE просто возвращает crc(или хеш) для data.
Мне нужно чтобы crc хранились так, чтобы когда я буду последовательно, от начала до конца, перебирать crc, то автоматически должны будут перебираться соответствующие строки в алфавитном порядке, которые я буду сохранять в файл. (изначально строки не в алфавитном порядке)
Объясните на словах причем здесь хеш.(что такое хеш таблица мне извесно, но неясно как вы хотите ее здесь применить.)

Это сообщение отредактировал(а) roko - 8.2.2010, 00:23

восемь раз повторяет первый.
BEOWOLF имел ввиду, что в хеш таблицу ты будешь загонять значения (сами строки) по ключу (хеш строки)
таким образом, когда ты будешь заносить новое значение:

старое, если оно и было, будет затираться сразу, так что искать значение при вставке тебе самому и не придется

Это сообщение отредактировал(а) NewDima - 8.2.2010, 08:39

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

так что лучше просто использовать std::set - он придуман как раз для этого

NewDima, спасибо за объяснение.
maxim1000, так и сделаю.
Всем спасибо, вопрос решен.