Efective search in set with non-key type

Question

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?

Just use a `Map`. There's really nothing wrong with storing the id twice. If it bothers you, make it a `Map` and extract the two fields from the `struct` at insertion time. — i_am_jorf, Sep 20 '11 at 16:00
I've searched the standard. You can use a non-Data key, but it will use O(n) iterator advancements (log(n) comparisons). Or you can use a Data key for O(log(n)). Unfortunately, if you don't want either, you have to use std::map. — Mooing Duck, Sep 20 '11 at 17:41
Possible duplicate of [Is it possible to use elements of a different type than contained in a std::set to perform search and deletion?](http://stackoverflow.com/questions/17375780/is-it-possible-to-use-elements-of-a-different-type-than-contained-in-a-stdset) — Ciro Santilli OurBigBook.com, Jan 12 '17 at 23:38

score 1 · Accepted Answer · answered Sep 20 '11 at 16:01

1

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.

answered Sep 20 '11 at 16:01

Nicola Musatti

17,834
2
46
55

score 1 · Answer 2 · answered Sep 20 '11 at 16:14

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.

ildjarn · Answer 3 · 2011-09-20T16:23:32.517

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

score 0 · Answer 4 · answered Nov 29 '16 at 10:19

0

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.

answered Nov 29 '16 at 10:19

zennehoy

6,405
28
55

score 0 · Answer 5 · answered Sep 20 '11 at 15:57

0

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.

answered Sep 20 '11 at 15:57

K-ballo

80,396
20
159
169

Won't that degrade the search to linear complexity? – Šimon Tóth Sep 20 '11 at 15:58
@Let_Me_Be: Yeap, that's why you should use a `std::map` instead. – K-ballo Sep 20 '11 at 15:59
@MooingDuck How does that help exactly? – Šimon Tóth Sep 20 '11 at 16:20
std::set::find_lower_bound is logarithmic instead of linear. I'd forgotten you were trying to do this without creating a `Data` instance to search by though. – Mooing Duck Sep 20 '11 at 16:25

Efective search in set with non-key type

5 Answers5

Linked