Hi, Let my illustrate my problem, i need to make a list of "products" groups like for example for "SuperGLU", each product has its unique SERIAL_ID_START, and SERIAL_ID_END. Example: Product: "SuperGlue" SERIAL_ID_START: 0 SERIAL_ID_END: 100 Product: "BluePaint" SERIAL_ID_START: 101 SERIAL_ID_END: 120 etc. etc. And now the client wants to get the single product where SERIAL_ID is 105. The search process should return "BluePaint" product. Of course this can be easily done by implementing normal std:list container, but the problem is SPEED. There could be an N products in the shop (for example a >million), and each element in the product "list" should be erasable, also user may add an new element at any time. Std:map is fast, but the problem in this implementation is the key value. Any idea what container should i use? Binary trees maybe? Please note this program must be done in c++, no SQL is alowed :) Thanks!!

Well, with the std::map you could make your key value an std::pair, or other struct, which contains the upper and lower limits and you test against that when finding.

The other option might be boost's Multi-index container. You should be able to index on the two values and force them both to be unique in the container meaning you can't duplicate them.

Quote:Original post by phantom
Well, with the std::map you could make your key value an std::pair, or other struct, which contains the upper and lower limits and you test against that when finding.

The other option might be boost's Multi-index container. You should be able to index on the two values and force them both to be unique in the container meaning you can't duplicate them.

I'm not sure if i got you correctly, is that the thing you were talking about?:

typedef std::pair<int, int>     MyPair;typedef std::map<MyPair, DWORD>  MyMap;  // at this moment the second DWORD param is not importantMyMap	product_map;product_map.insert(make_pair(MyPair(PRODUCT1_SERIALID_START,PRODUCT1_SERIALID_END ),0));product_map.insert(make_pair(MyPair(PRODUCT2_SERIALID_START,PRODUCT2_SERIALID_END ),0));

How does this simplify the finding the specific map entry like PRODUCT1_SERIALID_START+1? You were thinking about using "find" method or iterating all the map entries?

A binary search tree would work. Create the tree using the minimum number as the primary value, then add a second value to each node which would be the maximum. When traversing the tree, you'd need to check the maximum at each node before moving to the right.

There's probably a better solution, but that should work fairly well.

Yeah, std::pair wouldn't work, however if you did it with a struct and implimented the function/operator 'find' uses to find matches and have it do the right thing you might be able to get away with it.

Although you still have the potential for overlapping ranges if you aren't careful.

Boost::Multi-index container might well be a better solution as you can do all manner of lookups on that; it does come with a bit of a learning curve however.

thanks for replying phantom and drakostar.


I was thinking about binary tree, but in bit different manner, for example
instead of finding the correct value, i would request the binary tree to find the nearest one, and then do manual check with the "neareast one" element size.
If that would fail, it means that the element is not in list. What do you think?

Now i will try to play with this BOOST library!

ToohrVyk:
I've modified your idea a bit works like a charm! Thank you! Silly me i didnt remember the "lower_bound" method!