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

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

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

Станд. попытки:: карта.

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

Прежде всего необходимо смочь определить количество опций. Вы также сказали нам, что основной шаблон использования, которым Вы интересуетесь, является поиском, не вставкой.

Позволить 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. В случае a std::map- основанный подход (который использует красно-черные деревья), для каждого поиска Вы оплачиваете следующие издержки:

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

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

Прежде, чем принять любое решение, тем не менее, необходимо также проверить:

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

кажется, что массив работал бы просто великолепно, где индекс является индексом в массив. Чтобы проверить, существует ли это, просто удостоверьтесь, что индекс находится в границах измерения массива и что его запись не является ПУСТОЙ.

Править: при сортировке списка Вы могли бы всегда использовать двоичный поиск, который должен иметь быстрый поиск.

Править: Кроме того, если Вы хотите искать строку, можно всегда использовать a std::map<std::string, int> также. Это должно иметь некоторые достойные скорости поиска.

Самый легкий должен использовать станд.:: карта.

Это работает как это:

#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")

Google редкий хеш, возможно,