Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > STL Добавление в отсортированный массив

Автор: roko 7.2.2010, 22:26

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

Код


char* p1="that";
char* p2="alpha";
char* p3="color";
char* p4="despite";
char* p5="alpha";

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

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

Автор: Ozerich 7.2.2010, 22:40

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

Автор: roko 7.2.2010, 22:56

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

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

Автор: BEOWOLF 7.2.2010, 23:07

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

Код


#define DO1 crc = table[(unsigned char)(crc) ^ *data++] ^ (crc >> 8)
#define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1

static CRC32 _CRC32(const unsigned char* data, size_t len, CRC32 crc, const CRC32* table)
{
    if (!data) return crc;

    while (len >= 8) {
        DO8;
        len -= 8;
    }
    while (len--) {
        DO1;
    }
    return crc;
}

CRC32 CRC32IEEE(const void* data, size_t len, CRC32 crc)
{
    static CRC32 table[256];
    static const watchdog wd(0xEDB88320, table);

    return _CRC32((const unsigned char*)data, len, crc, table);
}

Добавлено через 9 минут и 18 секунд
да, ещё одну фичу не дописал для инициализации таблицы:

Код


struct watchdog {
    watchdog(const CRC32 CRC_POLY, CRC32* table) {
        unsigned i, j;
        unsigned r;
        for (i = 0; i < 256; i++){
            for (r = i, j = 8; j; j--)
                if (r & 1) r = (r >> 1) ^ CRC_POLY;
                else r >>= 1;
                table[i] = r;
        }
    };
};

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

Автор: roko 8.2.2010, 00:08

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

Автор: NewDima 8.2.2010, 08:35

Цитата

что делает второй define?

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

Код


CRC32 crc32(char *buffer) {...}
...
    char *u[] = {
        "that"
      , "alpha"
      , "color"
      , "despite"
      , "alpha"
    };
    std::map<CRC32, std::string> map;
    for (char *string = u[0]; string < u[sizeof(u)/sizeof(u[0])]; ++string) {
        map[crc32(string)] = string;
    }

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

Автор: maxim1000 8.2.2010, 09:15

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

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

Автор: roko 8.2.2010, 16:01

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