ProgrammingThis forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.
Notices
Welcome to LinuxQuestions.org, a friendly and active Linux Community.
You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!
Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.
If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.
Having a problem logging in? Please visit this page to clear all LQ-related cookies.
Get a virtual cloud desktop with the Linux distro that you want in less than five minutes with Shells! With over 10 pre-installed distros to choose from, the worry-free installation life is here! Whether you are a digital nomad or just looking for flexibility, Shells can put your Linux machine on the device that you want to use.
Exclusive for LQ members, get up to 45% off per month. Click here for more info.
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<int> ints;
for(int i = 0; i < 9; ++i) ints.push_back(i+1);
list<list<int>::iterator> ptrs;
for(list<int>::iterator it = ints.begin(); it != ints.end(); ++it) ptrs.push_back(it);
cout << "Before deleting the last number:" << endl;
cout << "Direct access" << endl;
for(list<int>::iterator it = ints.begin(); it != ints.end(); ++it) cout << *it << "\t";
cout << endl;
cout << "Indirect access" << endl;
for(list<list<int>::iterator>::iterator it_it = ptrs.begin(); it_it != ptrs.end(); ++it_it) cout << **it_it << "\t";
cout << endl;
// Deleting the last number
ints.erase(--ints.end());
cout << "After deleting the last number:" << endl;
cout << "Direct access" << endl;
for(list<int>::iterator it = ints.begin(); it != ints.end(); ++it) cout << *it << "\t";
cout << endl;
cout << "Indirect access" << endl;
for(list<list<int>::iterator>::iterator it_it = ptrs.begin(); it_it != ptrs.end(); ++it_it) cout << **it_it << "\t";
cout << endl;
return 0;
}
No matter what version of GCC compilers were used, e.g. 3.2.3, 3.4.4, 4.0.1, the last number "9" could always be accessed through the iterator of the iterator pointing to "9" after it was deleted. Why? I think the compiled program should generate a runtime "segmentation fault" error when the program tried to access the last number "9". Anyone knows why?
You remove the value from one but not the other. Which is why the other list still displays the original nine values.
Oh yes, ints stores the actual numbers, and ptrs stores the iterators of those numbers in ints. The deletion operation deletes the actual numbers in ints and keep those iterators untouched. The problem is that after deletion the deleted number can still be accessed through its DELETED iterator from ptrs. Logically this should not happen. After doing some researches, I found out the possible cause: the way how std::list actually uses its memory allocation method. The definition of std::list is:
list<T, Alloc>
The parameter Alloc determins what memory allocation method to use among four choices: alloc, pthread_alloc, single_client_alloc and malloc_alloc. The list container may temporarily keep the deleted iterator after it is removed, but how long this deleted iterator remains effective is unknown to outside which means a deleted iterator should not be used any more. But for some reason, if a program is mistakenly coded, for example in my case, I forgot to remove an iterator which I kept elsewhere after it was deleted by the original list container, and then I accessed this iterator sometime later. What happened then is: the program compiled by the GCC compiler older than 3.4 met "segmentation fault" after this program rans briefly, but the same program compiled by newer version of GCC ran without any problem. I don't know if this is good or bad, but I guess the older GCC did the right thing which then let me find out the bug of my program.
Or more to the point don't store iterators. They are inherently unsafe in the same way the pointers are inherently unsafe with the added bonus that the data they refer to may have become invalid. Which may happen with a vector when you add more elements and the underlying memory is reallocated.
The iterator essentially points to an area of memory, if you tell the computer that you no longer want to use that memory then it is free to reallocate it, but the memory is still there and so you can still look at it.
In short use iterators as temporary acquaintances not as long term friends
After any erase operation with most STL containers, all iterators "expire". This means they should no longer be used; it's just like trying to use a pointer after deleting it. Even though the system recognizes the memory as free, it doesn't take steps to erase it; it waits until something else needs that space. Your program is simple enough that nothing needed to overwrite it. Also, std::list uses automatic allocation with guestimating. This means that when you create it, it has a certain amount of memory for elements. When it becomes full, it reallocates to another guestimated size. When you deleted the element, the list probably just decremented the internal size value and went on with its business (and maybe called ~int(), which is superfluous); one element of an integral type isn't enough for it to reallocate to a smaller size.
ta0kira
In C and C++, you are almost never assured of getting a segmentation fault in response to a particular action. You can *sometimes* dereference a pointer after free()ing it, write past the end of an array, dereference a pointer to a stack variable from a function that has returned, or dereference an uninitialized pointer without a segmentation fault. Hell, you can even construct circumstances where you can dereference NULL
Using the iterator after it's supposed to be invalid probably does one of these things.
ta0kira points out that the stl keeps blocks of list nodes around, and the iterator probably pointed to a freed node. malloc() and operator new can do roughly the same thing. moral: almost never be suprised by not getting a segfault : )
As far as I can remember, I've never had a case where accessing a non-floating point integral type from a bad pointer (or as a member of a class through a bad pointer) has caused an exception. In fact, a lot of my troubles early on in C++ were from this; I could write to a bad location, but the error didn't show up until something else found out that it had been accidentally modified. That makes debugging VERY difficult. Too bad Linux doesn't give an address with the segfault.
ta0kira
As far as I can remember, I've never had a case where accessing a non-floating point integral type from a bad pointer (or as a member of a class through a bad pointer) has caused an exception. In fact, a lot of my troubles early on in C++ were from this; I could write to a bad location, but the error didn't show up until something else found out that it had been accidentally modified. That makes debugging VERY difficult. Too bad Linux doesn't give an address with the segfault.
ta0kira
Oh boy, we are having the exactly same kind of headache! My porgram makes very intensive use of std::list and its iterator. Since my program has to update the elements held in list based on their fairly complex relationships, it is very common for me to accidently access some elements that have already been deleted during development stage. But such illegal access won't cause "segmentation fault" all the time, but only sometimes, and the place where the debugger shows the segmental fault happens usually is not where the actual problem is. This took me weeks to locate the actual roots of the problems. //sigh... It seems it's the time to start thinking about using smart pointers, e.g. BOOST's smart pointer types.
I've got a list class. It isn't for everyone or every application, though; it's not really intended for simple operations and incidentally it takes a little more learning up front than the STL containers. The big thing is that you never deal with iterators.
ta0kira
LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.