flat_hash_map::end() and node_hash_map::end() value changes as the map grows

[koer...@gmail.com]

I noticed a discrepancy between std::unordered_map and the abseil *_hash_maps.

The return value from the end() method changes.  But for std::unordered_map, the value does not change.

I am working on ubuntu with g++ -std=c++17

Is this intentional? 

I understand that iterators can be invalidated.  However, shouldn't the value of end() be the same as the maps change, as with std::unordered_map?

Below is a snippet of a coding example.

template< typename KeyT, typename ValueT>

using UnorderedMap = absl::flat_hash_map<KeyT, ValueT>;

//// cut....

UnorderedMap<int, int> myMap;  // replace with myMap(4000) to see end() change at a later instance.

UnorderedMap<int, int>::iterator theEnd = myMap.end();

for( int index=0; index < 100000; ++index)

{

    myMap.emplace(index, index+1);

    if( theEnd != myMap.end() )

        std::cout << "the end has changed at " << index << std::endl;

}

[Samuel Benzaquen]

On Tue, Jul 7, 2020 at 4:10 PM <koer...@gmail.com> wrote:

I noticed a discrepancy between std::unordered_map and the abseil *_hash_maps.

The return value from the end() method changes.  But for std::unordered_map, the value does not change.

I am working on ubuntu with g++ -std=c++17

Is this intentional? 

I understand that iterators can be invalidated.  However, shouldn't the value of end() be the same as the maps change, as with std::unordered_map?

end() is an iterator like any other.

Unless otherwise specified it will be invalidated in cases where iterators are invalidated. Abseil's hash tables are not special here.

In particular, Abseil's hash table invalidates all iterators on rehash, just like std::vector invalidates all iterators (including end()) on realloc.

std::unordered_map has more guarantees regarding iterator invalidation. An iterator is only invalidated when the element itself is erased. It is similar to std::map in this regard.

However, this comes with a price tag since it requires more CPU and memory in order to provide these guarantees.

 

Below is a snippet of a coding example.

template< typename KeyT, typename ValueT>

using UnorderedMap = absl::flat_hash_map<KeyT, ValueT>;

//// cut....

UnorderedMap<int, int> myMap;  // replace with myMap(4000) to see end() change at a later instance.

UnorderedMap<int, int>::iterator theEnd = myMap.end();

for( int index=0; index < 100000; ++index)

{

    myMap.emplace(index, index+1);

    if( theEnd != myMap.end() )

        std::cout << "the end has changed at " << index << std::endl;

}

--
You received this message because you are subscribed to the Google Groups "Abseil.io" group.
To unsubscribe from this group and stop receiving emails from it, send an email to abseil-io+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/abseil-io/ea1d50a1-81ae-46bc-9aea-44696248256co%40googlegroups.com.

[Marshall Clow]

On Jul 7, 2020, at 1:10 PM, koer...@gmail.com wrote:
>
> I noticed a discrepancy between std::unordered_map and the abseil *_hash_maps.
> The return value from the end() method changes. But for std::unordered_map, the value does not change.
> I am working on ubuntu with g++ -std=c++17
>
> Is this intentional?
> I understand that iterators can be invalidated. However, shouldn't the value of end() be the same as the maps change, as with std::unordered_map?

I think you’re depending on behavior of std::unordered_map that is not guaranteed by the standard.

See http://eel.is/c++draft/unord.req#14, which says:

The insert and emplace members shall not affect the validity of references to container elements, but may invalidate all iterators to the container.

The iterator returned by `end()` is still an iterator to the container.

— Marshall