Наличие составного ключа для хэш-карты в C ++

Question

У меня есть структура данных, которая имеет

<Book title>, <Author>, and <rate>

Поскольку название книги или автора можно дублировать, я хотел бы создать составной ключ.(допустим, я не могу создать дополнительный уникальный ключ, такой как ID)

Поскольку данные довольно большие, я использую GOR unordered_map для скорости и построил свою структуру следующим образом:

typedef pair<string, string> keys_t
typedef unordered_map<keys_t, double> map_t;

В целом все работает хорошо, но проблема возникает, когда я хочу сослаться на один конкретный ключ.

Например, предположим, я хотел бы найти книгу с самым высоким рейтингом среди книг под названием«математика», или я бы хотел найти среднюю оценку книг Толстого.В этом случае это становится очень утомительным, поскольку я не могу ссылаться только на одну из пары ключей.

Мне удалось найти boost::multi_index, но у меня возникли некоторые проблемы с пониманием документов.У кого-нибудь есть идеи или рекомендации для этого?

Решение сделать несколько индексов, краткий пример для multi_index, любой другой подход и т. Д. Любая помощь будет оценена.

Спасибо.

Answer 1

Я понял, как использовать boost::multi_index Я сослался на этот код: Увеличить составные ключи multi_index, используя MEM_FUN

и вот мой код для справки.

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/mem_fun.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/composite_key.hpp>
#include <boost/multi_index/member.hpp>
#include <iostream>
#include <string>

using namespace boost::multi_index;
using namespace std;

class Book {
public:
    Book(const string &lang1, const string &lang2, const double &value) : m_lang1(lang1) , m_lang2(lang2) , m_value(value) {}

    friend std::ostream& operator << (ostream& os,const Book& n)    {
        os << n.m_lang1 << " " << n.m_lang2 << " " << n.m_value << endl;
        return os;
    }

    const string &lang1() const { return m_lang1; }
    const string &lang2() const { return m_lang2; }
    const double &value() const { return m_value; }
private:
    string m_lang1, m_lang2;
    double m_value;
};

// These will be Tag names
struct lang1 {};
struct lang2 {};
struct value {};

typedef multi_index_container <
    Book, 
    indexed_by<
        ordered_non_unique<tag<lang1>, BOOST_MULTI_INDEX_CONST_MEM_FUN( Book, const string &, lang1)
        >,
        ordered_non_unique<tag<lang2>, BOOST_MULTI_INDEX_CONST_MEM_FUN(Book, const string &, lang2)
        >,
        ordered_non_unique<tag<value>, BOOST_MULTI_INDEX_CONST_MEM_FUN(Book, const double &, value), greater<double>
        >,
        ordered_unique<
            // make as a composite key with Title and Author
            composite_key<
                Book,
                BOOST_MULTI_INDEX_CONST_MEM_FUN(Book, const string &, lang1),
                BOOST_MULTI_INDEX_CONST_MEM_FUN(Book, const string &, lang2)
            >
        >
    >
> Book_set;

// Indices for iterators
typedef Book_set::index<lang1>::type Book_set_by_lang1;
typedef Book_set::index<lang2>::type Book_set_by_lang2;
typedef Book_set::index<value>::type Book_set_by_value;

int main() {

    Book_set books;
    books.insert(Book("Math", "shawn", 4.3));
    books.insert(Book("Math", "john", 4.2));
    books.insert(Book("Math2", "abel", 3.8));
    books.insert(Book("Novel1", "Tolstoy", 5.0));
    books.insert(Book("Novel1", "Tolstoy", 4.8)); // This will not be inserted(duplicated)
    books.insert(Book("Novel2", "Tolstoy", 4.2));
    books.insert(Book("Novel3", "Tolstoy", 4.4));
    books.insert(Book("Math", "abel", 2.5));
    books.insert(Book("Math2", "Tolstoy", 3.0));

    cout << "SORTED BY TITLE" << endl;
    for (Book_set_by_lang1::iterator itf = books.get<lang1>().begin(); itf != books.get<lang1>().end(); ++itf)
        cout << *itf;

    cout << endl<<"SORTED BY AUTHOR" << endl;
    for (Book_set_by_lang2::iterator itm = books.get<lang2>().begin(); itm != books.get<lang2>().end(); ++itm)
        cout << *itm;

    cout << endl<<"SORTED BY RATING" << endl;
    for (Book_set_by_value::iterator itl = books.get<value>().begin(); itl != books.get<value>().end(); ++itl)
        cout << *itl;

    // Want to see Tolstoy's books? (in descending order of rating)
    cout << endl;
    Book_set_by_lang2::iterator mitchells = books.get<lang2>().find("Tolstoy");
    while (mitchells->lang2() == "Tolstoy")
        cout << *mitchells++;

    return 0;
}

Спасибо всем, кто сделал комментарии!

Answer 2

В похожем случае я использовал один контейнер для хранения объекты и отдельные std::multiset<ObjectType const*, CmpType> для каждый возможный индекс; при вставке, я бы сделал push_back, а затем восстановить адрес от back() и вставьте его в каждый из std::set. (std::unordered_set и std::unordered_multiset было бы лучше в ваш случай: в моем случае, не только был значительным заказ, но я не сделал иметь доступ к последнему компилятору с unordered_set.

Обратите внимание, что это предполагает, что объекты являются неизменными, как только они находятся в контейнер. Если вы собираетесь мутировать один из них, вам, вероятно, следует извлеките его из всех наборов, внесите изменения и вставьте его заново.

Это также предполагает, что основной тип контейнера никогда не станет недействительным указатели и ссылки на объект; в моем случае я знал максимум размер впереди, так что я мог бы сделать reserve() и использовать std::vector. В противном случае вы можете использовать std::deque или просто использовать std::map для первичного (полного) ключа.

Даже для этого требуется доступ ко всему элементу ключа. Это не из ваших сообщений ясно, достаточно ли это - & ldquo; книг с названием математика и Rdquo; заставляет меня думать, что вам может понадобиться поиск подстроки в title (и должен & ldquo; Толстой & rdquo; соответствовать & ldquo; Лев Толстой и Rdquo ;?). Если вы хотите сопоставить произвольную подстроку, либо ваш мультимножество будет очень, очень большим (так как вы вставите все возможное подстроки как записи), или вы будете выполнять линейный поиск. (На длинной работает система, где записи не меняются, это может стоить компромисс: выполните линейный поиск при первом появлении подстроки запросил, но кешировал результаты в мультимножестве, так что в следующий раз, Вы можете найти их быстро. Вполне вероятно, что люди будут часто использовать те же самые подстроки, например & Ldquo; & Rdquo математика; для любой книги с & Ldquo; & Rdquo математика; в заголовке.)

Answer 3

На эту тему есть статья: http://marknelson.us/2011/09/03/hash-functions-for-c-unordered-containers/

Автор, Марк Нельсон, пытался сделать подобное: «использовать простой класс или структуру для хранения имени человека», в основном он использует пару в качестве ключа (как и вы) для своего unordered_map:

typedef pair<string,string> Name;

int main(int argc, char* argv[])
{
    unordered_map<Name,int> ids;
    ids[Name("Mark", "Nelson")] = 40561;
    ids[Name("Andrew","Binstock")] = 40562;
    for ( auto ii = ids.begin() ; ii != ids.end() ; ii++ )
        cout << ii->first.first
        << " "
        << ii->first.second
        << " : "
        << ii->second
        << endl;
        return 0;
}

Он понял, что unordered_map не знает, как создать хеш для данного типа ключа std :: pair. Поэтому он демонстрирует 4 способа создания хеш-функции для использования в unordered_map.

Answer 4

Если это нечастая операция, вы можете искать значение.

for(auto& p : m)
{
     if(p.second.name==name_to_find)
     {
          //you now have the element
     }
}

однако, если карта большая, это будет проблематично, потому что это будет линейная процедура, а не O (log n), это проблема, потому что карты по своей сути медленные.