Lecture Notes for SE 598, Data Structures and Algorithms

31 May 2000, Standard Template Library Introduction

1. generic programming

   1. data structures and algorithms - who is to be the boss

   2. data structures - object-oriented programming

   3. algorithms - procedural programming

   4. neither - generic programming

2. stl components

   1. containers - data structures

   2. generic algorithms - algorithms

   3. iterators - the link between containers and generic algorithms

   4. function objects - make generic algorithms useful

   5. adaptors - make one container into another

   6. allocators - mystery

3. containers - sequence sorted associative

   1. sequence

      1. arrays - ordinary c++ arrays

      2. vector - an array that can grow on one end

      3. dequeue - an array that can grow and shrink at both ends

      4. list - dequeue that can grow and shrink at both ends

   2. sorted associative containers

      1. sets - a collection of unique objects

      2. multisets - a collection of objects (bags)

      3. map - an associative array linking keys to elements

      4. multimap - associate a key with a set of elements

4. generic algorithms

   1. find(start, end, item) - look for item in the container part delimited by start and end.

   2. merge(start1, end1, start2, end2, result) - merge the contents of the container part delimited by start1 and end1 with the contents of the container part delimited by start2 and end2 and store the result in the container starting at result.

   3. accumulate(start, end, init, op) - perform op on the contents of the container part delimited by start and end and using init as the initial value; return the result

   4. lots more

5. iterators

   1. better called accessors

   2. how do algorithms get at the contents of a container - via the iterators provided by each container

This page last modified on 31 May 2000.