Assembly Language for Beginners

3.18. C++

This is very helpful here: having a pointer to the first list element, i.e., that is in thelvariable, it is easy
to get a pointer to the last one quickly, without the necessity to traverse the whole list.

Inserting an element at the end of the list is also quick, thanks to this feature.

operator--andoperator++just set the current iterator’s value to the
current_node->prevorcurrent_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 has
been 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 means that this operation isO(n), i.e., it steadily gets slower as the list grows.

Listing 3.109: 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