CODEWITHSUNDEEP
c++stl
Šimon Tóth
Šimon Tóth

Reputation: 36433

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 like constructing an object, just to use it as a key for search.

So my question is: Is there a better way?

Upvotes: 1

Views: 739

Answers (5)

zennehoy
zennehoy

Reputation: 6846

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.

Upvotes: 1

ildjarn
ildjarn

Reputation: 62975

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';
}

Upvotes: 1

Mooing Duck
Mooing Duck

Reputation: 66922

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.

Upvotes: 1

Nicola Musatti
Nicola Musatti

Reputation: 18218

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.

Upvotes: 1

K-ballo
K-ballo

Reputation: 81349

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.

Upvotes: 0

Related Questions