самая быстрая структура данных для поиска информации c ++

Question

Я разработал клиентское приложение, которое является симулятором для TCP-клиента, возможно, имитировать 1000 клиентов.

каждая информация о состоянии клиента может иметь размер 50 байт. Информация о состоянии требуется серверу, и клиентскому симулятору необходимо хранить где-то.

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

Сервер уже реализован. Как я могу управлять этой информацией о статусе Клиента. Поскольку я не могу использовать boost и другие сторонние библиотеки, мне приходится полагаться только на c ++.

О том, как управляется информация о состоянии:

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

Какую STL / или другую структуру данных можно использовать в этом сценарии. Здесь запрещена третья библиотека.

подскажите, пожалуйста, какой из них оптимально использовать

Спасибо

Answer 1

Это зависит от того, что вам нужно с ним делать.

Если это просто простой поиск, используйте stl :: map (в STL это обычно реализовано в виде дерева, поэтому у вас есть O (lg N) поиск).

Если есть только1000 и у вас есть некоторый контроль над идентификатором, почему бы не использовать массив?Это (очевидно) даст вам O (1) доступ к любому элементу данного ключа.Если набор идентификаторов известен всем заранее, используйте Perfect Hashing , и вы также можете получить O (1) поиск.

Если честно, если у вас есть только 1000 элементов,тогда почти все будет работать чертовски быстро, если это не относится к критической по времени части кода.

Answer 2

В общем, самый быстрый равен O (1) , что является поиском с постоянным временем. Как этого добиться и, если это возможно, ограничено конкретным контекстом, который у вас есть.

Из вашего объяснения пока неясно, какие у вас есть ограничения (у сервера), и мы также не знаем, какая у него информация и как она работает.

Открытые вопросы:

• Кто знает статус?
• Кто знает о состоянии, как клиента, так и сервера?
• Что сервер «имеет доступ» до того, как хочет узнать статус клиента?
• Нужен ли серверу статус всех клиентов каждый раз?

Несколько примеров, когда сервер хочет знать статус клиента:

Сервер имеет указатель на объект клиента и статус на клиенте.

int status = client->getStatus();

Сервер имеет идентификатор клиента и статус сохраняется в массиве. Клиентские идентификаторы от 0-999.

int status = clientStatus[clientId];

Оба из вышеперечисленных являются O (1).

Если вы лучше опишите вещи, вы получите лучшие ответы.

Answer 3

Я бы предложил использовать вектор пользовательских объектов типа <key, value> с доступом O (1) с использованием хеш-функций.