On 08/01/20 18:47 -0500, David Malcolm wrote:
On Wed, 2019-12-04 at 10:59 -0700, Martin Sebor wrote:
On 11/15/19 6:23 PM, David Malcolm wrote:
> This patch adds an ordered_hash_map template, which is similar to
> hash_map, but preserves insertion order.
>
> gcc/ChangeLog:
> * Makefile.in (OBJS): Add ordered-hash-map-tests.o.
> * ordered-hash-map-tests.cc: New file.
> * ordered-hash-map.h: New file.
> * selftest-run-tests.c (selftest::run_tests): Call
> selftest::ordered_hash_map_tests_cc_tests.
> * selftest.h (selftest::ordered_hash_map_tests_cc_tests): New
> decl.
> ---
> gcc/Makefile.in | 1 +
> gcc/ordered-hash-map-tests.cc | 247
> ++++++++++++++++++++++++++++++++++++++++++
> gcc/ordered-hash-map.h | 184
> +++++++++++++++++++++++++++++++
> gcc/selftest-run-tests.c | 1 +
> gcc/selftest.h | 1 +
> 5 files changed, 434 insertions(+)
> create mode 100644 gcc/ordered-hash-map-tests.cc
> create mode 100644 gcc/ordered-hash-map.h
>
[...]
The container defines a copy-constructor but no copy assignment.
Is it safely assignable? (I don't think auto_vec is safely copyable
or assignable due to PR 90904. It looks like the copy ctor works
around it below.)
It's not safely assignable; I don't believe I'm using that (I am using
the copy ctor).
I can make it private or similar to ensure it's not used.
Yes, if the compiler-generated assignment isn't safe, please declare
(but don't define) a private assignment operator, to suppress the
compiler-generated one.
I don't think I've made use of the hash_map copy ctor or copy
assignment but if it's anything like other GCC containers I'd
worry about it not doing the right thing, especially for non-
PODs. I spent too much time chasing down miscompilations and
other problems due to bugs (or design limitations) in these
classes.
I'd far prefer to see us use libstdc++ containers in new code
than introduce new ones of our own. They are better designed
and much better tested than these. (I realize we're still
hampered by targeting C++ 98.)
Martin
[CCing Jonathan for libstdc++ expertise]
Is there such a container in libstdc++?
This patch implements a map that preserves insertion order when
iterating, without requiring the Key type to be comparable.
As far as I can tell, std::map instead is a map that requires the Key
type to be comparable,
Right.
and uses that to implement a red-black tree
(rather than via hashing),
Right.
and doesn't preserve insertion ordering.
std::map has unique keys anyway, so insertion order is irrelevant.
Iteration is done by key order.
std::multimap is the non-unique version, and preserves insertion order
for equivalent keys, but only since C++11. Before that it was
unspecified whether or not a duplicate key was inserted after existing
elements with equivalent keys.
I use this ordered_hash_map class later in various places in the
analyzer patch kit to ensure more deterministic results, so that
results aren't affected by hash values of possibly-changing pointer
values.
Nothing in the standard library provides that functionality out of the
box. The C++11 hash containers don't preserve order at all, even
equivalent elements can be reordered when insertion triggers
rehashing.
You could build something using a sequence container (vector, deque or
list) that preserves a stable order according to insertion order, and
then manually maintain a separate index of hash values used for
lookup. That might not make things any simpler (I haven't looked at
your actual patch).
