Хранение и поиск большого набора данных

Question

Я относительно новичок в программировании на C++, и я пытаюсь создать набор данных, который имеет только два значения: идентификационный номер и строку. Их будет около 100 000 пар. Я просто не уверен, какая структура данных наилучшим образом соответствует моим потребностям.

Набор данных имеет следующие требования:

-The идентификационный номер, соответствующий строка 6 цифр (так 000000 до 999999)

-не все значения ID между 000000 и 999999 будут использоваться

-Пользователь не будет иметь разрешение на изменение набора данных

-Жаль поиск по ID или слова в строке и вернуться к пользовательскому ID и строки

- скорость поиска важна

Итак, в основном мне интересно, что я должен использовать (вектор, список, массив, базу данных SQL и т. Д.), Чтобы построить этот набор данных и быстро найти его?

Answer 1

идентификационный номер, соответствующий строке 6 цифр (так 000000 до 999999)

Хорошо, используйте int, или более точно int32_t для ID

-не все значения ID твин 000000 и 999999 будет использоваться

Не проблема ...

-Пользователь не будет иметь разрешение на изменение данных установлено

Инкапсуляция данных в классе и вы готовы пойти

-Я хочу выполнить поиск по ID или словам в строке и вернуться к идентификатору пользователя и строке

Хорошо использовать Boost.Bimap

Скоростная поисков важно

Я знаю, именно поэтому вы используете C++ ... :-)

Вы можете также хотите проверить SQLite: SQLite, также может работать как база данных в памяти.

Answer 2

использование станд :: Карта

void main() 
{ 
    std::map<string /*id*/, string> m; 
    m["000000"] = "any string you want"; 
} 

Answer 3

У вас есть несколько вариантов.

1. Используйте базу данных MySQL, SQLite и т. Д.Производительность зависит от используемой вами базы данных.

2. Или, если вы хотите сделать это в коде на C++, вы можете использовать векторы. Один вектор для ключа, другой - для строки. Вам также нужно сопоставить соответствующий индекс между двумя векторами.

Сортировка обоих векторов после добавления нового товара. Не забудьте обновить карту соответствующего индекса

Затем используйте двоичный поиск, чтобы найти либо ключ, либо значение. Он должен быть достаточно быстрым.

Answer 4

Список: & Список наименее используемых, если вы их не сортируете, вы не хотите проходить через все. Предлагаю вам использовать карту, даже если построить всю карту может потребоваться больше времени (nlogn). Я по-прежнему рекомендую его, так как время выполнения для поиска - log (n), которое довольно быстро!

«скорость поиска важна»

Answer 5

Я хотел бы предложить что-то вроде класса, который содержит вектор ваших ID/строковые пары, в unordered_map, отображающую идентификатор итератора или ссылки на которые vector и unordered_map, который отображает строку в итератор или ссылку в этот вектор. Затем две функции поиска в классе, которые ищут пару id/string на основе идентификатора или строки.