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

[Obnoxious User]

On Sat, 04 Oct 2008 19:07:50 +0200, guido wrote:

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.

You mean something like:

#include <iostream>
#include <map>

typedef std::pair<int,intrange;

range make_range(int lower, int upper) {
if(upper < lower) {
return std::make_pair(upper,lower);
}
return std::make_pair(lower,upper);
}

struct cmp {
bool operator()(range const & a, range const & b) {
if(a.second < b.first) return true;
return false;
}
};

int main() {
std::map<range,int,cmpm;
m.insert(std::make_pair(make_range(-3,9),1));
m.insert(std::make_pair(make_range(10,67),2));
m.insert(std::make_pair(make_range(-799,-4),3));
m.insert(std::make_pair(make_range(100,1000),4));
m.insert(std::make_pair(make_range(66,71),5)); //<-!
m.insert(std::make_pair(make_range(4,17),6)); //<-!
std::cout<<m.size()<<std::endl;
std::cout<<m[make_range(-27,-27)]<<std::endl;

return 0;
}

--
OU
Remember 18th of June 2008, Democracy died that afternoon.
http://frapedia.se/wiki/Information_in_English

[Jerry Coffin]

In article <48***********************@news1.pop-hannover.net>,
gu***@thisisnotatest.de says...

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[i])
return i;
return -1;
}
public:
bool operator()(unsigned a, unsigned b) const {
return range(a) < range(b);
}
};

int main() {
std::map<unsigned, std::string, cmpvalues;

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.

--
Later,
Jerry.

The universe is a figment of its own imagination.

[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[i])
return i;
return -1;
}
public:
bool operator()(unsigned a, unsigned b) const {
return range(a) < range(b);
}
};

int main() {
std::map<unsigned, std::string, cmpvalues;

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]

In article <48***********************@news1.pop-hannover.net>,
gu***@thisisnotatest.de says...

[ ... ]

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.

--
Later,
Jerry.

The universe is a figment of its own imagination.

[LR]

guido wrote:

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::stringXMap;
typedef std::pair<XMap::const_iterator, XMap::const_iteratorXMapCIPair;
typedef std::pair<XMap::key_type, XMap::key_typeXMapKeyPair;

std::ostream &operator<<(std::ostream &o, const XMap::value_type &v) {
o << "[" << v.first << "] = \"" << v.second << "\"";
return o;
}
std::ostream &operator<<(std::ostream &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[i];
std::cout << i << "** trying " << t.first << " " << t.second <<
std::endl;
std::cout << range(m,t) << std::endl;
}

}

LR

[James Kanze]

On Oct 5, 12:55 am, Jerry Coffin <[e-mail]:

In article <48e7cc11$0$29281$[e-mail]>,
[e-mail] says...

[ ... ]

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.

--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, [phone]

[Kai-Uwe Bux]

guido wrote:

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