Есть ли способ ограничить размер STL-карты?
Я хочу реализовать некоторую таблицу поиска в С++, которая будет действовать как кеш. Он предназначен для эмуляции части оборудования, которое я имитирую.
Ключи нецелые, поэтому я предполагаю, что хэш в порядке. Я не собираюсь изобретать колесо, поэтому я намерен использовать std::map
для этого (хотя предложения по альтернативам приветствуются).
Вопрос в том, есть ли способ ограничить размер хэша, чтобы подражать факту, что мое оборудование имеет конечный размер? Я бы ожидал, что метод хеш-вставки вернет сообщение об ошибке или выдаст исключение, если предел достигнут.
Если такого пути нет, я просто проверю его размер, прежде чем пытаться вставить его, но это похоже на неэлегантный способ сделать это.
Ответы
Ответ 1
Прежде всего, структура map
не является hash table
, а скорее сбалансированным двоичным деревом. Это влияет на время поиска O(log N)
вместо O(1)
для оптимальной реализации хэша. Это может повлиять или не повлиять на вашу проблему (если количество фактических ключей и операций невелико, этого может быть достаточно, но эмуляция кеша может быть как-то субоптимальной.
Самое простое решение, которое вы можете сделать, - инкапсулировать фактическую структуру данных в класс, который проверяет размер в каждой вставке (поиск по размеру должен быть реализован в постоянное время во всех реализациях STL) и сбой, если вы тоже пытаетесь добавить его много элементов.
class cache {
public:
static const int max_size = 100;
typedef std::map<key_t, value_t> cache_map_t;
void add( key_t key, value_t value ) {
cache_map_t::const_iterator it = m_table.find( key );
if ( it != m_table.end() && m_table.size() == max_size ) {
// handle error, throw exception...
} else {
m_table.insert( it, std::make_pair(key,value) );
}
}
private:
cache_map_t m_table;
};
// Don't forget, in just one translation unit:
const int cache::max_size;
Ответ 2
Невозможно "автоматически" ограничить размер std::map
, просто потому, что "ограниченный std::map
" больше не будет std::map
.
Оберните std::map
в свой собственный класс, который просто проверяет размер std::map
на константу перед вставкой и делает все, что вы хотите, в случае достижения максимального размера.
Ответ 3
Если вы используете кеши LRU или аналогичные, я нашел boost:: bimap, чтобы быть бесценным. Используйте один индекс как основной ключ "идентификатор объекта" (который может быть эффективным векторным представлением, если у вас есть простая перечисление объектов), а другой индекс может быть упорядоченной меткой времени.