Very Computer

Hi everyone,

I try to find a data structure that has all the caracteristics of a
map but with something more. I would like it to give me the first
element with the greater or smaller key than a key that I would pass
it.

Example: If I have those keys in a map: 2 5 6 10 11
If I pass it 8, it would return me the element with the key = 6 or key
= 10 depending if I want the greater or the smaller.

I found 'multimap' which I tought would be good with the functions
'lower_bound()' and 'upper_bound()'. The 'upper_bound' works exactly
as I want, but the 'lower_bound' doesn't seems to work as I tought.

I found these descriptions of the functions:

"Lower bound  a.lower_bound(k):     Returns an iterator pointing to
the first element whose key is not less than k. "

"Upper bound  a.upper_bound(k):     Returns an iterator pointing to
the first element whose key is greater than k. Returns a.end() if no
such element exists"

Since I'm french, I don't see exactly the difference between "is not
less" or "is greater". Can somebody tell me? Is it '>=' and '>'?

Or is there another data structure that I can use?

Quote:>Hi everyone,

>I try to find a data structure that has all the caracteristics of a
>map but with something more. I would like it to give me the first
>element with the greater or smaller key than a key that I would pass
>it.

>Example: If I have those keys in a map: 2 5 6 10 11
>If I pass it 8, it would return me the element with the key = 6 or key
>> 10 depending if I want the greater or the smaller.

>I found 'multimap' which I tought would be good with the functions
>'lower_bound()' and 'upper_bound()'. The 'upper_bound' works exactly
>as I want, but the 'lower_bound' doesn't seems to work as I tought.

>I found these descriptions of the functions:

>"Lower bound  a.lower_bound(k):     Returns an iterator pointing to
>the first element whose key is not less than k. "

>"Upper bound  a.upper_bound(k):     Returns an iterator pointing to
>the first element whose key is greater than k. Returns a.end() if no
>such element exists"

>Since I'm french, I don't see exactly the difference between "is not
>less" or "is greater". Can somebody tell me? Is it '>=' and '>'?

>Or is there another data structure that I can use?

Here's a question for you: given the values above (2 5 6 10 11) what would
you get back if I asked for the key less than 1?  

Quote:> Since I'm french, I don't see exactly the difference between "is not
> less" or "is greater". Can somebody tell me? Is it '>=' and '>'?

It is >=

Given

multimap <int> m.

if you use m.lower_bound() and get back an iterator, if you compare it with
m.begin() and it is not the same, then decrementing will
give you the element you want. If it is the same as m.begin() then there is
no previous element. Also, if m.upper_bound() is m.end() then there is next
element.

Quote:> Or is there another data structure that I can use?

I think it might be the right one. Your basic question is, "Do I need a
container that ordered by key, storing values, with logarithmic look up on
key, such that keys might be duplicated?" If the answer is yes, then
multimap is your container.

If you don't want duplicates then you want map
If you don't have pairs of (key, value) you just have key then you want to
be using set or multiset.

The thing about set,multiset,map,multimap is they give you fast lookup time
for elements that is logarithmic. The same is true if you insert or delete
elements, logarithmic time. You also do not need to keep it ordered, the
container will do that itself. The downside to associative containers is
that they are more expensive on memory than vector, deque, list. Also, if
you almost never do inserts or deletes, a sorted vector will beat a map on
performance. Of course inserting or deleting a arbitrary element in a vector
takes time compared to a map.

Stephen Howe

Quote:> Also, if
> you almost never do inserts or deletes, a sorted vector will beat a map on
> performance. Of course inserting or deleting a arbitrary element in a
vector
> takes time compared to a map.

Why is this?  A sorted vector (binary search) should theoretically provide
access times equal to a map (binary tree).  I suspect that it has something
to do with the fact that vectors are contiguous and therefore easily loaded
into L2/L1 cache?

Matthew D. Hall