CODEWITHSUNDEEP
c++boostvectorstlset
Cookie
Cookie

Reputation: 12652

Replacing std::map with std::set and search by index

Say we have a map with larger objects and an index value. The index value is also part of the larger object.

What I would like to know is whether it is possible to replace the map with a set, extracting the index value.

It is fairly easy to create a set that sorts on a functor comparing two larger objects by extracting the index value.

Which leaves searching by index value, which is not supported by default in a set, I think.

I was thinking of using std::find_if, but I believe that searches linearly, ignoring the fact we have set.

Then I thought of using std::binary_search with a functor comparing the larger object and the value, but I believe that it doesn't work in this case as it wouldn't make use of the structure and would use traversal as it doesn't have a random access iterator. Is this correct? Or are there overloads which correctly handle this call on a set?

And then finally I was thinking of using a boost::containter::flat_set, as this has an underlying vector and thus presumably should be able to work well with std::binary_search?

But maybe there is an all together easier way to do this?

Before you answer just use a map where a map ought to be used - I am actually using a vector that is manually sorted (well std::lower_bound) and was thinking of replacing it with boost::containter::flat_set, but it doesn't seem to be easily possible to do so, so I might just stick with the vector.

Upvotes: 1

Views: 199

Answers (3)

Mankarse
Mankarse

Reputation: 40603

C++14 will introduce the ability to lookup by a key that does not require the construction of the entire stored object. This can be used as follows:

#include <set>
#include <iostream>

struct StringRef {
    StringRef(const std::string& s):x(&s[0]) { }
    StringRef(const char *s):x(s) { std::cout << "works: " << s << std::endl; }
    const char *x;    
};

struct Object {
    long long data;
    std::size_t index;
};
struct ObjectIndexer {
    ObjectIndexer(Object const& o) : index(o.index) {}
    ObjectIndexer(std::size_t index) : index(index) {}
    std::size_t index;
};
struct ObjComp {
    bool operator()(ObjectIndexer a, ObjectIndexer b) const { 
        return a.index < b.index; 
    }
    typedef void is_transparent; //Allows the comparison with non-Object types.
};

int main() {
    std::set<Object, ObjComp> stuff;
    stuff.insert(Object{135, 1});
    std::cout << stuff.find(ObjectIndexer(1))->data << "\n";
}

More generally, these sorts of problems where there are multiple ways of indexing your data can be solved using Boost.MultiIndex.

Upvotes: 3

Claire Andrews
Claire Andrews

Reputation: 301

If you add the following to your contained object type:

  • less than operator that only compares the object indices
  • equality operator that only compares the object indices
  • a constructor that takes your index type and initializes a dummy object with that value for the index

then you can pass your index type to find, lower_bound, equal_range, etc... and it will act the way you want. When you pass your index to the set's (or flat_set's) find methods it will construct a dummy object of the contained type to use for the comparisons.

Now if your object is really big, or expensive to construct, this might not be the way you want to go.

Upvotes: 0

jasal
jasal

Reputation: 1053

Use boost::intrusive::set which can utilize the object's index value directly. It has a find(const KeyType & key, KeyValueCompare comp) function with logarithmic complexity. There are also other set types based on splay trees, AVL trees, scapegoat trees etc. which may perform better depending on your requirements.

Upvotes: 1

Related Questions