Sign in to follow this  

Best container for me.

This topic is 3374 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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!!

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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 important

MyMap 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?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

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!

Share this post


Link to post
Share on other sites
Assuming non-overlapping intervals:
struct edge { product_id product; enum type { START, END } side; };

typedef std::map<int,edge> intervals;

void add_interval(intervals& i, product_id id, int min, int max)
{
edge start = { id, START };
edge end = { id, END ];

i[min] = start;
i[max] = end;
}

boost::optional<product_id> get(const intervals& i, int pos)
{
intervals::const_iterator found =
i.lower_bound(pos);

if (found == i.end() || found -> second.side == START)
return boost::optional<product_id>();

return found->second.product;
}


Of course, if there are no holes between intervals, you can get away with storing only the end edge. Both methods get even faster if the list of products changes infrequently, since you can then use an array with the std::lower_bound function for improved speed.

Share this post


Link to post
Share on other sites

This topic is 3374 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this