карта C ++ с использованием пары в качестве ключа
Я использую карту (которая казалась лучшей реализацией после предыдущий вопрос, с парным ключом, в качестве «контейнера» для входящих сообщений, которые могут быть отсортированы в соответствии с sourceID и приоритетом, т.е. key: (sourceID, priority), который указывает на значение int.
Обработка будет происходить «на» этой карте.
Я только что столкнулся с проблемой — мне нужно сделать что-то вроде этого псевдокода для последующего получения сообщений:
map<pair<int, int>, int> mymap;
if (!mymap[make_pair(nodeID,i)].empty()) //i refers to all the priority levels
//processing occurs here to retrieve a value
но я не могу сделать это легко. Есть ли способ сделать это просто без запуска итератора, например for (i = 0; i <priority ; i++)? Я знаю, что если бы я использовал эквивалент vector<vector<int>> Я мог бы сделать это легко, но карта работает лучше для моей программы в данный момент.
редактировать:
Сообщения сортируются в карте по (sourceID, уровню приоритета), а затем обрабатываются перед отображением в другую карту по (destID, уровню приоритета). Мне нужно проверить, есть ли сообщения, доступные для любого конкретного destID, независимо от уровня приоритета, поэтому я ищу простой способ проверить это.
Я знаю, что если я использую вектор>, я смогу сделать что-то вроде node [2] .empty (), если я хочу проверить, что на узле 2 нет доступных сообщений. Есть ли эквивалент для карт?
Решение
Если я правильно понимаю, вы хотели бы удобный способ определить, сколько записей (node_id,i) карта имеет, где node_id является фиксированным и i может быть что угодно.
Если это понимание верно, вы можете использовать тот факт, что порядок внутри вашей карты основан на порядке, определенном std::less<std::pair<int,int>>, который по умолчанию является лексикографическим порядком. Другими словами, идентификатор узла будет использоваться в качестве основного критерия сортировки, тогда как второй элемент пары будет использоваться в качестве вторичного критерия сортировки.
Поэтому вы можете использовать lower_bound а также upper_bound функции карты для определения диапазона записей для данного идентификатора узла следующим образом (код C ++ 11, но может быть преобразован в C ++ 03):
std::ptrdiff_t num_per_node(const mymap &map, const int node_id)
{
using std::distance;
static constexpr int min = std::numeric_limits<int>::min();
static constexpr int max = std::numeric_limits<int>::max();
auto lo = map.lower_bound({node_id,min});
auto hi = map.upper_bound({node_id,max});
return distance(lo,hi);
}
Определенная выше функция возвращает количество записей на карте map для данного идентификатора узла node_id,
Таким образом, ваш псевдокод становится:
if (num_per_node(mymap,nodeID) > 0)
Функция имеет логарифмическую сложность, которая явно (асимптотически) лучше, чем итерация по всем значениям приоритета.
Обратите внимание, что это работает только потому, что элементы ваших пар intТаким образом, можно легко установить минимальные и максимальные значения. Опять же, это также работает только из-за лексикографического порядка. Если вы используете настраиваемую функцию компаратора с вашей картой, этот метод больше не будет работать, и от того, насколько точно определен ваш компаратор, можно найти соответствующий метод.
Вот GIT-гист с полным примером, который демонстрирует, как можно использовать функцию: https://gist.github.com/jogojapan/5027365
Другие решения
Просто чтобы построить то, что сделал @jogojapan, я адаптировал его так, чтобы он не использовал C ++ 11 (потому что я его не использую), и оставил его здесь для справки. Не уверен, что это делает все он делает, но работает достаточно для меня
#include <iostream>
#include <utility>
#include <limits>
#include <map>
using namespace std;
std::ptrdiff_t num_per_node(const map<pair<int, int>, int> &map, const int node_id)
{
using std::distance;
static int min = std::numeric_limits<int>::min();
static int max = std::numeric_limits<int>::max();
auto lo = map.lower_bound(make_pair(node_id,min));
auto hi = map.upper_bound(make_pair(node_id,max));
return distance(lo,hi);
}
int main() {
map<pair<int, int>, int> m;
m.insert(make_pair(make_pair(1,3),1));
m.insert(make_pair(make_pair(3,4),2));
m.insert(make_pair(make_pair(3,5),3));
m.insert(make_pair(make_pair(3,9),4));
m.insert(make_pair(make_pair(4,2),5));
m.insert(make_pair(make_pair(4,3),6));
m.insert(make_pair(make_pair(5,1),7));
m.insert(make_pair(make_pair(8,2),8));
for (int node_id = 0 ; node_id < 10 ; ++node_id)
std::cout << "node-id " << node_id << ": " << num_per_node(m,node_id) << '\n';
return 0;
}
который правильно возвращает
node-id 0: 0
node-id 1: 1
node-id 2: 0
node-id 3: 3
node-id 4: 2
node-id 5: 1
node-id 6: 0
node-id 7: 0
node-id 8: 1
node-id 9: 0
Одним из возможных решений может быть использование 2-х вложенных карт:
typedef std::map<int,int> priorities;
typedef std::map<int,priorities> messages;
Найдите, есть ли какое-либо сообщение для данного sourceId, и любой приоритет становится тривиальным по цене 2 поисков, когда вам нужно найти сообщение с данным sopurceId и приоритетом.