https://gcc.gnu.org/bugzilla/show_bug.cgi?id=83709
Bug ID: 83709
Summary: Inserting duplicates into an unordered associative
containers causes the container to invalidate
iterators
Product: gcc
Version: 7.2.0
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: libstdc++
Assignee: unassigned at gcc dot gnu.org
Reporter: david.mrobinson at yahoo dot com
Target Milestone: ---
Created attachment 43049
--> https://gcc.gnu.org/bugzilla/attachment.cgi?id=43049&action=edit
Demonstrates unordered_set changing its order when no element is added
According to the C++11-C++17 draft standards unordered associative containers
(unordered_set, unordered_map, unordered_multiset, unordered_multimap) may only
invalidate iterators when a non-duplicate element is inserted into them.
N4659 (C++17 Draft) 26.2.7 [unord.req] states: "14 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, and preserve
the relative order of the elements that are not erased. 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."
In table 91 a_uniq.insert(t) states: "Effects: Inserts t if and only if
there is no element in the container with key equivalent to the key of t"
Based on the definition in table 91 of insert, in 26.2.7.15 inserted means that
an element must be added to the container for it to actually count as being
inserted, adding duplicates does not count. In 26.2.7.15 "n" is the number of
elements actually added to the container, not the number of elements insert is
called with.
Therefore, the current implementation of libstdc++ is in violation of the
standard as it invalidates iterators when adding only duplicates.
See the attachment for a short program that demonstrates that unordered_set
changes the order of its elements when inserting only duplicates. The output of
the program should be:
Starting Order: T, e,
Ending Order: e, T
Build command: g++ -v -save-temps main.cpp
Using built-in specs.
COLLECT_GCC=g++
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/7/lto-wrapper
OFFLOAD_TARGET_NAMES=nvptx-none
OFFLOAD_TARGET_DEFAULT=1
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Ubuntu 7.2.0-8ubuntu3'
--with-bugurl=file:///usr/share/doc/gcc-7/README.Bugs
--enable-languages=c,ada,c++,go,brig,d,fortran,objc,obj-c++ --prefix=/usr
--with-gcc-major-version-only --program-suffix=-7
--program-prefix=x86_64-linux-gnu- --enable-shared --enable-linker-build-id
--libexecdir=/usr/lib --without-included-gettext --enable-threads=posix
--libdir=/usr/lib --enable-nls --with-sysroot=/ --enable-clocale=gnu
--enable-libstdcxx-debug --enable-libstdcxx-time=yes
--with-default-libstdcxx-abi=new --enable-gnu-unique-object
--disable-vtable-verify --enable-libmpx --enable-plugin --enable-default-pie
--with-system-zlib --with-target-system-zlib --enable-objc-gc=auto
--enable-multiarch --disable-werror --with-arch-32=i686 --with-abi=m64
--with-multilib-list=m32,m64,mx32 --enable-multilib --with-tune=generic
--enable-offload-targets=nvptx-none --without-cuda-driver
--enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu
--target=x86_64-linux-gnu
Thread model: posix
gcc version 7.2.0 (Ubuntu 7.2.0-8ubuntu3)
COLLECT_GCC_OPTIONS='-v' '-save-temps' '-shared-libgcc' '-mtune=generic'
'-march=x86-64'
/usr/lib/gcc/x86_64-linux-gnu/7/cc1plus -E -quiet -v -imultiarch
x86_64-linux-gnu -D_GNU_SOURCE main.cpp -mtune=generic -march=x86-64
-fpch-preprocess -fstack-protector-strong -Wformat -Wformat-security -o main.ii
ignoring duplicate directory "/usr/include/x86_64-linux-gnu/c++/7"
ignoring nonexistent directory "/usr/local/include/x86_64-linux-gnu"
ignoring nonexistent directory
"/usr/lib/gcc/x86_64-linux-gnu/7/../../../../x86_64-linux-gnu/include"
#include "..." search starts here:
#include <...> search starts here:
/usr/include/c++/7
/usr/include/x86_64-linux-gnu/c++/7
/usr/include/c++/7/backward
/usr/lib/gcc/x86_64-linux-gnu/7/include
/usr/local/include
/usr/lib/gcc/x86_64-linux-gnu/7/include-fixed
/usr/include/x86_64-linux-gnu
/usr/include
End of search list.
COLLECT_GCC_OPTIONS='-v' '-save-temps' '-shared-libgcc' '-mtune=generic'
'-march=x86-64'
/usr/lib/gcc/x86_64-linux-gnu/7/cc1plus -fpreprocessed main.ii -quiet
-dumpbase main.cpp -mtune=generic -march=x86-64 -auxbase main -version
-fstack-protector-strong -Wformat -Wformat-security -o main.s
GNU C++14 (Ubuntu 7.2.0-8ubuntu3) version 7.2.0 (x86_64-linux-gnu)
compiled by GNU C version 7.2.0, GMP version 6.1.2, MPFR version 3.1.6,
MPC version 1.0.3, isl version isl-0.18-GMP
GGC heuristics: --param ggc-min-expand=100 --param ggc-min-heapsize=131072
GNU C++14 (Ubuntu 7.2.0-8ubuntu3) version 7.2.0 (x86_64-linux-gnu)
compiled by GNU C version 7.2.0, GMP version 6.1.2, MPFR version 3.1.6,
MPC version 1.0.3, isl version isl-0.18-GMP
GGC heuristics: --param ggc-min-expand=100 --param ggc-min-heapsize=131072
Compiler executable checksum: fa25397224c2d88843dc4f0893e88817
COLLECT_GCC_OPTIONS='-v' '-save-temps' '-shared-libgcc' '-mtune=generic'
'-march=x86-64'
as -v --64 -o main.o main.s
GNU assembler version 2.29.1 (x86_64-linux-gnu) using BFD version (GNU Binutils
for Ubuntu) 2.29.1
COMPILER_PATH=/usr/lib/gcc/x86_64-linux-gnu/7/:/usr/lib/gcc/x86_64-linux-gnu/7/:/usr/lib/gcc/x86_64-linux-gnu/:/usr/lib/gcc/x86_64-linux-gnu/7/:/usr/lib/gcc/x86_64-linux-gnu/
LIBRARY_PATH=/usr/lib/gcc/x86_64-linux-gnu/7/:/usr/lib/gcc/x86_64-linux-gnu/7/../../../x86_64-linux-gnu/:/usr/lib/gcc/x86_64-linux-gnu/7/../../../../lib/:/lib/x86_64-linux-gnu/:/lib/../lib/:/usr/lib/x86_64-linux-gnu/:/usr/lib/../lib/:/usr/lib/gcc/x86_64-linux-gnu/7/../../../:/lib/:/usr/lib/
COLLECT_GCC_OPTIONS='-v' '-save-temps' '-shared-libgcc' '-mtune=generic'
'-march=x86-64'
/usr/lib/gcc/x86_64-linux-gnu/7/collect2 -plugin
/usr/lib/gcc/x86_64-linux-gnu/7/liblto_plugin.so
-plugin-opt=/usr/lib/gcc/x86_64-linux-gnu/7/lto-wrapper
-plugin-opt=-fresolution=main.res -plugin-opt=-pass-through=-lgcc_s
-plugin-opt=-pass-through=-lgcc -plugin-opt=-pass-through=-lc
-plugin-opt=-pass-through=-lgcc_s -plugin-opt=-pass-through=-lgcc --sysroot=/
--build-id --eh-frame-hdr -m elf_x86_64 --hash-style=gnu --as-needed
-dynamic-linker /lib64/ld-linux-x86-64.so.2 -pie -z now -z relro
/usr/lib/gcc/x86_64-linux-gnu/7/../../../x86_64-linux-gnu/Scrt1.o
/usr/lib/gcc/x86_64-linux-gnu/7/../../../x86_64-linux-gnu/crti.o
/usr/lib/gcc/x86_64-linux-gnu/7/crtbeginS.o -L/usr/lib/gcc/x86_64-linux-gnu/7
-L/usr/lib/gcc/x86_64-linux-gnu/7/../../../x86_64-linux-gnu
-L/usr/lib/gcc/x86_64-linux-gnu/7/../../../../lib -L/lib/x86_64-linux-gnu
-L/lib/../lib -L/usr/lib/x86_64-linux-gnu -L/usr/lib/../lib
-L/usr/lib/gcc/x86_64-linux-gnu/7/../../.. main.o -lstdc++ -lm -lgcc_s -lgcc
-lc -lgcc_s -lgcc /usr/lib/gcc/x86_64-linux-gnu/7/crtendS.o
/usr/lib/gcc/x86_64-linux-gnu/7/../../../x86_64-linux-gnu/crtn.o
COLLECT_GCC_OPTIONS='-v' '-save-temps' '-shared-libgcc' '-mtune=generic'
'-march=x86-64'
