473,700 Members | 2,500 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Looking for container like std::map but for ranges

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
Oct 4 '08 #1
7 10253
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,i ntrange;

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()(rang e const & a, range const & b) {
if(a.second < b.first) return true;
return false;
}
};

int main() {
std::map<range, int,cmpm;
m.insert(std::m ake_pair(make_r ange(-3,9),1));
m.insert(std::m ake_pair(make_r ange(10,67),2)) ;
m.insert(std::m ake_pair(make_r ange(-799,-4),3));
m.insert(std::m ake_pair(make_r ange(100,1000), 4));
m.insert(std::m ake_pair(make_r ange(66,71),5)) ; //<-!
m.insert(std::m ake_pair(make_r ange(4,17),6)); //<-!
std::cout<<m.si ze()<<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
Oct 4 '08 #2
In article <48************ ***********@new s1.pop-hannover.net>,
gu***@thisisnot atest.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()(unsi gned a, unsigned b) const {
return range(a) < range(b);
}
};

int main() {
std::map<unsign ed, 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.
Oct 4 '08 #3
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()(unsi gned a, unsigned b) const {
return range(a) < range(b);
}
};

int main() {
std::map<unsign ed, 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.
Oct 4 '08 #4
In article <48************ ***********@new s1.pop-hannover.net>,
gu***@thisisnot atest.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.
Oct 4 '08 #5
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++.m oderated. 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<unsign ed int, std::stringXMap ;
typedef std::pair<XMap: :const_iterator , XMap::const_ite ratorXMapCIPair ;
typedef std::pair<XMap: :key_type, XMap::key_typeX MapKeyPair;

std::ostream &operator<<(std ::ostream &o, const XMap::value_typ e &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.lo wer_bound(keypa ir.first),
m.upper_bound(k eypair.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.be gin(),m.end()) << std::endl;

static const XMapKeyPair test[] = {
XMapKeyPair(0,9 9),
XMapKeyPair(0,1 ),
XMapKeyPair(1,2 ),
XMapKeyPair(2,3 ),
XMapKeyPair(0,1 0),
XMapKeyPair(2,4 1),
XMapKeyPair(3,4 0),
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

Oct 4 '08 #6
On Oct 5, 12:55 am, Jerry Coffin <jcof...@taeus. comwrote:
In article <48e7cc11$0$292 81$4d3eb...@new s1.pop-hannover.net>,
gu...@thisisnot atest.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.
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 objektorientier ter Datenverarbeitu ng
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Oct 6 '08 #7
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_boun d() 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
Oct 6 '08 #8

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

3
30060
by: Woodster | last post by:
I have declared the following std::map<std::string, std::string> myMap; to pass myMap to functions should I be declaring functions as: void function(std::map<std::string, std::string>); or is there a preferred/better method of doing this?
1
1864
by: Antti Granqvist | last post by:
Hello! I have following object relations: Competition 1--* Category 1--* Course 1 | | * Course
2
3395
by: Serengeti | last post by:
Hello, in my class I have a map that translates strings to pointers to some member functions. The code goes like this: class F { typedef void (Function::*MathFuncPtr)(); std::map<std::string, MathFuncPtr> predefinedFunctions; // lots of other stuff void makeDictionary(){ predefinedFunctions=&F::f_sin(); } };
1
3551
by: Saeed Amrollahi | last post by:
Dear All C++ Programmers Hello I am Saeed Amrollahi. I am a software engineer in Tehran Sewerage Company. I try to use std::map and map::find member function. I use Visual Studio .NET. my program uses two MFC classes: CRect and CPoint which represents Rectangle and Point concepts (as usual) and a user
19
6150
by: Erik Wikström | last post by:
First of all, forgive me if this is the wrong place to ask this question, if it's a stupid question (it's my second week with C++), or if this is answered some place else (I've searched but not found anything). Here's the problem, I have two sets of files, the name of a file contains a number which is unique for each set but it's possible (even probable) that two files in different sets have the same numbers. I want to store these...
3
3710
by: Dan Trowbridge | last post by:
Hi everyone, In my attempt to port code from VS 6.0 to VS.NET I had some code break along the way, mostly due to not adhereing closely to the C++ standard. This may be another instance but I can't think of a good fix, or even why it broke. The problem In one of my CFormView derived classes I have a member variable of the type...
1
6475
by: Avery Fong | last post by:
The following program will result in a compile error when building under Debug but will compile under Release. Why does is work under Release mode but not under Debug This program is developed under Visual Studio .NET 2003 in a Win32 Console Project // VectorInsert.cpp : Defines the entry point for the console application / #include "stdafx.h #include "VectorInsert.h #ifdef _DEBU
13
9669
by: kamaraj80 | last post by:
Hi I am using the std:: map as following. typedef struct _SeatRowCols { long nSeatRow; unsigned char ucSeatLetter; }SeatRowCols; typedef struct _NetData
8
4357
by: xuatla | last post by:
Hi, I want to define a map: std::map<string, intmyMap; e.g., the score of students. Then I can assign the value as follows: myMap = 90; myMap = 60; ....
0
8726
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
8645
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
0
9214
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
1
8973
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
5903
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
4404
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
0
4657
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
3089
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
2
2392
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.