Простой и эффективный способ хранения данных, к которым можно получить доступ через ключ или порядковый номер C ++

Question

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

В настоящее время класс использует массив узлов, которые содержат строковый ключ и указатель на любой элемент.Это позволяет выполнять O (n) циклическое прохождение или O (1) получать элемент по порядковому номеру, однако единственный способ найти элемент по ключу - это выполнить цикл O (n) и сравнивать ключи, пока я не найдуЯ хочу, который медленный, когда есть более 1000 элементов.Есть ли способ использовать ключ для ссылки на указатель, или мне не повезло?

РЕДАКТИРОВАТЬ: порядковый номер не так важен, как цикл O (n).Это будет использоваться в качестве базовой структуры, которая будет наследоваться для использования другими способами, например, если бы это была структура объектов, которые можно рисовать, я бы хотел иметь возможность рисовать их все в одном цикле

Answer 1

Вы можете использовать std::map для O(log n) скорости поиска. Для более подробной информации просмотрите эту ветку . В этой ветке обсуждается именно ваша ситуация (быстрый поиск значений по клавише string или / и ordinal).

Небольшой пример (используются порядковые ключи, вы можете делать что-то похожее со строками):

#include <map>
#include <string>

using std::map;
using std::string;

struct dummy {
 unsigned ordinal_key;
 string dummy_body;
};

int main() 
{
 map<unsigned, dummy> lookup_map;
 dummy d1;
 d1.ordinal_key = 10;
 lookup_map[d1.ordinal_key] = d1;
 // ...
 unsigned some_key = 20;
 //determing if element with desired key is presented in map
 if (lookup_map.find(some_key) != lookup_map.end())
  //do stuff
}

Answer 2

Используйте вектор и карту:

std::vector<your_struct> elements;
std::map<std::string, int> index;

Карта позволяет вам получить индекс ключа за время O (lg n), тогда как вектор разрешает доступ к элементу O (1) по индексу.

Answer 3

Если вы редко модифицируете свой массив, вы можете просто сохранить его отсортированным и использовать binary_search , чтобы найти элемент по ключу за O(logn) время (технически O(klogn), поскольку вы используете строки [гдеk - средняя длина ключевой строки]).
Конечно, это (как и при использовании карты или unordered_map) испортит ваш порядковый поиск, так как элементы будут сохраняться в отсортированном порядке, а не в порядке вставки.

Answer 4

Использовать hashmap