Changing map keys (no reordering of keys)

[alan]

Hello world,

I currently have implemented a sparse array needed by a class as a
map<int, boost::shared_ptr<my_type> >.
However, one of the derived classes needs to periodically "tighten"
the sparse array (i.e. make it non-sparse). For example:

a[0] = 1
a[4] = 2
a[42] = 54

=>

a[0] = 1
a[1] = 2
a[2] = 54


I'm currently somewhat puzzled at how I would rearrange the keys. One
possible solution I thought would be:
/*where inv is the member containing the map*/
int lim = inv.size();
map<int, boost::shared_ptr<my_type> >::iterator it = inv.begin();
for( int i = 0; i < lim; ++i, ++it){
inv = it->second;
}
/*delete everything after the last*/
inv.erase(it, inv.end());

However, this does create some new objects each time I need to
tighten; granted that my current application uses only smart pointers,
it's not a big deal, but suppose that a future map with similar
requirements is needed, where the value is no longer a pointer but a
reasonably costly object? Is there a better way of implementing this?

 

[Victor Bazarov]

Hello world,

I currently have implemented a sparse array needed by a class as a
map<int, boost::shared_ptr<my_type> >.
However, one of the derived classes needs to periodically "tighten"
the sparse array (i.e. make it non-sparse). For example:

a[0] = 1
a[4] = 2
a[42] = 54

=>

a[0] = 1
a[1] = 2
a[2] = 54


I'm currently somewhat puzzled at how I would rearrange the keys. One
possible solution I thought would be:
/*where inv is the member containing the map*/
int lim = inv.size();
map<int, boost::shared_ptr<my_type> >::iterator it = inv.begin();
for( int i = 0; i < lim; ++i, ++it){
inv = it->second;
}
/*delete everything after the last*/
inv.erase(it, inv.end());

I would probably copy everything into a new map and then simply swap
the new one with the old one (and let the new one be disposed of).

[..]

V

 

[alan]

Hello world,

I currently have implemented a sparse array needed by a class as a
map<int, boost::shared_ptr<my_type> >.
However, one of the derived classes needs to periodically "tighten"
the sparse array (i.e. make it non-sparse). For example:

a[0] = 1
a[4] = 2
a[42] = 54

=>

a[0] = 1
a[1] = 2
a[2] = 54

I'm currently somewhat puzzled at how I would rearrange the keys. One
possible solution I thought would be:
/*where inv is the member containing the map*/
int lim = inv.size();
map<int, boost::shared_ptr<my_type> >::iterator it = inv.begin();
for( int i = 0; i < lim; ++i, ++it){
inv = it->second;
}
/*delete everything after the last*/
inv.erase(it, inv.end());

I would probably copy everything into a new map and then simply swap
the new one with the old one (and let the new one be disposed of).

Hmm. I thought of that too. However, suppose for the sake of
argument that the copying of the value objects are nontrivial (even if
arguably, when object copying is nontrivial, you probably really want
to use pointers of some kind). Is there some way to avoid the copy?

It's an admittedly academic question, of course, since a pointer of
some sort, or at least a wrapper object which copies the
implementation object only on mutation would be better.

[..]

V

 

[Victor Bazarov]

alan wrote:
[..]

I'm currently somewhat puzzled at how I would rearrange the keys.
One possible solution I thought would be:
/*where inv is the member containing the map*/
int lim = inv.size();
map<int, boost::shared_ptr<my_type> >::iterator it = inv.begin();
for( int i = 0; i < lim; ++i, ++it){
inv = it->second;
}
/*delete everything after the last*/
inv.erase(it, inv.end());

I would probably copy everything into a new map and then simply swap
the new one with the old one (and let the new one be disposed of).

Hmm. I thought of that too. However, suppose for the sake of
argument that the copying of the value objects are nontrivial (even if
arguably, when object copying is nontrivial, you probably really want
to use pointers of some kind). Is there some way to avoid the copy?

Store pointers to begin with. Or, you could actually introduce some
kind of a wrapper map (instead of destroying the initial one), which
would store pointers to the objects in the other map instead of copying
the values. When done, destroy both maps.

It's an admittedly academic question, of course, since a pointer of
some sort, or at least a wrapper object which copies the
implementation object only on mutation would be better.

V