Thread: Search a product using STD::SET find()

In order to find an object in a set, you have to lookup the object with another object.

I assume that Prod is a set<Product> and is a member variable of your Grocery class, right?

If so, then that means that Product has an operator< that sorts it by its product ID, correct?

If so, then you need to create a fake Product with the ID you want to lookup, then use that. Something like this might work:

Code:

Product lookup("", "", 0, id);
set <product>::const_iterator it = Prod.find(lookup);
if( it == Prod.end())
	cout<<"not found\n";

Originally Posted by CornedBee

That's the part I really hate about std::set. It often forces me to compromise my class invariants.
The better alternative, a std::map, still forces me to duplicate data (the ID).

I personally prefer a Boost.MultiIndex with a ordered (or even unordered) unique index using an index extractor on the ID. Then I can just pass an ID and it will look up the product.

Another option is to store the products in a sorted vector and use a binary search on the product ID. Just as efficient as map (for lookup, anyway), with no data duplication.

Originally Posted by CornedBee

More efficient than the map, in fact. But very slow on insertion. Really depends on the usage pattern here.

I would certainly hope that a product list is not updated that often Even if it took a whole second to add a new item, you're still fine, unless you're adding more than one item per second. That would be one CRAAAAZY store!

Originally Posted by CornedBee

I personally prefer a Boost.MultiIndex with a ordered (or even unordered) unique index using an index extractor on the ID. Then I can just pass an ID and it will look up the product.

That sounds great! Several times I had the problem, that I just couldn't instantiate such a "fake object", because the constructor does complex things like plugging the object into a scheduler for execution, which isn't really wanted for objects needed just to compare with. My solution was then writing an extra ctor just to create more simple comparision-objects. Think I'll try multiindex instead in the future

>> unless you're adding more than one item per second.
You'd probably only do that if you were adding items en masse a bunch at a time. In that case you'd just add them to the end and do one sort afterwards, which is still probably faster than a map. So a sorted vector is still an excellent option.

Originally Posted by CornedBee

More efficient than the map, in fact. But very slow on insertion. Really depends on the usage pattern here.

Both map and binary search are O(log N) for lookup. Are you talking about overhead or algorithmic efficiency?

Another domain-specific observation: product IDs probably increase over time as new products are added. Therefore, a new product is very likely going to end up getting inserted at the very end of the vector, which is super-cheap.

Please post the declaration of the Prod member variable. Please post the constructor declaration for the products class. Please post the implementation of the operator< for the products class.

Also, please be more specific with what happens, why do you think it doesn't work. If it doesn't compile, post compiler errors.