STL components:
- Containers
- Sequential containers: vector, deque, list
- Associative containers: map, multimap, set, multiset
- C++0X: unsorted associative containers (hash)
- Algorithms
- Nonmodifying sequential algorithms
- Modifying sequential algorithms
- Sorted container algorithms
- Adaptors
- Container adaptors: stack, queue, priority_queue
- Others: iterator adaptors, inserters, etc.
- Functors, binders, ...
- Allocators
Types defined in a container:
template <class T, class A = allocator<T> > class std::vector {
public:
// types:
typedef T value_type; // type of element
typedef A allocator_type; // type of memory manager
typedef typename A::size_type size_type;
typedef typename A::difference_type difference_type;
typedef implementation_dependent1 iterator; // T*
typedef implementation_dependent2 const_iterator; // const T*
typedef std::reverse_iterator<iterator> reverse_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
typedef typename A::pointer pointer; // pointer to element
typedef typename A::const_pointer const_pointer;
typedef typename A::reference reference; // reference to element
typedef typename A::const_reference const_reference;
// ...
};
Usage of types declared in a container
makes you be able to write generic code
template<class C> typename C::value_type sum(const C& c)
{
typename C::value_type s = 0;
typename C::const_iterator p = c.begin(); // start at the beginning
while (p!=c.end()) { // continue until the end
s += *p; // get value of element
++p; // make p point to next element
}
return s;
}
Iterators and references
template <class T, class A = allocator<T> > class vector {
public:
// ...
// iterators:
iterator begin(); // points to first element
const_iterator begin() const;
iterator end(); // points to one-past-last element
const_iterator end() const;
reverse_iterator rbegin(); // points to first element of reverse sequence
const_reverse_iterator rbegin() const;
reverse_iterator rend(); // points to one-past-last element
const_reverse_iterator rend() const;
// ...
};
Usage of reverse iterator
template<class C> typename C::iterator find_last(C& c, typename C::value_type v)
{
typename C::reverse_iterator ri = find(c.rbegin(),c.rend(),v);
if (ri == c.rend()) return c.end(); // use c.end() to indicate "not found"
typename C::iterator i = ri.base();
return --i;
}
template<class C> typename C::iterator find_last(C& c, typename C::value_type v)
{
typename C::iterator p = c.end(); // search backwards from end
while (p!=c.begin())
if (*--p==v) return p;
return c.end(); // use c.end() to indicate "not found"
}
template<class C> typename C::iterator find_last(C& c, typename C::value_type v)
{
typename C::reverse_iterator p = c.rbegin(); // view sequence in reverse
while (p!=c.rend()) {
if (*p==v) {
typename C::iterator i = p.base();
return --i;
}
++p; // note: increment, not decrement (--)
}
return c.end(); // use c.end() to indicate "not found"
}
i = ri.base();
rend() ri rbegin()
| | |
V V V
-------------------
| 1 | 2 | 3 | 4 | 5 |
-------------------
^ ^ ^
| | |
begin() i end()
Constructors and assignments
template <class T, class A = allocator<T> > class vector {
public:
// ...
// constructors, etc.:
explicit vector(const A& = A());
explicit vector(size_type n, const T& val = T(), const A& = A()); // n copies of val
template <class In> // In must be an input iterator
vector(In first, In last, const A& = A()); // copy from [first:last[
vector(const vector& x);
~vector(); // destructor
vector& operator=(const vector& x); // assignment operator
template <class In> // In must be an input iterator (_iter.oper_)
void assign(In first, In last); // copy from [first:last[
void assign(size_type n, const T& val); // n copies of val
// ...
};
Use of constructors
vector<Record> vr(10000);
void f(int s1, int s2)
{
vector<int> vi(s1);
vector<double>* p = new vector<double>(s2);
}
void f(const list<X>& lst)
{
vector<X> v1(lst.begin(),lst.end()); // copy elements from list
char p[] = "despair";
vector<char> v2(p,&p[sizeof(p)-1]); // copy characters from C-style string
}
vector<int> v1(10); // ok: vector of 10 ints
vector<int> v2 = vector<int>(10); // ok: vector of 10 ints
vector<int> v3 = v2; // ok: v3 is a copy of v2
vector<int> v4 = 10; // error: attempted implicit conversion of 10 to vector<int>
void f1(vector<int>&); // common style
void f2(const vector<int>&);// common style
void f3(vector<int>); // rare style
void h()
{
vector<int> v(10000);
// ...
f1(v); // pass a reference
f2(v); // pass a reference
f3(v); // copy the 10000 elements into a new vector for f3() to use
}
Direct access for sequential containers
template <class T, class A = allocator<T> > class vector {
public:
// ...
// element access:
// only for vector and dequeue
reference operator[](size_type n); // unchecked access
const_reference operator[](size_type n) const;
// only for vector and dequeue
reference at(size_type n); // checked access
const_reference at(size_type n) const;
reference front(); // first element
const_reference front() const;
reference back(); // last element
const_reference back() const;
// ...
};
Stack operations
template <class T, class A = allocator<T> > class vector {
public:
// ...
// stack operations:
// not for vector
void push_front(const T& x); // add to the beginning
void pop_front(); // remove first element
void push_back(const T& x); // add to end
void pop_back(); // remove last element
// ...
};
void f()
{
vector<int> v;
v.pop_back(); // undefined effect: the state of v becomes undefined
v.push_back(7); // undefined effect (the state of v is undefined), probably bad
}
List operations
template <class T, class A = allocator<T> > class vector {
public:
// list operations:
iterator insert(iterator pos, const T& x); // add x before pos
void insert(iterator pos, size_type n, const T& x); // add n copies of x before pos
template <class In> // In must be an input iterator
void insert(iterator pos, In first, In last); // insert elements from sequence
iterator erase(iterator pos); // remove element at pos
iterator erase(iterator first, iterator last); // erase sequence
void clear(); // erase all elements
// ...
};
Usage of list operations
void duplicate_elements(vector<string>& f)
{
for(vector<string>::iterator p = f.begin(); p!=f.end(); ++p) f.insert(p,*p); // No!
}
template<class C> void f(C& c)
{
c.erase(c.begin()+7); // ok (if c's iterators support + )
c.erase(&c[7]); // not general
c.erase(c+7); // error: adding 7 to a container makes no sense
c.erase(c.back()); // error: c.back() is a reference, not an iterator
c.erase(c.end()-2); // ok (second to last element)
c.erase(c.rbegin()+2); // error: vector::reverse_iterator and vector::iterator
// are different types
c.erase((c.rbegin()+2).base()); // obscure, but ok
}
Size and Capacity
template <class T, class A = allocator<T> > class vector {
public:
// ...
// capacity:
size_type size() const; // number of elements
bool empty() const { return size()==0; }
size_type max_size() const; // size of the largest possible vector
void resize(size_type sz, T val = T()); // added elements initialized by val
size_type capacity() const; // size of the memory (in number of elements) allocated
void reserve(size_type n); // make room for a total of n elements; don't initialize
// throw a length_error if n>max_size()
// ...
};
Different containers have different memory usage characteristics:
______________________________________
|
|
|
__________|
|
__|
vector __|
________
| |
________| |____
| |
____| |______ ______
| | | |
_ | |____| |_____
|
dequeue | _
__| |_
_| |_
__ _| |_
_| |_| |_
_| |____
__| |_ _______
_| |___| |_____
list _|
The swap() trick for reduce vector's memory:
vector<int> v;
v.push_back(1); ....
vector<int>(v).swap(v);
template <class T, class A = allocator<T> > class vector {
public:
// ...
void swap(vector&);
};
template <class T, class A> void std::swap(vector<T,A>& x, vector<T,A>& y)
{
x.swap(y);
}
template <class T, class A>
bool std::operator==(const vector<T,A>& x, const vector<T,A>& y);
template <class T, class A>
inline bool std::operator<(const vector<T,A>& x, const vector<T,A>& y)
{
return lexicographical_compare(x.begin(),x.end(),y.begin(),y.end());
}
Container adaptors:
template <class T, class C = deque<T> > class std::stack {
protected:
C c;
public:
typedef typename C::value_type value_type;
typedef typename C::size_type size_type;
typedef C container_type;
explicit stack(const C& a = C()) : c(a) { }
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
value_type& top() { return c.back(); }
const value_type& top() const { return c.back(); }
void push(const value_type& x) { c.push_back(x); }
void pop() { c.pop_back(); }
};
Queue and priority_queue are similar.