Looking for container like std::map but for ranges

[guido]

Hi,

I'm looking for a container class that can map whole ranges of keys to
objects - something like std::map, but not only for individual values for
the key, but for whole ranges.

Example:
I want to be able to tell the container to return object a for every given
key between 0 and 10, object c for every key between 11 and 500000 and
object c for every key between 500001 and 599999, without having to
individually define all the 600000 values and of course without needing
600000 times whatever the size of the key+value pairs is of memory.

(The ranges are not supposed to have gaps between them, btw.)

Before I roll my own, I'd like to know if there is already a well-accepted
and tested solution out there. I didn't find anything in Boost.

Guido

 

[Jerry Coffin]

Hi,

I'm looking for a container class that can map whole ranges of keys to
objects - something like std::map, but not only for individual values for
the key, but for whole ranges.

The container just uses the comparison you define for it. To work with
ranges like this, all values within a range will be considered equal.

#include <map>
#include <iostream>
#include <string>

struct cmp {
int range(unsigned value) const {
static const unsigned bounds[] = { 11, 50001, 60000};
for (int i=0; i<3; i++)
if (value < bounds)
return i;
return -1;
}
public:
bool operator()(unsigned a, unsigned b) const {
return range(a) < range(b);
}
};

int main() {
std::map<unsigned, std::string, cmp> values;

values[5] = "String 1";
values[20] = "string 2";
values[55000] = "String 3";

std::cout << "Values[10] = " << values[10] << "\n";
return 0;
}

If you have very many ranges to deal with, you'd proably want to use a
binary search instead of a linear searhc, but for only three ranges it
wouldn't really make any noticeable difference.

 

[guido]

Jerry Coffin wrote:

The container just uses the comparison you define for it. To work with
ranges like this, all values within a range will be considered equal.

#include <map>
#include <iostream>
#include <string>

struct cmp {
int range(unsigned value) const {
static const unsigned bounds[] = { 11, 50001, 60000};
for (int i=0; i<3; i++)
if (value < bounds)
return i;
return -1;
}
public:
bool operator()(unsigned a, unsigned b) const {
return range(a) < range(b);
}
};

int main() {
std::map<unsigned, std::string, cmp> values;

values[5] = "String 1";
values[20] = "string 2";
values[55000] = "String 3";

std::cout << "Values[10] = " << values[10] << "\n";
return 0;
}

Uh, okay, maybe I should have specified this, but I was looking for a
container that would let me specify, inspect and redefine/move the range
bounds at runtime.

 

[Jerry Coffin]

[ ... ]

Uh, okay, maybe I should have specified this, but I was looking for a
container that would let me specify, inspect and redefine/move the range
bounds at runtime.

That is going to be a bit trickier. For std::map, the comparison
function is defined as a template parameter, so it can't be changed for
the life of a given map object.

If you want to change the bounds during run-time, how do you want things
to work? For example, assume I have a range 0..10, and insert an object
with a key of 7. I then adjust the bound to 0..6, and test a value of 5.
At that point, is the container supposed to show that when inserted,
there was an object in the first range, or that as the ranges are now
adjusted, there's not?

The latter sounds more sensible -- and in that case, I'm pretty sure
you're going to have to do the range checking as you retrieve items
rather than as you store them. In this case, you'd probably use
lower_bound to find both the lower and upper limits of the range (as
currently defined). The items between (if they're not equal) should be
those in that range.

 

[LR]

Hi,

I'm looking for a container class that can map whole ranges of keys to
objects - something like std::map, but not only for individual values for
the key, but for whole ranges.

Example:
I want to be able to tell the container to return object a for every given
key between 0 and 10, object c for every key between 11 and 500000 and
object c for every key between 500001 and 599999, without having to
individually define all the 600000 values and of course without needing
600000 times whatever the size of the key+value pairs is of memory.

(The ranges are not supposed to have gaps between them, btw.)

Before I roll my own, I'd like to know if there is already a well-accepted
and tested solution out there. I didn't find anything in Boost.

I don't know. I think someone asked about something similar recently in
either this group or comp.lang.c++.moderated. I think the best answer
was something like this, which might help point you in the right
direction. I don't claim this is great code, and it's certainly not
ready for production.

HTH.





#include <iostream>
#include <map>
#include <string>

typedef std::map<unsigned int, std::string> XMap;
typedef std:air<XMap::const_iterator, XMap::const_iterator> XMapCIPair;
typedef std:air<XMap::key_type, XMap::key_type> XMapKeyPair;

std:stream &operator<<(std:stream &o, const XMap::value_type &v) {
o << "[" << v.first << "] = \"" << v.second << "\"";
return o;
}
std:stream &operator<<(std:stream &o, const XMapCIPair &i) {
for(XMap::const_iterator j=i.first; j!=i.second; j++) {
o << *j << std::endl;
}
return o;
}

XMapCIPair range(const XMap &m, const XMapKeyPair &keypair) {
return XMapCIPair(m.lower_bound(keypair.first),
m.upper_bound(keypair.second));
}

int main() {
XMap m;
m[0] = "hello";
m[1] = "world";
m[2] = "this";
m[40] = "and";
m[41] = "that";
m[50] = "the";
m[51] = "other";
m[52] = "thing";

std::cout << "all of the map" << std::endl;
std::cout << XMapCIPair(m.begin(),m.end()) << std::endl;

static const XMapKeyPair test[] = {
XMapKeyPair(0,99),
XMapKeyPair(0,1),
XMapKeyPair(1,2),
XMapKeyPair(2,3),
XMapKeyPair(0,10),
XMapKeyPair(2,41),
XMapKeyPair(3,40),
XMapKeyPair(3,3),
XMapKeyPair(99,99),
XMapKeyPair(40,40),
};

for(unsigned int i=0; i<sizeof(test)/sizeof(test[0]); i++) {
const XMapKeyPair &t = test;
std::cout << i << "** trying " << t.first << " " << t.second <<
std::endl;
std::cout << range(m,t) << std::endl;
}

}

LR

 

[James Kanze]

[ ... ]

Uh, okay, maybe I should have specified this, but I was
looking for a container that would let me specify, inspect
and redefine/move the range bounds at runtime.

That is going to be a bit trickier. For std::map, the
comparison function is defined as a template parameter, so it
can't be changed for the life of a given map object.

Just a nit, but only the type of the comparator is defined as a
template parameter. The comparator itself is passed as an
argument to the constructor. It obviously can't be changed once
the map contains any elements, of course, since that would
require reordering all of the elements---in fact, it can't be
changed once the map has been constructed.

 

[Kai-Uwe Bux]

Hi,

I'm looking for a container class that can map whole ranges of keys to
objects - something like std::map, but not only for individual values for
the key, but for whole ranges.

Example:
I want to be able to tell the container to return object a for every given
key between 0 and 10, object c for every key between 11 and 500000 and
object c for every key between 500001 and 599999, without having to
individually define all the 600000 values and of course without needing
600000 times whatever the size of the key+value pairs is of memory.

(The ranges are not supposed to have gaps between them, btw.)

Should you mean that the ranges are not supposed to overlap nor to leave
gaps, then the problem can be solved using std::map<>. Just store the
right-ends of the ranges and have them point to the object.

Now, when you want to lookup a key, you can use std::lower_bound() to find
the farthest position in the map where the range whose right-end is not
less than the key.

You may need to pay special attention to the boundaries.


Best

Kai-Uwe Bux