контейнер для быстрого поиска имени

Question

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

Answer 1

Я бы предложил tr1 :: unordered_map. Он реализован в виде хэш-карты, поэтому он имеет ожидаемую сложность O (1) для поиска и худший вариант O (n). Существует также расширенная реализация, если ваш компилятор не поддерживает tr1.

#include <string>
#include <iostream>
#include <tr1/unordered_map>

using namespace std;

int main()
{
    tr1::unordered_map<string, int> table;

    table["One"] = 1;
    table["Two"] = 2;

    cout << "find(\"One\") == " << boolalpha << (table.find("One") != table.end()) << endl; 
    cout << "find(\"Three\") == " << boolalpha << (table.find("Three") != table.end()) << endl; 

    return 0;
}

Answer 2

попробуйте это:

_{(источник: adrinael.net )}

Answer 3

Попробуйте std :: map.

Answer 4

В первую очередь вы должны иметь возможность определить ваши параметры. Вы также сказали нам, что основной интересующий вас шаблон использования - это поиск , а не вставка.

Позвольте N быть числом строк, которое вы ожидаете иметь в таблице, и пусть C будет средним числом символов в любой данной строке, представленной в указанной таблице (или в строках которые сверяются с таблицей).

1. В случае подхода на основе хеша , за каждый поиск вы оплачиваете следующие расходы:

   • O(C) - вычисление хэша для строки, которую вы собираетесь найти
   • между O(1 x C) и O(N x C), где 1..N - это цена, которую вы ожидаете от обхода сегмента на основе хеш-ключа, здесь умноженная на C для повторной проверки символов в каждой строке на соответствие ключу поиска
   • общее время: от O(2 x C) до O((N + 1) x C)

2. В случае подхода std::map (в котором используются красно-черные деревья), за каждый поиск вы платите следующие расходы:

   • общее время: между O(1 x C) и O(log(N) x C) - где O(log(N)) - максимальная стоимость обхода дерева, а O(C) - время, которое универсальная less<> реализация std::map берет для перепроверки вашего ключа поиска при обходе дерева

В случае больших значений для N и при отсутствии хеш-функции, которая гарантирует коллизии меньше, чем log (N), или, если вы просто хотите воспроизвести ее безопасно, лучше использовать основанный на деревьях (std::map) подход . Если N мало, во что бы то ни стало, используйте подход, основанный на хешировании (все же следя за тем, чтобы коллизия хешей была низкой).

Однако, прежде чем принимать какое-либо решение, вам также следует проверить:

• http://meshula.net/wordpress/?p=183
• http://wyw.dcweb.cn/mstring.htm

Answer 5

Строки для поиска доступны статически? Возможно, вы захотите взглянуть на идеальную функцию хеширования

Answer 6

звучит так, как будто массив будет работать нормально, если индекс - это индекс в массиве. Чтобы проверить, существует ли он, просто убедитесь, что индекс находится в границах массива и что его запись не равна NULL.

РЕДАКТИРОВАТЬ: если вы сортируете список, вы всегда можете использовать двоичный поиск, который должен иметь быстрый поиск.

РЕДАКТИРОВАТЬ: Кроме того, если вы хотите найти строку, вы всегда можете также использовать std::map<std::string, int>. Это должно иметь приличную скорость поиска.

Answer 7

Проще всего использовать std :: map.

Работает так:

#include <map>
using namespace std;

...

   map<string, int> myContainer;
   myContainer["foo"] = 5; // map string "foo" to id 5
   // Now check if "foo" has been added to the container:
   if (myContainer.find("foo") != myContainer.end())
   {
       // Yes!
       cout << "The ID of foo is " << myContainer["foo"];
   }
   // Let's get "foo" out of it
   myContainer.erase("foo")

Answer 8

Google разреженный хеш возможно