Effective search in a set with a non-key

Question

I have a similar data structure:

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

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

std::set::find , of course, takes the type key 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. This will require a constructor that allows an ID without data, plus I don’t really like to construct an object, just to use it as a search key.

So my question is: is there a better way?

Answer 1

If the overhead is clearly unacceptable, I would go to std::map<std::string, Data *> or maybe std::map<std::string, boost::shared_ptr<Data> > , assuming that you do not have access to the compiler that provides shared_ptr natively.

Answer 2

Throw a few constructors and operator< , and everything will become simpler.

  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:

Bananas

I admit that this still creates an instance of "dummy" Data, but it seems to solve the problem.

Answer 3

If you don't mind using Boost , then Boost.MultiIndex makes this extremely easy without adding any unnecessary inefficiencies. Here is an example that effectively creates set objects from Data , which are entered into the Data::id value:

 #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

It is best to have an id data index. But since you do not want to do this, try with std::find_if( x.first(), x.end(), --predicate-- ) , where the predicate is a function object or a predicate of a lambda function that compares data with specified id .

Answer 5

I understand that this question was asked before it was possible, but:

Starting with C ++ 14, you can search inside a set without creating instances of the key type with additional overloads of std :: set :: find with the template.