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!
  • ../../../../../../_images/40-10-00-pointer-plus-int.svg
  • ../../../../../../_images/40-10-00-pointer-plus-int-error.svg

Pointer Increment and Decrement

Pointer Increment

int *pa = a;
++pa;
../../../../../../_images/40-10-00-pointer-increment.svg

Pointer Decrement

int *pa = &a[1];
--pa;
../../../../../../_images/40-10-00-pointer-decrement.svg

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 */
../../../../../../_images/40-10-00-pointer-out-of-range.svg 
*pa = a - 1;
pa += 2;
i = *pa; /* ok */
../../../../../../_images/40-10-00-pointer-out-of-range-negative.svg

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