Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is it correct to remove elements with std::list::remove using an alias to an element in the container?

When I compile this program:

#include <list>

int main() {
    std::list<int> l = {1, 2};
    l.remove(l.front());
}

With clang using ASAN and debug:

clang++-8 -fno-omit-frame-pointer -g -fsanitize=address -D_GLIBCXX_DEBUG -std=c++11 list-remove.cpp

I get a heap-use-after-free:

==31868==ERROR: AddressSanitizer: heap-use-after-free on address 0x603000000020 at pc 0x0000004fa1ae bp 0x7fff52cc5630 sp 0x7fff52cc5628
READ of size 4 at 0x603000000020 thread T0
    #0 0x4fa1ad in std::__debug::list<int, std::allocator<int> >::remove(int const&) /usr/bin/../lib/gcc/x86_64-linux-gnu/7.4.0/../../../../include/c++/7.4.0/debug/list:649:18
    #1 0x4f990f in main /tmp/list-remove.cpp:5:7
    #2 0x7ff27d974b96 in __libc_start_main /build/glibc-OTsEL5/glibc-2.27/csu/../csu/libc-start.c:310
    #3 0x41b879 in _start (/tmp/list-remove+0x41b879)

It seems when remove finds x matches the first element, it removes the element from the list and deletes it. When it goes to check the second element, it then uses x which has already been deleted to compare the element.

Is this a correct implementation according to C++ standard? It seems it would be better for it to move the elements to the end first and then delete them. This will avoid the heap-use-after-free error, but perhaps such an implementation is not required.

From cppreference it makes no mention that the value cannot be an alias to the element in the container.

Here is the c++ version I am using:

$ /usr/bin/c++ --version
c++ (Ubuntu 7.4.0-1ubuntu1~18.04.1) 7.4.0
Copyright (C) 2017 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
like image 235
Paul Fultz II Avatar asked Sep 20 '19 17:09

Paul Fultz II


People also ask

How to delete an element in a list c++?

remove() is an inbuilt function in C++ STL which is declared in header file. remove() is used to remove any specific value/element from the list container. It takes the value which is passed as a parameter and removes all the elements with that value from the list container.

How do you remove an element from a vector in C++?

The C++ vector has many member functions. Two of these member functions are erase() and pop_back(). pop_back() removes the last element from the vector. In order to remove all the elements from the vector, using pop_back(), the pop_back() function has to be repeated the number of times there are elements.


1 Answers

This question was asked (and answered) in LWG 526, which said:

list::remove(value) is required to work because the standard doesn't give permission for it not to work.

This was fixed in libc++ back in 2014

like image 133
Marshall Clow Avatar answered Oct 12 '22 14:10

Marshall Clow