]> gcc.gnu.org Git - gcc.git/commit
libstdc++: Replace try-catch in std::list::merge to avoid O(N) size
authorJonathan Wakely <jwakely@redhat.com>
Wed, 29 Sep 2021 19:46:55 +0000 (20:46 +0100)
committerJonathan Wakely <jwakely@redhat.com>
Fri, 1 Oct 2021 14:04:02 +0000 (15:04 +0100)
commitb8d42cfa84fb31e592411e6cea41bdde980c51d7
tree369e4156b46983da2de4e9120f7d7715a94b467a
parent5051fad8582fcbdd0844232b5a8c4e856be5e5a4
libstdc++: Replace try-catch in std::list::merge to avoid O(N) size

The current std::list::merge code calls size() before starting to merge
any elements, so that the _M_size members can be updated after the merge
finishes. The work is done in a try-block so that the sizes can still be
updated in an exception handler if any element comparison throws.

The _M_size members only exist for the cxx11 ABI, so the initial call to
size() and the try-catch are only needed for that ABI. For the old ABI
the size() call performs an O(N) list traversal to get a value that
isn't even used, and catching exceptions just to rethrow them isn't
needed either.

This refactors the merge functions to remove the try-catch block and use
an RAII type instead. For the cxx11 ABI that type's destructor updates
the list sizes, and for the old ABI it's a no-op.

libstdc++-v3/ChangeLog:

* include/bits/list.tcc (list::merge): Remove call to size() and
try-catch block. Use _Finalize_merge instead.
* include/bits/stl_list.h (list::_Finalize_merge): New
scope guard type to update _M_size members after a merge.
libstdc++-v3/include/bits/list.tcc
libstdc++-v3/include/bits/stl_list.h
This page took 0.054359 seconds and 5 git commands to generate.