C++ Logo

std-discussion

Advanced search

Should copying an unordered container keep the bucket structure?

From: Giuseppe D'Angelo <giuseppe.dangelo_at_[hidden]>
Date: Mon, 3 Jun 2019 11:00:40 +0200
Hello,

The requirements for an unordered associative container say that
copy-constructing or copy-assigning one will copy/assign (... the
various things in the common container requirements, e.g. contents,
allocator, etc. plus:) the hash function, the predicate and the maximum
load factor.

> http://eel.is/c++draft/unord.req

> Copy constructor.
> In addition to the requirements of Table 62, copies the hash function, predicate, and maximum load factor.


No guarantees are made regarding the actual structure of the copy --
whether the bucket count is preserved, or preserving the order of
elements in the original (whatever it may be). This seems to be by
design: in

> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1456.html

there's this note:

> Deliberately did not answer the question of whether they copy the bucket count; I have left that as an unresolved issue.


I don't know if that question had ever been reconsidered since (paper is
from 2003...). I'm guessing that this leaves room for implementations
where a given associative container object can, for instance, salt the
hash value and obtain a different arrangement in buckets.


However, would it make sense to further specify the copy semantics to
copy the bucket count and bucket structure (which elements in which
bucket, and the order of elements in a given bucket)? A quick test shows
that libstdc++ and MSVC actually seem to copy the exact structure, while
libc++ does not.

(A possible use case: I have an iterator into an unordered container; I
would like to take a copy of the container, and have a way to get an
iterator pointing to the copied element corresponding to the one pointed
by the first iterator.)

Apologies if there's already a proposal / defect report / etc., couldn't
find one.

Thank you for reading,
-- 
Giuseppe D'Angelo | giuseppe.dangelo_at_[hidden] | Senior Software Engineer
KDAB (France) S.A.S., a KDAB Group company
Tel. France +33 (0)4 90 84 08 53, http://www.kdab.com
KDAB - The Qt, C++ and OpenGL Experts

Received on 2019-06-03 04:02:31