Контейнеры STL и большие объемы данных

struct information{
  std::string name;
  unsigned int offset;
  information(information const&)=default;
  information(information&&)=default;
  information(std::string n, unsigned o):name(std::move(n)),offset(o),hash(std::hash<std::string>()(name)) {};
  information():information("",0) {};
  bool operator<( information const& o ) const {
    return tie() < o.tie();
  }
  std::tuple<std::size_t, std::string const&> tie() const { return std::tie(hash, name); }
private:
  std::size_t hash;
};

Используйте приведенную выше структуру для вашего std::vector.

После добавления всех данных std::sort его.

Чтобы найти что-то, совпадающее с name, сделайте следующее:

struct information_searcher {
  struct helper {
    std::tuple<std::size_t, std::string const&> data;
    helper( std::string const& o ):data(std::hash<std::string>()(o), o) {};
    helper( helper const& o ) = default;
    helper( information const& o ):data(o.tie()) {}
    bool operator<( helper const& o ) const { return data < o.data; }
  };
  bool operator()( helper lhs, helper rhs ) const { return lhs < rhs; }
};

information* get_info_by_name( std::string const& name ) {
  auto range = std::equal_range( vec.begin(), vec.end(), information_searcher::helper(name), information_searcher{} );
  if (range.first == range.second) {
    return nullptr;
  } else {
    return &*range.first;
  }
}

который является поиском с почти нулевыми накладными расходами.

Что мы делаем здесь, так это хешируем строки (для быстрого сравнения), возвращаясь к std::string сравнению, если у нас есть коллизия.

information_searcher — это класс, который позволяет нам искать данные без необходимости создавать information (что потребовало бы расточительного выделения памяти).

get_info_by_name возвращает указатель -- nullptr, если он не найден, и указатель на первый элемент с таким именем в противном случае.

Изменение information.name невежливо и делает поле hash неверным.

Это может использовать немного больше памяти, чем наивная версия std::vector.

В общем, если ваша работа заключается в том, чтобы «добавить кучу данных в таблицу», а затем «выполнить множество операций поиска», лучше всего создать std::vector, быстро отсортировать ее, а затем использовать equal_range для выполнения поиска. . map и unordered_map оптимизированы для большого количества смешанных вставок/удалений/и т.д.

vector обычно реализуется как «динамический массив» и должен быть наиболее эффективным с точки зрения памяти. с хорошей стратегией резервирования он может иметь вставку O (1) = fast. Поиск O(n) = очень плохой.

Вы можете помочь вектору, отсортировав его (и если вы сначала загрузите, а затем выполните поиск, чем, я думаю, будет лучше всего - std::sort + std::binary_search).
Вы также можете реализовать что-то вроде сортировки вставкой, используя std: :нижняя граница. вставка = O(log n) = хорошо, поиск = O(log n) = хорошо

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

unordered_map обычно реализуется с использованием хеш-таблиц = некоторые накладные расходы памяти, но быстрые операции (вставка не может быть такой быстрой, как в несортированном векторе, но все равно должна быть довольно быстрой). Проблема с хэшированием заключается в том, что оно может быть быстрым и даже самым быстрым, но также может быть худшим решением (в экстремальных условиях). Приведенные выше структуры (отсортированный вектор и карта/дерево стабильны, всегда ведут себя одинаково - логарифмическая сложность).

Проблема с большим вектором заключается во времени поиска, когда вы не знаете индекс нужных вам объектов. Как вы сказали, один из способов улучшить его - сохранить упорядоченный вектор и выполнить по нему двоичный поиск. Таким образом, время поиска будет иметь не линейную, а логарифмическую сложность, что позволяет сэкономить довольно много времени при работе с очень большими контейнерами. Это поиск, используемый в std::map (упорядоченный). Вы можете выполнить аналогичный двоичный поиск, используя std::lower_bound или std::equal_range на вашем std::vector.

Проблема с большой неупорядоченной картой совершенно другая: такой контейнер использует хеш-функцию и вычисление модуля для размещения элементов в соответствии с их ключами в стандартном массиве. Поэтому, когда у вас есть n элементов в std::unordered_map, очень маловероятно, что вам нужен только массив из n элементов, потому что некоторые индексы не будут заполнены. Вы будете использовать по крайней мере наибольший индекс, полученный с помощью хэш-и-модуля. Один из способов улучшить использование памяти, а также время вставки — написать собственную хеш-функцию. Но это может быть сложно в зависимости от того, какие строки вы используете.

Что ж, оптимальным решением здесь будет создание std::map, логарифмической сложности как при вставке, так и при поиске. Хотя я не вижу причин, по которым вы бы не использовали std::vector. Это довольно быстро при использовании быстрой сортировки для сортировки даже 2M элементов, особенно если вы делаете это один раз. std::binary_search работает очень быстро. Подумайте об этом, если вам нужно сделать много поисков между вставками.