Does a std::set ever rebalance ?

[mathieu]

hi there,

I would like to know if the following piece of code is garantee to
work. I am afraid that the cstring address I am using in the std::map
found from a request in std::set is not garantee to remain the same as
the std::set grows...

thanks
-Mathieu

#include <set>
#include <map>
#include <iostream>

struct FileValuePair {
const char *filename;
const char *value;
};

static FileValuePair MAPPINGS[] = {
{ "foo1.dat" , "value1" },
{ "foo2.dat" , "value2" },
{ "foo3.dat" , "value1" },
{ "foo4.dat" , "value3" },
{ "foo5.dat" , "value2" },
{ "foo6.dat" , "value3" },
{ NULL , NULL },
};

int main()
{
FileValuePair *p = MAPPINGS;
std::set< std::string > values;
std::map< const char *, const char * > mappings;
while(p->filename)
{
values.insert( p->value );
// find back the address:
const char *v = values.find( p->value )->c_str();
mappings.insert(
std::map<const char*,const char*>::value_type(p->filename, v));
++p;
}

std::map<const char*,const char*>::const_iterator it =
mappings.begin();
for(; it != mappings.end(); ++it)
{
std::cout << it->first << " -> " << it->second << std::endl;
}

return 0;
}

 

[Victor Bazarov]

I would like to know if the following piece of code is garantee to
work. I am afraid that the cstring address I am using in the std::map
found from a request in std::set is not garantee to remain the same as
the std::set grows...

Insertions in 'std::set' or 'std::map' do not invalidate iterators
or references. The call to 'find' returns an iterator. You call the
'c_str()' for the object referred to by the iterator. The object is
not going to change unless you remove the entry itself from the set.
So, the pointer returned by 'c_str()' should still be valid up until
the set is destroyed.

At least that's my take on it...

thanks
-Mathieu

#include <set>
#include <map>
#include <iostream>

struct FileValuePair {
const char *filename;
const char *value;
};

static FileValuePair MAPPINGS[] = {
{ "foo1.dat" , "value1" },
{ "foo2.dat" , "value2" },
{ "foo3.dat" , "value1" },
{ "foo4.dat" , "value3" },
{ "foo5.dat" , "value2" },
{ "foo6.dat" , "value3" },
{ NULL , NULL },
};

int main()
{
FileValuePair *p = MAPPINGS;
std::set< std::string > values;
std::map< const char *, const char * > mappings;
while(p->filename)
{
values.insert( p->value );
// find back the address:
const char *v = values.find( p->value )->c_str();
mappings.insert(
std::map<const char*,const char*>::value_type(p->filename, v));
++p;
}

std::map<const char*,const char*>::const_iterator it =
mappings.begin();
for(; it != mappings.end(); ++it)
{
std::cout << it->first << " -> " << it->second << std::endl;
}

return 0;
}

 

[Jerry Coffin]

(e-mail address removed)>, (e-mail address removed)
says...

hi there,

I would like to know if the following piece of code is garantee to
work. I am afraid that the cstring address I am using in the std::map
found from a request in std::set is not garantee to remain the same as
the std::set grows...

It does rebalance, but rebalancing only involves changing the
arrangement of the nodes in the tree. Each node contains pointers to one
or two children. Rebalancing involves changing the pointers between
nodes, but does not actually move the nodes themselves. Addresses and/or
iterators that refer to objects you store in the set/map are never
invalidated by inserting into the set/map.

 

[Martin York]

It does rebalance, but rebalancing only involves changing the
arrangement of the nodes in the tree. Each node contains pointers to one
or two children. Rebalancing involves changing the pointers between
nodes, but does not actually move the nodes themselves. Addresses and/or
iterators that refer to objects you store in the set/map are never
invalidated by inserting into the set/map.

You are talking about implementation details.
The standard does not specify how the set class should be implemented.

The standard defines a set (and all containers) in terms of
guarantees. How the implementor decides implement this is up to the
implementor (and I have seen multiple implementations of the set class
over the years).

But to the original question the standard guarantees for std::set
<quote>Set has the important property that inserting a new element
into a set does not invalidate iterators that point to existing
elements. Erasing an element from a set also does not invalidate any
iterators, except, of course, for iterators that actually point to the
element that is being erased.</quote>