c++ >> std::maps within std::maps -- optimisation

by Simon Elliott » Wed, 09 Mar 2005 21:12:58 GMT

Here's a small example which uses std::maps within std::maps. Note the
line flagged // *** copy?

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

struct Tfoo
Tfoo(int i1, int i2):i1_(i1),i2_(i2){}
int i1_;
int i2_;

typedef std::map<std::string, Tfoo> TfooMapInner;
typedef std::map<std::string, TfooMapInner> TfooMapOuter;

int main(int argc, char **argv)
TfooMapOuter myFooMapOuter;

TfooMapInner myFooMapInner;
myFooMapInner["inner_key_1"] = Tfoo(0,1);
myFooMapInner["inner_key_2"] = Tfoo(0,2);
myFooMapOuter["outer_key_1"] = myFooMapInner;

TfooMapInner myFooMapInner;
myFooMapInner["inner_key_3"] = Tfoo(0,3);
myFooMapInner["inner_key_4"] = Tfoo(0,4);
myFooMapOuter["outer_key_2"] = myFooMapInner;

TfooMapOuter::const_iterator ipOuter;
TfooMapOuter::const_iterator epOuter = myFooMapOuter.end();
for (ipOuter=myFooMapOuter.begin(); ipOuter!=epOuter; ++ipOuter)
const std::string& outerKey = (*ipOuter).first;
const TfooMapInner& fooMapInner = (*ipOuter).second; // *** copy?
TfooMapInner::const_iterator ipInner;
TfooMapInner::const_iterator epInner = fooMapInner.end();
for (ipInner=fooMapInner.begin(); ipInner!=epInner; ++ipInner)
const std::string& innerKey = (*ipInner).first;
const Tfoo& foo = (*ipInner).second;
cout << outerKey << " " << innerKey << " " << foo.i1_ << " "
<< foo.i2_ << std::endl;

return 0;

This produces the output I expected:

outer_key_1 inner_key_1 0 1
outer_key_1 inner_key_2 0 2
outer_key_2 inner_key_3 0 3
outer_key_2 inner_key_4 0 4

But I'm concerned about the line I flagged (// *** copy?)
const TfooMapInner& fooMapInner = (*ipOuter).second;

Is (*ipOuter).second a copy of the TfooMapInner? If so, how can I avoid
this unnecessary copy being made?

Simon Elliott http://www.ctsn.co.uk

c++ >> std::maps within std::maps -- optimisation

by Rolf Magnus » Wed, 09 Mar 2005 21:26:17 GMT

First insert the map, then fill it instead of the other way round:

TfooMapInner& myFooMapInner = myFooMapOuter["outer_key_2"];
myFooMapInner["inner_key_3"] = Tfoo(0,3);
myFooMapInner["inner_key_4"] = Tfoo(0,4);

Similar Threads

1. Problems with std::map.insert() and std::map.find()

2. Crash in std::map::~map with MS VC++ 7.1

I've encountered a rather bizarre problem with std::map::~map when
using MS Visual Studio .NET 2003 C++.

In the context I work with a map of the following form

typedef std::map<double, std::map<double, MyDataClass, MyLess>, MyLess>

MyLess implements operator< using a tolerance in the comparison.
MyDataClass is a simple struct have one public data member of type

When using MyMap in the same context as MyVector std::map::~map
crashes. I define MyVector as follows:

typedef std::vector<std::pair<double,double> > MyVector.

I tried replacing the STL code provided by MS with STLport without
getting rid of the error.

Moving to MS Visual Studio 2005 .NET Release Candidate however seems to
have solved the problem. This seems easy, but release candidate just
isn't a real release and also 2005 .NET requires XP sp2 which will not
be approved by my organised for some time. It would there be very nice
the understand the reason for the problem and then know what kind of
hack to resort to.


3. polymorphism for maps, was inheritance, overwrite functions,std::map

4. polymorphism for maps, was inheritance, overwrite functions,std::map

"Daniel Heiserer" < XXXX@XXXXX.COM > wrote in message
news: XXXX@XXXXX.COM ...
> >
> > Why not? It is the way to go in your case.
> >
> > >
> > [snip]
> > > As seen below this polymorphism I want does not work. I need
> > >
> > > std::map<int,A*> Bs;
> > > Where can I store my millions of B's right now? they are different.
> >
> >   Bs[5] = new B1;
> >   Bs[6] = new B56;
> This does not work:
> inheritance4.cc: In function `int main()':
> inheritance4.cc:37: no match for `A& = B1*&' operator
> inheritance4.cc:4: candidates are: A& A::operator=(const A&)
> inheritance4.cc:38: no match for `A& = B2*&' operator
> inheritance4.cc:4: candidates are: A& A::operator=(const A&)

It does work, its the way to do this. This is basic C++, if it doesn't work
for you then it is because you are doing something wrong. Post the code.


5. polymorphism for maps, was inheritance, overwrite functions,std::map

6. searching keys in std::map using map::upper_bound


let's say I have a std::map<std::string,int> and I want to search the map
for all keys that start with "foo". The regexp equivalent is to search for
"foo*", or perhaps "^foo*".

At present I do this quick'n'dirty by appending a tilde (~) to the query
term, since I know it's last in the ascii table and my keys don't include
any special characters. So to find everything that starts with "foo" I
search the map from map::lower_bound("foo") to map::upper_bound("foo~").
See below for complete program that demonstrates this.

There must be a much smarter, cleaner, more portable and less ugly way to
do this. Any ideas?



#include <iostream>
#include <map>

using namespace std;

int main(int argc, char* argv[])
  map<string, int> testmap;
  testmap.insert( make_pair("fon", 1) );
  testmap.insert( make_pair("foo", 2) );
  testmap.insert( make_pair("foobar", 3) );
  testmap.insert( make_pair("fool", 4) );
  testmap.insert( make_pair("fop", 5) );

  map<string, int>::iterator start_it = testmap.lower_bound("foo");
  map<string, int>::iterator stop_it = testmap.upper_bound("foo~");

  for( ; start_it != stop_it; ++start_it ) {
  return 0;

My Hotmail address is a spam magnet. If replying by email, use
erik dot arner at cgb dot ki dot se