Is any stl-container standartized to be a determenistic?

[Garbor]

I was trying to find a reference that any stl-container is determentistic. I mean, iterating over them returns the result in the same order each time we're doing that. Does the standard specify that fact?

[Thiago Macieira]

Yes. All ordered containers are specified to retain the order that the user
specified.

--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center
PGP/GPG: 0x6EF45358; fingerprint:
E067 918B B660 DBD1 105C 966C 33F5 F005 6EF4 5358

[Róbert Dávid]

I think the question was also about non-ordered containers.

Sequence containers have to iterate through the sequence in order, obviously, but I actually see nothing to forbid unordered ones to iterate differently for a second time.

I also see no reason for an implementation to do that though. Maybe with some garbage collection backed unordered_map

Best,
Robert

[Thiago Macieira]

I'd expect that if you iterate twice in sequence, without inserting or
removing elements, any reasonable implementation will iterate again in the
same order. Whichever container that is, ordered, sequential or otherwise.

I had understood the question about whether iterating the same container type
yields the same order if you recreate the container from its component
elements. That is not guaranteed for unordered containers, even if you keep
the same insertion order. But it is guaranteed for ordered and sequential
containers, of course.

[David Krauss]

> On 2015–06–16, at 12:28 AM, Róbert Dávid <lrd...@gmail.com> wrote:
>
> I think the question was also about non-ordered containers.
>
> Sequence containers have to iterate through the sequence in order, obviously, but I actually see nothing to forbid unordered ones to iterate differently for a second time.

It’s all the way at the end, [unord.req] §23.2.5/15:

> 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.


Since unordered container iterators are ForwardIterators and thus have the multi-pass guarantee ([forward.iterators] §24.2.5/3), the order has to remain fixed until the load factor constraint allows a re-hash.

> I also see no reason for an implementation to do that though. Maybe with some garbage collection backed unordered_map

I’m interested to collect examples of containers implementing allocator-based garbage collection. Do you have an existing library in mind?