about unordered_set

[morando]

I need to know when i insert element into this container does previous items preserve their addresses or after some time this container reallocates/copies everything into another memory locations?
How does it store elements?

[viliml]

http://publib.boulder.ibm.com/infocenter/comphelp/v9v111/index.jsp?topic=/com.ibm.xlcpp9.aix.doc/standlib/stl_unordered_set.htm

[morando]

Moreover, inserting an element invalidates no iterators, and removing an element invalidates only those iterators which point at the removed element.

Thanks.

[JLBorges]

> Moreover, inserting an element invalidates no iterators, and removing an element
> invalidates only those iterators which point at the removed element.

The IS makes no such guarantee. Pointers or references to elements are not invalidated, but all iterators may be invalidated.

The elements of an unordered associative container are organized into buckets. Keys with the same hash code appear in the same bucket. The number of buckets is automatically increased as elements are added to an unordered associative container, so that the average number of elements per bucket is kept below a bound.

Rehashing invalidates iterators, changes ordering between elements, and changes which buckets elements appear in, but does not invalidate pointers or references to elements.
...
The insert and emplace members shall not affect the validity of references to container elements, but may invalidate all iterators to the container. The erase members shall invalidate only iterators and references to the erased elements.
...
The insert and emplace members shall not affect the validity of iterators if (N+n) < z * B, where N is the number of elements in the container prior to the insert operation, n is the number of elements inserted, B is the container’s bucket count, and z is the container’s maximum load factor.

[morando]

EDIT:
My mistake.

Just seen that my code loads resource even if it is in the set:

// class move enabled
class resource;
...
std::unordered_set<resource>  us_resources;
...
template<typename TStr>
const resource* load_res(TStr&& s)
{
	resource r(std::forward<TStr>(s));// loads resource
	auto result = us_resources.insert(std::move(r));
	return &(*result.first);
}

then this is useless.
Maybie better of with std::list and walk thru it when i need to insert element to see if it has it and return that?

[JLBorges]

> Then i use pointer returned elswhere. Is this safe?

Yes, it is safe. Pointers and references will not change and can be safely used. (As long as the element is not erased, and provided the code that uses the pointer is const-correct.)

> Just seen that my code loads resource even if it is in the set:

You need to first check if the resource is already in the set. find() on the set would be a lot faster than walking through a list.

[morando]

I don't understand what is a Key that i need to pass to find()?

[JLBorges]

The way you have defined the set, the key is a resource.

Perhaps it would help if you gave us an idea of what you are aiming to do.

[morando]

Ok.

resource is a class that hold some kind of resource (image, sound...)

resource r(std::forward<TStr>(s));

In resource constructor i pass a string witch holds file name of that resource witch is loaded by some 3d party library function and destroy that in destructor.

Long story short, basic idea is:

class resource
{
private:
        IMAGE*   ptr; 
        str name;
    ...private copy con
    ...private = operator
public:
    resource(str s) : name(s)
    {
           ptr = LoadImageFromFile(name);
    }
    ... move constructor
    ... move = operator
    ~resource()
    {
          FreeImage(ptr);
     }
};
class res_manager
{
private:
    std::unordered_set<resource> us_resources;
public:
     ....
     template<typename TStr> 
     const resource* load_res(TStr&& s)
    {
             if not found in us_resources insert new 
                      return last inserted
               if found
                       return that from us_resources.
     }
};

....
class some_class
{
   const resource* r;
...
};

res_manager rm;
som_class s[100]; //some items might need same image
s[0].r = rm.load_res("image.bmp");

[mik2718]

A map offers order logN keyed access to elements and also does not invalidate iterators after an erase (except for the one pointing to the erased element)
(internal structure of a map is a tree)

An unordered set (i.e. hash) is likely to invalidate iterators due to the bucket structure described

A list allows erasing elements without invalidating other iterators but access to an arbitrary element will be order N (instead of logN for the map)

My feeling is you are unlikely to notice the difference for this usage anyway

[morando]

Then the list is a better choice?
I don't need sorting, insertion and deletion is not time critical as far as addresses of elements are not mangled somehow.

[JLBorges]

Use an unordered_map<>, instead? With a string (file name) as the key and resource as the data. Something like this:

std::unordered_map< std::string, resource > resource_cache ;

const resource* load_res( const std::string& file_name )
{
    auto iter =  resource_cache.find( file_name ) ;
    if( iter != resource_cache.end() ) return &iter->second ; // found in cache

    resource_cache[file_name] = resource(file_name) ; // not found, add to cache

    return load_res(file_name) ; // call recursively, will find it next time
}

EDIT: Invalidation of iterators is a non-issue here - no iterators are being passed anywhere. And the pointer that is returned is guaranteed to be valid.

[morando]

Thanks. I will try that.