- The STL
- STL components.
- Containers
- Iterators
- Generic algorithms.
- The four stages of STL use.
- Generic programming.
- The Standard Template Library (STL)
- Standard
- Part of any standards-compliant C++ compiler.
- Requires advanced features (default template values, for example).
- Some compilers (Microsoft Visual C++ 6.0, for example) can't hack
it.
- Include files don't end in
.h.
- Everything's defined in the
std namespace.
- Template
- Not a lot of object play involved.
- Templates give the STL its power, and make it hard to use.
- Subtle errors, humungous error messages.
- Library
- Actually just header files, no libraries involved.
- Six main components; three we'll spend a lot of time on, three we won't.
- The three main components are containers, iterators and generic
algorithms.
- A container is a data structure.
- An iterator references data in a container.
- A generic algorithm manipulates data referenced by iterators.
- The other three components.
- An adaptor changes the behavior of a component.
- There are adaptors for containers and iterators.
- A functor is an object that acts like a function.
- An allocator manages container storage.
- Containers separate into sequential and sorted associative containers.
- We'll be studying the vector and list sequential containers and the
map sorted associative container.
- A sequential container represents a sequence of values.
- Ordinary c++ arrays.
- STL vectors are dynamic arrays.
- Similar to pointers.
- More accurately called accessors.
- Relative to containers, unlike pointers.
- Iterators are the connective tissue between containers and generic algorithms.
- This is the basis of generic programming.
- The most important part of the STL.
- You can use the generic algorithms in the absence of anything else in
the STL.
- Look for
item in the container part delimited by start and end.
- That's a linear search.
-
std::find(start, end, item)
- There are lots more.
- Part of the STL standard includes performance requirements.
- The search generic algorithm
find() should be linear.
- The container member function
push_back() should be
amortized linear
.
- Understanding the performance requirements helps in understanding
the STL.
- Why doesn't vector have
.push_front()?
- Why can't I use
std::sort() on a list?
- Understanding the performance requirements helps in selecting STL
components.
- The STL has a lot of different ways to do the same thing. Which do
you choose?
- Estimate operation counts on your data structures.
- Pick STL components that cheaply provide the most frequent
operations.
- Denial.
- Why use that? I've got my own list class I can use.
- Acceptance.
- Oh, o.k. - I'll use maps. And maybe their list class isn't as buggy
as mine. But iterators are still stupid.
- Embrace.
- Hey, look at this: by putting this string into an istring stream, I
can pull off some istream iterators and use them in the copy algorithm to
back insert the words directly into a vector. Cool.
- Extend.
- Humm, maybe if I write an allocator that manages space in a disk
file, I can create persistent containers...
This page last modified on 12 February 2004.