Accessing classes from standard containers

[Juicer_X]

Hello,

I have some code that I'm working on, the problem isn't that it doesn't
work it's that it's too slow. I have a class that holds my homemade class
within an std::map, within an std::map. here is the declaration.

std::map<char, std::map<char, CWordFrequency> > baseMap;

Now I can assign a pointer to the inner map, but I cannot assign a
pointer to my class without actually copying the second map into memory. I'm
not sure but I think the operators I need to use are ".*" or "->*".

Can somebody point me in the right direction?

Here is the slow but working code fragment.

sequenceFrequencyMap = baseMap[base];
tempFrequency = sequenceFrequencyMap[sequence];

if (wordPosition > 0 && (wordPosition + 1) < (word.length() -
1)) {tempFrequency.incrementCountWithin();}
else if (wordPosition == 0)
{tempFrequency.incrementCountBeginning();}
else if ((wordPosition + 1) == word.length() - 1)
{tempFrequency.incrementCountEnd();}

sequenceFrequencyMap[sequence] = tempFrequency;
baseMap[base] = sequenceFrequencyMap;

 

[alexmdac]

References are your friends here:

CWordFrequency &wf = baseMap[base][sequence];
if( ... )
{ wf.incrementCountWithin(); }
// etc.

 

[loritsch]

Hello,

I have some code that I'm working on, the problem isn't that it doesn't
work it's that it's too slow.

First off, this small code fragment is a bit difficult to decipher
because it doesn't clearly define the types of all of the instance
variables. In the future, it might be helpful for you to show the
declarations of the variables being used, so that your question is a
bit more clear.

From the context of your posting, I can only assume that there are

declarations similar to the ones below someplace in the code prior to
the block you shared:

std::map<char, CWordFrequency> sequenceFrequencyMap;
CWordFrequency tempfrequency;
char base;
char sequence;

My answer will rely on these assumptions...

Now there are quite a few things one could do to speed up the code.
First off, the statements:

sequenceFrequencyMap = baseMap[base];
tempFrequency = sequenceFrequencyMap[sequence];

create temporary instances of std::map<char, CWordFrequency> and
CWordFrequency, respectively, that you then perform operations on.
These are extremely costly and seemingly unecessary operations in this
case.

It would be wiser to simply obtain a reference to the CWordFrequency
object (via map:perator[]), and then call your incrementXXXX()
methods using this reference. Do do this, simply get rid of the lines
above, and replace each place you use 'tempFrequency' with
'baseMap[base][sequence]'

Since you will now be working with your embedded object directly, you
will have no need to re-insert a copy of it into your map, therefore
the code below will also be unnecessary.

sequenceFrequencyMap[sequence] = tempFrequency;
baseMap[base] = sequenceFrequencyMap;

Again, the code above was creating unnecessary copies of large objects,
and thus slowly you down. After making these changes, your code should
be significantly faster, and look something like the following snippet:

std::map<char, std::map<char, CWordFrequency> > baseMap;
if (wordPosition > 0 &&
(wordPosition + 1) < (2 - 1)) {
baseMap[base][sequence].incrementCountWithin();
}
else if (wordPosition == 0) {
baseMap[base][sequence].incrementCountBeginning();
}
else if ((wordPosition + 1) == 2 - 1) {
baseMap[base][sequence].incrementCountEnd();
}

There is one more thing that should be noted...

Since the standard containers are allowed to arbitrarily make copies of
their entries, it is likely that using either raw or managed pointers
to your CWordFrequency objects within your maps would also increase
speed. That being said, it is a less obvious optimization, not knowing
what a CWordFrequency object is. In any case, I normally recommend it
for most anything but the most primitive types.
I hope this helps!

Michael Loritsch

 

[msalters]

Hello,

I have some code that I'm working on, the problem isn't that it doesn't
work it's that it's too slow. I have a class that holds my homemade class
within an std::map, within an std::map. here is the declaration.

std::map<char, std::map<char, CWordFrequency> > baseMap;

Now I can assign a pointer to the inner map, but I cannot assign a
pointer to my class without actually copying the second map into memory. I'm
not sure but I think the operators I need to use are ".*" or "->*".

No. First, the address-of operator is &, and secondly, the only thing
you need to do is name the object.

Here is the slow but working code fragment.

sequenceFrequencyMap = baseMap[base];
tempFrequency = sequenceFrequencyMap[sequence];

That's not a pointer! You're copying the entire inner map out, and
then you copy your class out of that copy!

if (wordPosition > 0 && (wordPosition + 1) < (word.length() -
1)) {tempFrequency.incrementCountWithin();}
else if (wordPosition == 0)
{tempFrequency.incrementCountBeginning();}
else if ((wordPosition + 1) == word.length() - 1)
{tempFrequency.incrementCountEnd();}

sequenceFrequencyMap[sequence] = tempFrequency;
baseMap[base] = sequenceFrequencyMap;

Simple optimalization:
((wordPosition + 1) == word.length() - 1) ==
(wordPosition + 2 == word.length() )
Compiler probably can't do that, because it is unlikely to see
that no overflow can happen.

The /real/ solution is to use references (not pointers):

std::map<char, CWordFrequency>& sequenceFrequencyMap = baseMap[base];
CWordFrequency& tempFrequency = sequenceFrequencyMap[sequence];

This means you won't copy the objects, but modify them in place.
As a result, the copy-back step can also be skipped, i.e. no more

sequenceFrequencyMap[sequence] = tempFrequency;
baseMap[base] = sequenceFrequencyMap;

Regards,
Michiel Salters

 

[velthuijsen]

Why don't you use find() (the one included with map) & iterators?
Here is an example of how to access the value of the nested map.
I'm using the fact that an iterator behaves as if it is a pointer. In
your case you might want to store the iterator

#include <map>
#include <iostream>

int main()
{
// create & fill example double map
std::map<char, std::map<char, int> > Test;
std::map<char, int> Test2;
Test2['b'] = 4;
Test2['c'] = 1;
Test['b'] = Test2;
Test2.clear();
Test2['b'] = 2;
Test['o'] = Test2;
// acess innermap value
std::cout << ((Test.find('o'))->second.find('b'))->second;
std::cout << ((Test.find('b'))->second.find('b'))->second;
std::cout << ((Test.find('b'))->second.find('c'))->second;
// output should be 241
getchar();
return 0;
}

 

[Michael Loritsch]

Hello,

I have some code that I'm working on, the problem isn't that it doesn't
work it's that it's too slow.

First off, this small code fragment is a bit difficult to decipher
because it doesn't clearly define the types of all of the instance
variables. In the future, it might be helpful for you to show the
declarations of the variables being used, so that your question is a
bit more clear.

From the context of your posting, I can only assume that there are

declarations similar to the ones below someplace in the code prior to
the block you shared:

std::map<char, CWordFrequency> sequenceFrequencyMap;
CWordFrequency tempfrequency;
char base;
char sequence;

My answer will rely on these assumptions...

Now there are quite a few things one could do to speed up the code.
First off, the statements:

sequenceFrequencyMap = baseMap[base];
tempFrequency = sequenceFrequencyMap[sequence];

create temporary instances of std::map<char, CWordFrequency> and
CWordFrequency, respectively, that you then perform operations on.
These are extremely costly and seemingly unecessary operations in this
case.

It would be wiser to simply obtain a reference to the CWordFrequency
object (via map:perator[]), and then call your incrementXXXX()
methods using this reference. Do do this, simply get rid of the lines
above, and replace each place you use 'tempFrequency' with
'baseMap[base][sequence]'

Since you will now be working with your embedded object directly, you
will have no need to re-insert a copy of it into your map, therefore
the code below will also be unnecessary.

sequenceFrequencyMap[sequence] = tempFrequency;
baseMap[base] = sequenceFrequencyMap;

Again, the code above was creating unnecessary copies of large objects,
and thus slowly you down. After making these changes, your code should
be significantly faster, and look something like the following snippet:

std::map<char, std::map<char, CWordFrequency> > baseMap;
if (wordPosition > 0 &&
(wordPosition + 1) < (2 - 1)) {
baseMap[base][sequence].incrementCountWithin();
}
else if (wordPosition == 0) {
baseMap[base][sequence].incrementCountBeginning();
}
else if ((wordPosition + 1) == 2 - 1) {
baseMap[base][sequence].incrementCountEnd();
}

There is one more thing that should be noted...

Since the standard containers are allowed to arbitrarily make copies of
their contents, I would also recommend using either raw or managed
pointers to your CWordFrequency objects would likely also increase
speed. That being said, it is a less obvious optimization, not knowing
what a CWordFrequency object is. In any case, I recommend it for most
anything but the most primitive types.
I hope this helps!

Michael Loritsch

 

[Juicer_X]

Hello,

I have some code that I'm working on, the problem isn't that it doesn't
work it's that it's too slow. I have a class that holds my homemade class
within an std::map, within an std::map. here is the declaration.

std::map<char, std::map<char, CWordFrequency> > baseMap;

Now I can assign a pointer to the inner map, but I cannot assign a
pointer to my class without actually copying the second map into memory. I'm
not sure but I think the operators I need to use are ".*" or "->*".

No. First, the address-of operator is &, and secondly, the only thing
you need to do is name the object.

Here is the slow but working code fragment.

sequenceFrequencyMap = baseMap[base];
tempFrequency = sequenceFrequencyMap[sequence];

That's not a pointer! You're copying the entire inner map out, and
then you copy your class out of that copy!

Sorry, I recently revised this code and took the pointer refrences out
for simplification. But there was a pointer to the inner map.

if (wordPosition > 0 && (wordPosition + 1) < (word.length() -
1)) {tempFrequency.incrementCountWithin();}
else if (wordPosition == 0)
{tempFrequency.incrementCountBeginning();}
else if ((wordPosition + 1) == word.length() - 1)
{tempFrequency.incrementCountEnd();}

sequenceFrequencyMap[sequence] = tempFrequency;
baseMap[base] = sequenceFrequencyMap;

Simple optimalization:
((wordPosition + 1) == word.length() - 1) ==
(wordPosition + 2 == word.length() )
Compiler probably can't do that, because it is unlikely to see
that no overflow can happen.

I don't seem to understand how this speeds anything up? Could you please
explain?

The /real/ solution is to use references (not pointers):

std::map<char, CWordFrequency>& sequenceFrequencyMap = baseMap[base];
CWordFrequency& tempFrequency = sequenceFrequencyMap[sequence];

So which way is better This way is more verbose which I like and it
seems that it's doing pretty much the same as : CWordFrequency &wf =
baseMap[base][sequence];

This means you won't copy the objects, but modify them in place.
As a result, the copy-back step can also be skipped, i.e. no more

sequenceFrequencyMap[sequence] = tempFrequency;
baseMap[base] = sequenceFrequencyMap;

Regards,
Michiel Salters

Thank you for the info.

 

[Juicer_X]

First off, this small code fragment is a bit difficult to decipher
because it doesn't clearly define the types of all of the instance
variables. In the future, it might be helpful for you to show the
declarations of the variables being used, so that your question is a
bit more clear.

Sorry, I forgot all about the declarations.

declarations similar to the ones below someplace in the code prior to
the block you shared:

std::map<char, CWordFrequency> sequenceFrequencyMap;
CWordFrequency tempfrequency;
char base;
char sequence;

My answer will rely on these assumptions...

Your assumptions are correct.

Now there are quite a few things one could do to speed up the code.
First off, the statements:

sequenceFrequencyMap = baseMap[base];
tempFrequency = sequenceFrequencyMap[sequence];

create temporary instances of std::map<char, CWordFrequency> and
CWordFrequency, respectively, that you then perform operations on.
These are extremely costly and seemingly unecessary operations in this
case.

See the problem is I knew that it's just that I really didn't know any
other way of getting it done.

It would be wiser to simply obtain a reference to the CWordFrequency
object (via map:perator[]), and then call your incrementXXXX()

Ihad no idea that you could use operator[] like a 2 dimensional array.
It makes sense now but I really thought that I couldn't do that.

methods using this reference. Do do this, simply get rid of the lines
above, and replace each place you use 'tempFrequency' with
'baseMap[base][sequence]'

Since you will now be working with your embedded object directly, you
will have no need to re-insert a copy of it into your map, therefore
the code below will also be unnecessary.

sequenceFrequencyMap[sequence] = tempFrequency;
baseMap[base] = sequenceFrequencyMap;

This was really annoying to put in, but I was glad when I was able to
get rid of it.

Again, the code above was creating unnecessary copies of large objects,
and thus slowly you down. After making these changes, your code should
be significantly faster, and look something like the following snippet:

std::map<char, std::map<char, CWordFrequency> > baseMap;
if (wordPosition > 0 &&
(wordPosition + 1) < (2 - 1)) {
baseMap[base][sequence].incrementCountWithin();
}
else if (wordPosition == 0) {
baseMap[base][sequence].incrementCountBeginning();
}
else if ((wordPosition + 1) == 2 - 1) {
baseMap[base][sequence].incrementCountEnd();
}

There is one more thing that should be noted...

Since the standard containers are allowed to arbitrarily make copies of
their entries, it is likely that using either raw or managed pointers
to your CWordFrequency objects within your maps would also increase
speed. That being said, it is a less obvious optimization, not knowing
what a CWordFrequency object is. In any case, I normally recommend it
for most anything but the most primitive types.
I hope this helps!

Michael Loritsch

Thank you, for all your help.

 

[Juicer_X]

Why don't you use find() (the one included with map) & iterators?

The thing is that I tried find(), but what happens is that it doesn't
matter whether or not my key pairs have actually been in the map before
because they will be added when I come across them.

Here is an example of how to access the value of the nested map.
I'm using the fact that an iterator behaves as if it is a pointer. In
your case you might want to store the iterator

#include <map>
#include <iostream>

int main()
{
// create & fill example double map
std::map<char, std::map<char, int> > Test;
std::map<char, int> Test2;
Test2['b'] = 4;
Test2['c'] = 1;
Test['b'] = Test2;
Test2.clear();
Test2['b'] = 2;
Test['o'] = Test2;
// acess innermap value
std::cout << ((Test.find('o'))->second.find('b'))->second;
std::cout << ((Test.find('b'))->second.find('b'))->second;
std::cout << ((Test.find('b'))->second.find('c'))->second;
// output should be 241
getchar();
return 0;
}

Your implementation has given me an idea. I need to use find() for when
I make new words out of my character pairs. My code is hard to read so I
think I might borrow your solution.

 

[velthuijsen]

The thing is that I tried find(), but what happens is that it doesn't
matter whether or not my key pairs have actually been in the map before
because they will be added when I come across them.

I'm not sure what you mean by this. If you mean that you want to add
values that not yet exist Alexm has shown a solution that will do that.

If you mean that find() actually adds values that is not true, if the
value you are trying to find does not exist in the map you get the same
iterator as the one you get when you do end(). That is why I said that
you'd probably have to work with iterators to when using find()

 

[Juicer_X]

I'm not sure what you mean by this. If you mean that you want to add
values that not yet exist Alexm has shown a solution that will do that.

If you mean that find() actually adds values that is not true, if the
value you are trying to find does not exist in the map you get the same
iterator as the one you get when you do end(). That is why I said that
you'd probably have to work with iterators to when using find()

Sorry, I wrote that in a hurry. I did adopt alexm's code for loading the
map. Because I'm reading information from a file and assume that everything
is valid. I error check before my class member is called.

I tried to validate with find() in a previous attempt but found it more
efficient without it. (Thats why I do it with another class now).

Thanks for replying,

Brent Ritchie

 

[Jeff Flinn]

Why don't you use find() (the one included with map) & iterators?
Here is an example of how to access the value of the nested map.
I'm using the fact that an iterator behaves as if it is a pointer. In
your case you might want to store the iterator

#include <map>
#include <iostream>

int main()
{
// create & fill example double map
std::map<char, std::map<char, int> > Test;
std::map<char, int> Test2;
Test2['b'] = 4;
Test2['c'] = 1;
Test['b'] = Test2;
Test2.clear();
Test2['b'] = 2;
Test['o'] = Test2;
// acess innermap value
std::cout << ((Test.find('o'))->second.find('b'))->second;
std::cout << ((Test.find('b'))->second.find('b'))->second;
std::cout << ((Test.find('b'))->second.find('c'))->second;
// output should be 241
getchar();
return 0;
}

It appears the OP is only operating on individual items, rather than on an
entire inner map. An alternative that may be more efficient would be to
avoid the 'nested' maps and use a slightly more complex key in a single map.
Something like this:

int main()
{
typedef std:air< char, char > tKey
typedef std::map < tKey, int > tMap;

tMap lMap;

lMap[tKey('o','b') ] = 1;
lMap[tKey('b','b') ] = 3;
lMap[tKey('b','c') ] = 5;

std::cout << lMap.find(tKey('o','b'))->second
<< lMap.find(tKey('b','b'))->second
<< lMap.find(tKey('b','c'))->second;

return 0;
}