Reverse Engineering for Beginners

CHAPTER 51. C++ CHAPTER 51. C++

operator--andoperator++just set the current iterator’s value to thecurrent_node->prevor
current_node->nextvalues. The reverse iterators (.rbegin, .rend) work just as the same, but in reverse.

operator*just returns a pointer to the point in the node structure, where the user’s structure starts, i.e., a pointer to the
first element of the structure (x).

The list insertion and deletion are trivial: just allocate a new node (or deallocate) and update all pointers to be valid.

That’s why an iterator may become invalid after element deletion: it may still point to the node that was already deallocated.
This is also called adangling pointer. And of course, the information from the freed node (to which iterator still points)
cannot be used anymore.

The GCC implementation (as of 4.8.1) doesn’t store the current size of the list: this implies a slow .size() method: it has to
traverse the whole list to count the elements, because it doesn’t have any other way to get the information. This mean that
this operation isO(n), i.e., it gets slower steadily as the list grows.

Listing 51.29: Optimizing GCC 4.8.1 -fno-inline-small-functions

main proc near
push ebp
mov ebp, esp
push esi
push ebx
and esp, 0FFFFFFF0h
sub esp, 20h
lea ebx, [esp+10h]
mov dword ptr [esp], offset s ; " empty list:"
mov [esp+10h], ebx
mov [esp+14h], ebx
call puts
mov [esp], ebx
call _Z13dump_List_valPj ; dump_List_val(uint )
lea esi, [esp+18h]
mov [esp+4], esi
mov [esp], ebx
mov dword ptr [esp+18h], 1 ; X for new element
mov dword ptr [esp+1Ch], 2 ; Y for new element
call _ZNSt4listI1aSaIS0_EE10pushfrontERKS0 ; std::list<a,std::allocator>::push_front(a⤦
Ç const&)
mov [esp+4], esi
mov [esp], ebx
mov dword ptr [esp+18h], 3 ; X for new element
mov dword ptr [esp+1Ch], 4 ; Y for new element
call _ZNSt4listI1aSaIS0_EE10pushfrontERKS0 ; std::list<a,std::allocator>::push_front(a⤦
Ç const&)
mov dword ptr [esp], 10h
mov dword ptr [esp+18h], 5 ; X for new element
mov dword ptr [esp+1Ch], 6 ; Y for new element
call _Znwj ; operator new(uint)
cmp eax, 0FFFFFFF8h
jz short loc_80002A6
mov ecx, [esp+1Ch]
mov edx, [esp+18h]
mov [eax+0Ch], ecx
mov [eax+8], edx