Эффективный поиск в наборе с неключевым типом

Question

У меня похожая структура данных:

struct Data { std::string id; Blob data; };

Теперь я могу использовать std::map для хранения структуры и поиска по идентификатору, но я искал способ добиться того же с помощью std::set (поскольку мне действительно не нужно разделять идентификатор и структура).

std::set::find, конечно, принимает тип ключа в качестве параметра, поэтому я мог бы сделать что-то вроде этого (с соответствующим конструктором):

set<Data> x; x.find(Data("some_id"));

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

Итак, мой вопрос: есть ли лучший способ?

Answer 1

Если вы не против использования Boost , то Boost.MultiIndex делает это чрезвычайно простым без добавления любой ненужной неэффективности.Вот пример, который эффективно создает set из Data объектов, которые имеют значение Data::id:

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

namespace bmi = boost::multi_index;

typedef char const* Blob;

struct Data
{
    std::string id;
    Blob data;

    void display() const { std::cout << "id: " << id << '\n'; }
};

typedef bmi::multi_index_container<
    Data,
    bmi::indexed_by<
        bmi::ordered_unique<
            bmi::member<Data, std::string, &Data::id>
        >
    >
> DataSet;

int main()
{
    Data d1 = { "some_id", nullptr };
    Data d2 = { "some_other_id", nullptr };

    DataSet set;
    set.insert(d1);
    set.insert(d2);

    set.find("some_id")->display();

    // for exposition, find is actually returning an iterator
    DataSet::const_iterator iter = set.find("some_other_id");
    if (iter != set.end())
        iter->display();

    // set semantics -- newly_added is false here, because the
    // container already contains a Data object with id "some_id"
    Data d3 = { "some_id", "blob data" };
    bool const newly_added = set.insert(d3).second;
    std::cout << std::boolalpha << newly_added << '\n';
}

Answer 2

Если накладные расходы явно недопустимы, я бы выбрал std::map<std::string, Data *> или, возможно, std::map<std::string, boost::shared_ptr<Data> >, предполагая, что у вас нет доступа к компилятору, который предоставляет shared_ptr изначально.

Answer 3

Добавьте несколько конструкторов и operator<, и все станет супер просто.

 struct Data { 
    std::string id; 
    Blob data; 

    Data(const char* r) : id(r), data() {}
    bool operator<(const Data & r) const {return id<r.id;}

    // rest not needed for demo, but handy
    Data() : id(), data() {}
    Data(std::string&& r) : id(std::move(r)), data() {}
    Data(const std::string& r) : id(r), data() {}
    Data(Data && r) : id(r.id), data(r.data) {}
    Data(const Data & r) : id(r.id), data(r.data) {}
    ~Data() {} 
};

int main() {
    std::set<Data> x;
    x.insert("Apple");
    x.insert("Banana");
    x.insert("Orange");
    x.insert("Grape");

    std::set<Data>::iterator i = x.find("Banana");
    if (i != x.end())
        std::cout << i->id;
    else 
        std::cout << "ERR";
}

http://ideone.com/nVihc Результаты:

Бананы

Я признаю, что это все еще создает "фиктивный" экземпляр Data, но, похоже, это решает проблему.

Answer 4

Я понимаю, что этот вопрос задавался до того, как это стало возможным, но:

Начиная с C ++ 14, можно выполнять поиск в наборе, не создавая экземпляры типа ключа с дополнительными перегрузками std :: set :: find , берущими шаблонный ключ.

Answer 5

Лучше всего иметь индекс id для data. Но так как вы не хотите этого делать, попробуйте использовать std::find_if( x.first(), x.end(), --predicate-- ), где предикат - это функциональный объект или лямбда-предикат функции, который сравнивает Data с указанным id.