хэш — Как агрегировать значения в C ++, используя ключи?
В C ++, как я могу агрегировать значения для структуры на основе трех ключей?
В Perl я бы делал это, используя хэш хэшей (например, что-то вроде $ hash {$ key1} {$ key2} {$ key3} {‘call_duration’} + = 25);
Как я новичок в C ++, не могли бы вы предложить подходящий подход?
Я взглянул на темы о том, как SO обсуждает вложенные хеш-эквиваленты в C ++ с использованием std :: map, однако в нем говорится, что это медленная производительность и, поскольку мне нужно обрабатывать записи для оператора связи, производительность критична.
Необязательно, чтобы я следовал подходу, использующему библиотеку шаблонов или что-то похожее на Perl по синтаксису и образу мышления, но если вам приходилось делать что-то подобное, не могли бы вы поделиться быстрым и подходящим способом для его реализации?
Я в основном ограничен стандартом C ++ 98 (технический руководитель позволил использовать более новые функции при условии, что они поддерживаются компилятором, и они имеют критическое преимущество).
Извиняюсь, если описание запутано и заранее спасибо!
редактирование: версия компилятора — GCC 4.1.2, импорт tr1 / функциональный, поскольку библиотека не осуждается им.
редактирование: большое спасибо всем, кто присоединился, в частности к Bartek и Росту за то, что они терпели мои глупые вопросы. Я решил выбрать ответ Роста, потому что это то, что я смог получить на работе! 🙂
Решение
общий std::map должно быть подходящим, его производительность обычно не является проблемой для большинства случаев. Хэш обеспечивает постоянный доступ к элементам, древовидная карта обеспечивает логарифмическое время, но в действительности постоянное время может быть больше, чем логарифмическое — это зависит от конкретной реализации и конкретных данных. В случае, если вы заполняете контейнер один раз, а затем обновляете данные только без изменения / вставки / удаления ключа, вы можете использовать отсортированный std::vector или же Loki::AssocVector,
Вы должны сначала попробовать std::map (или же std::set если ключ является частью данных), и только тогда принимайте решение, слишком медленно это для вас или нет. Пример:
// Composite key definition
struct CompositeKey
{
int key1;
std::string key2;
AnotherType key3;
CompositeKey(int i_key1, const std::string& i_key2, AnotherType i_key3):
key1(i_key1), key2(i_key2), key3(i_key3)
{}
bool operator < (const CompositeKey& i_rhs) const
{
// You must define your own less operator for ordering keys
}
};
// Usage
std::map<CompositeKey, Data> aggrData;
aggrData[CompositeKey(0, "KeyString", AnotherType())] = Data();
if(aggrData.find(CompositeKey(0, "KeyString", AnotherType())) != aggrData.end())
{
// Process found data
}
Для дальнейшего исследования производительности вы можете попробовать:
hash_map/hash_set(названныйstdex::hash_mapв MSVC ++ и__gnu_cxx::hash_mapв GCC)boost::unordered_map/boost::unordered_setLoki::AssocVectorstd::unordered_map/std::unordered_set— только для C ++ 11
Все эти контейнеры имеют схожий интерфейс, поэтому не составит труда инкапсулировать его и легко переключать реализацию при необходимости.
Другие решения
Простое решение — использовать структуру, объединяющую 3 ключа, и использовать ее в качестве ключа.
struct Key
{
Type1 Key1;
Type2 Key2;
Type3 Key3;
// I forgot about the comparator - you have to provide it explicitly
};
Поскольку вы несколько ограничены языком, проверьте, поддерживает ли ваш компилятор std::hash_map:
std::hash_map<Key, TValue> Data;
Если нет, вы всегда можете использовать boost::unordered_map,
Если кто-то сталкивается с той же проблемой, «правильное решение», однако, заключается в следующем:
std::unordered_map<std::tuple<Type1, Type2, Type3>, TValue>;
РЕДАКТИРОВАТЬ: образец использования
struct Key
{
int Int;
float Float;
string String;
// add ctor and operator<
};
std::hash_map<Key, int> Data;
Data[Key(5, 3.5f, "x")] = 10;