словарь — поиск карты C ++ для авторизации
Мне интересно, каковы эффективные способы поиска карты для групп пользователей. Предположим, у нас есть карта конкретных объектов, для которых у группы пользователей есть разрешение на доступ к ней.
Будет ли лучше создать еще одну карту для каждой группы пользователей, чтобы иметь более быстрый доступ?
Решение
Это действительно зависит от ваших ожидаемых моделей использования. У вас есть три типа объектов:
- объекты
- группы
- пользователи
Для упрощения давайте сосредоточимся только на последнем 2.
-
Оптимизируете ли вы случай, когда для данной группы вы хотите проверить, принадлежит ли ей конкретный пользователь?
-
Эффективно ли удаление пользователя из всех групп? Должно ли это повлиять на других пользователей в многопоточной среде? Должно ли это быть атомным, если так?
-
Вы оптимизируете по размеру или скорости?
В зависимости от ответов (на эти и, возможно, на многие другие вопросы) вам могут подойти разные решения.
Например, рассмотрим следующее:
#include <unordered_map>
#include <unordered_set>
using user_id_t = std::size_t;
using group_id_t = std::size_t;
using group_to_users_t = std::unordered_map<group_id_t, std::unordered_set<user_id_t>>;
int main() {
group_to_users_t authorized;
authorized[3].insert(20);
}
Это использует std::unordered_map сопоставить каждую группу с std::unordered_set пользователей. Он показывает, как вставить пользователя 20 в группу 3. Это очень эффективно при запросе, если пользователь 20 принадлежит группе 3. Это очень неэффективно для ответа, к каким группам принадлежит пользователь 20.
И наоборот, учтите следующее:
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/identity.hpp>
#include <boost/multi_index/member.hpp>
using namespace boost;
using namespace boost::multi_index;
struct permission {
std::size_t m_group_id;
std::size_t m_user_id;
};
using permissions_t = multi_index_container<
permission,
indexed_by<
ordered_non_unique<member<permission, decltype(permission{}.m_user_id), &permission::m_user_id>>,
ordered_non_unique<member<permission,std::size_t,&permission::m_group_id>>>>;
int main() {
permissions_t permissions;
permission foo{3, 20};
permissions.insert(foo);
}
Он использует boost::multi_index::multi_index_container одновременно сопоставить разрешение как группы, так и пользователя. Поэтому он обеспечивает эффективный доступ как для группы, так и для пользователя; и наоборот, это более сложный объект с большими накладными расходами пространства и времени.
Другие решения