1

I have tried searching for this but couldn't really find a proper answer. I have a stl::set of a custom class I made.

The class looks like 

class myObject{

public:
  int a;
  int b;
  int c;

// constructor and operator < ()
}

The < comparison is based on b and c but I want to find elements in the set by a. Is there a way to do that other than performing a linear search by iterating over the set and checking for myObject.a? I am trying to get a sorted container of myObject but I need to be able to find elements in that container by the identifier a which is not really involved in the < comparison.

Chinmay Nerurkar
  • 495
  • 6
  • 22
  • I'm afraid it's not possible. – john Nov 02 '12 at 19:53
  • 2
    You could maintain a separate index for lookup by `a`. – Kerrek SB Nov 02 '12 at 19:55
  • @KerrekSB - How would I do that? I would be inserting and removing values from the set all the time too. So this index would also have to be updated with every insert and remove. Thanks. – Chinmay Nerurkar Nov 02 '12 at 20:05
  • 1
    Yes, you'd have to keep the two in sync, so you'd insert each new item in both the set and the index (e.g., map) and when you remove from the set, you'd remove the corresponding item from the map as well. – Jerry Coffin Nov 02 '12 at 20:13
  • 1
    Yes, quite. A separate multiset of iterators comes to mind. Or use a ready-made solution that does exactly that, such as boost.multiindex. – Kerrek SB Nov 02 '12 at 20:18
  • @JerryCoffin - Just out of curiosity, is there a way to avoid object duplication by using reference to the object in one of the containers? – Chinmay Nerurkar Nov 02 '12 at 21:01

1 Answers1

2

You can do it using boost::multi_index_container

class myObject
{
public:
    int a;
    int b;
    int c;
    bool operator < (const myObject& obj) const
    { return b < obj.b; }
};

using namespace boost::multi_index;
typedef multi_index_container<
    myObject,
    indexed_by<
        ordered_unique<identity<myObject> >, // index by operator <
        ordered_unique<member<myObject, int, &myObject::a> > // index by member a
  > 
> SetOfmyObjects;

typedef SetOfmyObjects::nth_index<0>::type SetIndex_b;
typedef SetOfmyObjects::nth_index<1>::type SetIndex_a;

...

    SetOfmyObjects s;
    const SetIndex_b& index_b = s.get<0>();
    SetIndex_b::iterator it_b;
    for (it_b = index_b.begin(); it_b != index_b.end(); ++it_b)
        // ordered by b
    const SetIndex_a& index_a = s.get<1>();
    SetIndex_a::iterator it_a;
    for (it_a = index_a.begin(); it_a != index_a.end(); ++it_a)
        // ordered by a
panda-34
  • 4,089
  • 20
  • 25
  • I wasn't planning on using Boost at this point in my project but that is extremely convenient. I am going to use this. Thanks for the elaborate code as its going to save me a lot of research. – Chinmay Nerurkar Nov 02 '12 at 20:32
  • will this also preserve order of insertion for duplicates? – Chinmay Nerurkar Nov 02 '12 at 21:30
  • it won't even work for duplicates, since it uses `ordered_unique` index. You asked about a set and you can't have duplicates in a set. You may use `ordered_non_unique` index that'll allow for duplicates. I don't know if it's stable. It models std::multiset, stability of which is a rather moot point. – panda-34 Nov 02 '12 at 22:27
  • Thanks for the explanation. I did ask about the set but I extended the conversation to multiset to include duplicates. I understand that std::multiset is stable only if you use C++11. I was wondering of boost has had that capability for a while. Thanks for the pointers though. I will try hunting for information in `ordered_non_unique` – Chinmay Nerurkar Nov 03 '12 at 00:01