Standard Template Library: Basics¶

Containers, Iterators, Algorithms ¶

Genius Combination of …

Operator overloading (->, *, +, +=, ++)
Abstract containers
Abstract algorithms
… based upon pointer arithmetic!

⟶ Pointer arithmetic, revisited …

Blahblah ¶

Pointer and array index

Pointer + Integer = Pointer
Exactly the same as subscript (“index”) operator
No range check
⟶ Error prone
But: performance!

Pointer Increment and Decrement ¶

Pointer Increment int *pa = a; ++pa;
Pointer Decrement int *pa = &a[1]; --pa;

Out Of Range Errors (The Spirit Of C)¶

Pointers don’t necessarily point to valid memory locations …

pa = a + 4; pa -= 2; i = pa; /* ok */
pa = a - 1; pa += 2; i = pa; /* ok */

Pointer Difference ¶

How many array elements are there between two pointers?

p = &a[0];
q = &a[2];
num = q - p;      /* 2 */

../../../../../../_images/40-10-00-pointer-diff.svg

General practice (“The Spirit of C”): [1]

Beginning of an array (a set of elements) is a pointer to the first element
End is pointer past the last element

Step Width? (1)¶

So far: pointer to int - how about different datatypes?

⟶ same!

pointer + n: points to the n-th array element from pointer
Type system knows about sizes
Pointer knows the type of the data it points to
Careful with void and void*

Step Width? (2)¶

struct point
{
    int x, y;
};

struct point points[3], *begin, *end;

begin = points;
end = points + sizeof(points)/sizeof(struct point);

while (begin < end) {
    ...
    ++begin;
}

And Arbitrary Data Types?¶

sizeof: size (in bytes) of a type or variable

sizeof(int)
sizeof(struct point)
sizeof(i)
sizeof(pi)
sizeof(pp)

../../../../../../_images/40-10-00-pointer-plus-int-generalized.svg

Enter Algorithms (On Good Old C Arrays)¶

Iteration over all elements of an array
begin: pointer to first element, inclusive
end: pointer past last element, exclusive
⟶ range [begin, end)

int sum(const int *begin, const int *end)
{
    int sum = 0;

    while (begin < end)
        sum += *begin++; /* precedence? what? */
    return sum;
}

void copy(const int *src_begin, const int *src_end, int *dst_begin)
{
    while (src_begin != src_end)
        *dst_begin++ = *src_begin++;
}

../../../../../../_images/40-10-00-pointer-begin-end.svg

Pretty, isn’t it?

STL Algorithms ¶

#include <algorithm>
Many general purpose algorithms
One of the simplest: std::copy<>()

STL Containers ¶

Container

Extremely practical collection of template classes
Sequential container ⟶ array, list
Associative containers

Footnotes