Efective search in set with non-key type

I have a similar data structure like this:

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

Now I can use a std::map to store the structure and search by ID, but I searching for a way to achieve the same thing with a std::set (since I don't really need to separate the ID and the structure).

std::set::find of course takes the key type as a parameter, so I could do something like this (with the appropriate constructor):

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

But I would like to avoid this if possible. It would require having a constructor that allows ID without data, plus I don't really l开发者_如何学Pythonike constructing an object, just to use it as a key for search.

So my question is: Is there a better way?

Unless the overhead is demonstrably unacceptable I'd go for std::map<std::string, Data *>, or possibly std::map<std::string, boost::shared_ptr<Data> >, assuming you don't have access to a compiler that provides shared_ptr natively.

Throw in a few constructors, and an operator<, and things get super easy.

 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 results:

Banana

I admit, this does still create a "dummy" Data instance, but it seems to solve the problem.

If you're not opposed to using Boost, then Boost.MultiIndex makes this extremely simple without adding any needless inefficiency. Here's an example that effectively creates a set of Data objects that is keyed on the value of 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';
}

The better way is to have the id index the data. But since you don't want to do that, try with std::find_if( x.first(), x.end(), --predicate-- ), where predicate is a function object or lambda function predicate that compares Data against a specified id.

I realize this question was asked before this was possible, but:

Starting with C++14, it is possible to search within a set without creating instances of the key type with the additional overloads of std::set::find taking a templated key.