在具有非关键字类型的集合中进行有效搜索

Question

我有一个类似的数据结构，如下所示：

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

现在我可以使用std::map来存储结构并按ID进行搜索，但我正在寻找一种方法来使用std::set实现同样的功能(因为我真的不需要分离ID和结构(。

std::set::find当然将密钥类型作为参数，所以我可以(使用适当的构造函数(这样做：

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

但如果可能的话，我想避免这种情况。这需要有一个允许ID不带数据的构造函数，而且我真的不喜欢构造对象，只是把它用作搜索的关键字。

所以我的问题是：有更好的方法吗？

Answer 1

除非开销明显不可接受，否则我会选择std::map<std::string, Data *>，或者可能是std::map<std::string, boost::shared_ptr<Data> >，假设您无法访问本机提供shared_ptr的编译器。

Answer 2

加上几个构造函数和一个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结果：

香蕉

我承认，这仍然创建了一个"伪"数据实例，但它似乎解决了问题。

Answer 3

如果您不反对使用Boost，那么Boost.MultiIndex会让这变得非常简单，而不会添加任何不必要的低效率。以下是一个有效创建Data对象的set的示例，该对象以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 4

更好的方法是让id索引data。但由于您不想这样做，请尝试使用std::find_if( x.first(), x.end(), --predicate-- )，其中谓词是一个函数对象或lambda函数谓词，用于将Data与指定的id进行比较。

Answer 5

我意识到这个问题是在可能之前提出的，但是：

从C++14开始，可以在一个集合中进行搜索，而无需创建密钥类型的实例，只需使用模板化密钥的std:：set:：find的额外重载。