整理电脑的时候，翻出来一篇不知道是猴年马月写的文章，关于STL的简单介绍，应该是以前写给学生看的吧，贴在这里分享一下。
STL是Standard Template Library的缩写，是C++标准库中最强大、最复杂、最有用的部分。STL主要由容器（container）、跌代子（iterator）、算法（algorithm）所组成。
容器是存放和管理数据元素的数据结构，容器分为两大类：顺序容器（sequence container）和关联容器（associative container）。
顺序容器有：vector, deque, list
关联容器有：map, set, multi_map, multi_set
特殊的容器：string, array
容器适配器：stack, queue, priority_queue
跌代子是用来访问容器内元素的对象，类似指针。
跌代子分为：随机跌代子，双向跌代子，单向跌代子，输入跌代子，输出跌代子
跌代子适配器
算法是用来处理容器内的元素的一些操作，比如搜索、排序、拷贝、修改等。
算法分为两大类：更易型和非更易型
仿函数：类似函数指针
vector类似于数组，但是可以动态分配空间。
#include <vector>
namespace std {
template< class T, class Allocator = allocator<T> > vector;
}
T可以是任何类型，但是必须满足：assignable, copyable
1. 构造方法：
vector< int > a1; // 构造一个空的vector
vector< int > a2(10); //构造10个元素的vector
vector< int > a3(10, 5); //构造一个10个元素的vector，每个元素都是5
vector < int > a4(a2); //构造一个vector与a2完全一样
int values[] = {10, 11, 12, 13, 14};
vector < int > a5( values, values+5);
2. 不变操作和赋值
a1.size( ) //取容器内元素的个数
a1.empty( ) //判断容器是否为空
a1 == a2 //判断两个容器的内容是否相同, 还有!=, <, >, <=, >=
a1 = a2 //将a2全部元素赋给a1
a1.assign( values, values+5 ) //将values[0]到values[4]赋给a1
a1.assign( 10, 5) //给a1赋值10个5
3. 元素访问
a1[ 5 ] //取第5个元素，下标从0开始
a1.at(5) //取第5个元素，带边界检查
a1.front() //取第0个元素
a1.end() //取最后一个元素
4. 跌代子
a1.begin() //随机跌代子，指向a1[0]
a1.end() //随机跌代子，指向最后一个的下一个
a1.rbegin() //随机跌代子，指向最后一个
a1.rend() //随机跌代子，指向a1[0]的前一个
5. 插入删除操作
a1.insert( a1.begin(), 5); //在a1的最前面插入一个5
a1.insert(a1.end(), 10, 6); //在a1的最后面插入10个6
a1.insert(a1.begin(), values, values+5) //在a1的最前面插入values[0]到values[4]
a1.push_back( 5 ) //在a1的最后面插入一个5
a1.pop_back( ) // 删除a1的最后一个元素
a1.erase( a1.begin() ) //删除a1中的第一个元素
a1.erase( a1.begin(), a1.begin() +2) //删除a1最前面2个元素
a1.resize( 10 ) //将a1元素个数改为10，增加的部分值为默认构造
a1.resize( 10, 6) //将a1元素个数改为10，增加的部分值为6
a1.clear() //清除所有元素
类似于数据结构中的顺序表
a1.capacity() //返回容量的大小
a1.reserve(10); //改变容量的大小
int main() {
vector< string > sentence;
sentence.reserve( 5 );
sentence.push_back( “ Hello, “);
sentence.push_back( “how “);
sentence.push_back( “are “);
sentence.push_back( “you “);
sentence.push_back( “?“);
copy( sentence.begin(), sentence.end(), ostream_iterator<string>(cout, “ “));
cout << endl;
cout << sentence.size() << endl;
cout << sentence.capacity() << endl;
swap( sentence[1], sentence[3]);
sentence.insert( find(sentence.begin(), sentence.end(), “?”), “always”);
sentence.back() = “!”;
copy( sentence.rbegin(), sentence.rend(), ostream_iterator<string>(cout, “ “));
cout << endl;
}
vector < int > a(10);
a[0] = 1;
a[1] = 2;
a[2] = a[0] + a[1];
for( int i = 0; i < a.size(); i++)
scanf( “%d”, &a[i] );
处理容器内的数据的函数
#include <algorithm> //一般算法
#include <numeric> //数值算法
#include <functional> //仿函数
for_each
count
count_if
min_element
max_element
find
find_if
search_n
search
find_end
find_first_of
adjacent_find
equal
mismatch
lexicographical_compare
copy
copy_backward
transform
merge
swap_ranges
fill
fill_n
generate
generate_n
replace
replace_if
replace_copy
replace_copy_if
remove
remove_if
remove_copy
remove_copy_if
unique
unique_copy
reverse
reverse_copy
rotate
rotate_copy
next_permutation
prev_permutation
random_shuffle
partition
stable_partition
sort
stable_sort
partial_sort
partial_sort_copy
nth_element
partition
stable_partition
make_heap
push_heap
pop_heap
sort_heap
binary_search
includes
lower_bound
upper_bound
equal_range
merge
set_union
set_intersection
set_difference
set_symmetric_difference
inplace_merge
accumulate
inner_product
adjacent_difference
partial_sum
对区间内每一个元素采用某一种操作
实现：
template <class InputIterator, class UnaryFunction>
UnaryFunction for_each(InputIterator first, InputIterator last, UnaryFunction f) {
while( first != end) {
f(*first);
++first;
}
return f;
}
用例1：
void print ( int elem) {
cout << elem << ‘ ‘;
}
int main() {
vector< int > col( 5, 10);
for_each( col.begin(), col.end(), print);
cout << endl;
}
用例2：
template< class T>
class AddValue{
private:
T value;
public:
AddValue( const T&v) : value(v) {}
void operator()(T&elem) const { elem+=value; }
};
int main() {
vector<int > col(5, 10);
for_each(col.begin(), col.end(), AddValue<int>(10));
copy( col.begin(), col.end(), ostream_iterator<int>(cout, “ “));
}
用例3：
class MeanValue {
private:
int num, sum;
public:
MeanValue() : num(0), sum(0) {}
void operator()( int elem ) { num ++; sum+=elem; }
double value() { return static_cast<double>(sum) / static_cast<double>(num); }
};
int main() {
vector<int> col(5, 10);
MeanValue mv = for_each(col.begin(), col.end(), MeanValue() );
cout << mv.value();
}
功能1：将区间内每个元素作变换，存储到另一个空间里面
template <class InputIterator, class OutputIterator, class UnaryFunction>
OutputIterator transform(InputIterator first, InputIterator last, OutputIterator result, UnaryFunction op) {
while( first != last ) {
*result = op(*first);
++result;
++first;
}
return result;
}
功能2：将两个区间内的元素作变换，存储到另一个空间内
template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryFunction>
OutputIterator transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryFunction binary_op) {
while( first1 != last1 ) {
*result = op(*first1, *first2);
++result;
++first1;
++first2;
}
return result;
}
用例1：
int main() {
vector< int > c1(5, 10);
transform( c1.begin(), c1.end(), c1.begin(), negate<int>() );
list < int> c2;
transform( c1.begin(), c1.end(), back_inserter(c2), bind2nd(multiplies<int>(), 5));
transform( c2.rbegin(), c2.rend(), ostream_iterator<int>(cout, “ “), negate<int>());
transform( c1.begin(), c1.end(), c1.begin(), c1.begin(), multiplies<int>());
transform( c1.begin(), c1.end(), c2.rbegin(), c1.begin(), plus<int>());
transform( c1.begin(), c1.end(), c1.begin(), ostream_iterator<int>(cout, “ “), minus<int>() );
}
能像函数一样使用的对象。普通函数、函数指针、定义了operator()的类的对象都可以作为仿函数。
#include <functional>
不带参数的仿函数
比如：
rand
带一个参数的仿函数。
比如：
abs
negate
identity
返回真或假的Unary Function
比如：
logical_not
带两个参数的仿函数。
plus
minus
multiplies
divides
modulus
返回真或假的Binary Function
less
greater
equal_to
not_equal_to
less_equal
greater_equal
logical_and
logical_or
bind1st
bind2nd
not1
not2
mem_fun_ref
mem_fun
ptr_fun
compose1
compose2
例1
find_if (coll.begin(),coll.end(), bind2nd (greater<int>(),42));
例2
pos = find_if (coll.begin() , coll.end(), not1 (bind2nd(modulus<int>(),2)));
list<int> L;
list<int>::iterator first_positive = find_if(L.begin(), L.end(), bind2nd(greater<int>(), 0));
例3
class Person {
private:
std::string name;
public:
void print() const {
std::cout << name << std::endl;
}
void printWithPrefix (std::string prefix) const {
std::cout << prefix << name << std::endl;
}
};
void foo (const std::vector<Person>& coll){
for_each (coll.begin(), coll.end(), mem_fun_ref(&Person::print));
for_each (coll.begin(), coll.end(), bind2nd (mem_fun_ref (&Person::printWithPrefix), "person: "));
}
void ptrfoo (const std::vector<Person*>& coll) {
for_each (coll.begin() , coll.end(), mem_fun(&Person::print));
for_each (coll.begin() , coll.end(), bind2nd(mem_fun(&Person::printWithPrefix), "person: "));
}
例4
bool check(int elem);
pos = find_if (coll.begin(), coll.end(), not1(ptr_fun(check)));
pos = find_if (coll.begin(), coll.end(), bind2nd(ptr_fun(strcmp),""));
transform(first, last, first, compose1(negate<double>, ptr_fun(fabs)));
例5
list<int> L;
list<int>::iterator in_range = find_if(L.begin(), L.end(),
not1(compose2(logical_and<bool>(), bind2nd(greater_equal<int>(), 1), bind2nd(less_equal<int>(), 10))));
例6
char str[MAXLEN];
const char* wptr = find_if(str, str + MAXLEN, compose2(not2(logical_or<bool>()), bind2nd(equal_to<char>(), ' '), bind2nd(equal_to<char>(), '\n')));
迭代子是一种能够遍历容器里面的全部或者部分元素的对象，一个迭代子能够表示容器里面一个特定的位置。
使用begin(), end()获得容器的迭代子。迭代子的类型会随着容器的不同而不同，可表示为container<T>::iterator,如果支持双向跌代，则可以通过rbegin(), rend()获得反向跌代子。反向跌代子的类型为：container<T>::reverse_iterator,
Input：只能单向读取，比如istream
Output：只能单向写入，比如ostream
Forward：单向读取和写入，具有Input和Output跌代子的全部能力，比如slist
Bidirectional：双向读取和写入，具有Forward跌代子的全部能力，比如list, set, map
Random：随机读取和写入，具有Bidirectional跌代子的全部能力，比如vector, deque
迭代子最基本的操作有：
iter++, ++iter：让跌代子移动到下一个元素，有前置后置两种形式。
*iter：返回迭代子当前位置上的元素。如果是Input代子，返回元素的值，只能读取；如果是Output跌代子，返回引用，只能写入。
iter1 == iter2 , iter1 != iter2：判断两个跌代子是否指向同一个位置。（Output没有此操作）
iter1 = iter2：改变跌代子指向的位置。（Output没有此操作）
iter ->：如果元素是类（结构体），则可以使用->直接访问元素的成员。
iter --, --iter：使用--移动到前一个元素，有前置后置两种形式。（双向跌代子和随机跌代子）
iter [n]：后面第n个的元素（Random跌代子）
iter += n：往后面移动n个位置（Random跌代子）
iter -= n：往前面移动n个位置（Random跌代子）
iter + n, n + iter：后面第n个位置（Random跌代子）
iter - n：前面第n个位置（Random跌代子）
iter1 - iter2: 两个元素之间的距离（Random跌代子）
iter1<iter2, iter1 > iter2, iter1 <= iter2, iter1 >= iter2: 比较两个跌代子的位置（Random跌代子）
advance(iter, n)：将跌代子后移n个位置
distance(iter1, iter2)：两个跌代子之间的距离
reverse iterator
insert iterators(back_inserter, front_inserter, inserter)
Stream Iterators(ostream_iterator, istream_iterator)
例1
//OK for forward iterators
//IMPOSSIBLE for output iterators
while (pos != coll.end()) {
*pos = foo();
++pos;
}
例2
int main() {
vector<int> coll;
for (int i=-3; i<=9; ++i) {
coll.push_back (i);
}
cout << "number/distance: " << coll.end()-coll.begin() << endl;
vector<int>::iterator pos;
for (pos=coll.begin(); pos<coll.end(); ++pos) {
cout << *pos << ' ';
}
for (int i=0; i<coll.size(); ++i) {
cout << coll.begin() [i] << ' ';
}
for (pos = coll.begin(); pos < coll.end()-1; pos += 2) {
cout << *pos << ' ';
}
}
例3
int main() {
list<int> coll;
//insert elements from 1 to 9
for (int i=1; i<=9; ++i) {
coll.push_back(i);
}
list<int>::iterator pos = coll.begin();
cout << *pos << endl;
advance (pos, 3);
cout << *pos << endl;
advance (pos, -1);
cout << *pos << endl;
}
例4
int main(){
list<int> coll;
for (int i=-3; i<=9; ++i) {
coll.push_back(i);
}
list<int>::iterator pos;
pos = find (coll.begin(), coll.end(), 5);
if (pos != coll.end()) {
cout << distance(coll.begin(),pos) << endl;
}
else {
cout << "5 not found" << endl;
}
}
例5
void print (int elem) {
cout << elem << ' ';
}
int main() {
list<int> coll;
for (int i=1; i<=9; ++i) {
coll.push_back(i);
}
for_each (coll.begin(), coll.end(), print);
for_each (coll.rbegin(), coll.rend(), print);
}
例6
int main() {
vector<int> coll;
for (int i=1; i<=9; ++i) {
coll.push_back(i);
}
vector<int>::iterator pos;
pos = find (coll.begin(), coll.end(), 5);
cout << "pos: " << *pos << endl;
vector<int>::reverse_iterator rpos(pos);
cout << "rpos: " << *rpos <<endl;
}
例7
void print (int elem) {
cout << elem << ' ';
}
int main() {
deque<int> coll;
for (int i=1; i<=9; ++i) {
coll.push_back(i);
}
deque<int>::iterator pos1;
pos1 = find (coll.begin(), coll.end(), 2);
deque<int>::iterator pos2;
pos2 = find (coll.begin(), coll.end(), 7);
for_each (pos1, pos2, print);
deque<int>::reverse_iterator rpos1(pos1);
deque<int>::reverse_iterator rpos2(pos2);
for.each (rpos2, rpos1, print);
}
例8
int main(){
list<int> coll;
for (int i=1; i<=9; ++i) {
coll.push_back(i);
}
list<int>::iterator pos;
pos = find (coll.begin(), coll.end(),5);
cout << "pos: " << *pos << endl;
list<int>::reverse_iterator rpos(pos);
cout << "rpos: " << *rpos << endl;
list<int>::iterator rrpos;
rrpos = rpos.base();
cout << "rrpos: " << *rrpos << endl;
}
例9
int main() {
vector<int> coll;
back_insert_iterator<vector<int> > iter(coll);
*iter = 1;
iter++;
*iter = 2;
iter++;
*iter = 3;
copy( col1.begin(), col1.end(), ostream_iterator<int>(cout, “ “));
back_inserter(coll) = 44;
back_inserter(coll) = 55;
copy( col1.begin(), col1.end(), ostream_iterator<int>(cout, “ “));
copy (coll .begin(), coll.end(), back_inserter(coll));
copy( col1.begin(), col1.end(), ostream_iterator<int>(cout, “ “));
}
例10
int main() {
list<int> coll;
front_insert_iterator<list<int> > iter(coll);
*iter = 1;
iter++;
*iter = 2;
iter++;
*iter = 3;
copy( col1.begin(), col1.end(), ostream_iterator<int>(cout, “ “));
front_inserter(coll) = 44;
front_inserter(coll) = 55;
copy( col1.begin(), col1.end(), ostream_iterator<int>(cout, “ “));
copy (coll.begin(), coll.end(), front_inserter(coll));
copy( col1.begin(), col1.end(), ostream_iterator<int>(cout, “ “));
}
例11
int main() {
ostream_iterator<int> intWriter(cout,"\n");
*intWriter = 42;
intWriter++;
*intWriter = 77;
intWriter++;
*intWriter = -5;
vector<int> coll;
for (int i=1; i<=9; ++i) {
coll.push_back(i);
}
copy (coll.begin(), coll.end(), ostream_iterator<int>(cout));
copy (coll.gin(), coll.end(), ostream_iterator<int>(cout," < "));
}
例12
int main(){
istream_iterator<int> intReader(cin);
istream_iterator<int> intReaderEOF;
while (intReader != intReaderEOF) {
cout << "once: " << *intReader << endl;
cout << "once again: " << *intReader << endl;
++intReader;
}
}
例13
int main() {
istream_iterator<string> cinPos(cin);
ostream_iterator<string> coutPos(cout," ");
while (cinPos != istream_iterator<string>()) {
advance (cinPos, 2);
if (cinPos != istream_iterator<string>()) {
*coutPos++ = *cinPos++;
}
}
cout << endl;
}
例14
int main() {
vector<Date> e;
copy( istream_iterator<Date>(cin), istream_iterator<Date>(), back_inserter(e));
vector<Date>::iterator first = find(e.begin(), e.end(), "01/01/95");
vector<Date>::iterator last = find(e.begin(), e.end(), "12/31/95");
*last = "12/30/95";
copy(first, last, ostream_iterator<Date>(cout, "\n"));
e.insert(--e.end(), TodaysDate());
copy( first, last, ostream_iterator<Date>(cout, "\n") );
}
注：早先获得的跌代子在特定的操作后会失效！！vector的迭代子在插入、删除以及重新分配内存后可能会失效。
#include <deque>
deque与vector相似，区别是deque两端都是开放的，两端插入删除都很快。
deque的内存结构
可以随机访问，但比vector稍慢
迭代子是随机跌代子，是一种class而不是原始指针
操作非常相似，增加操作：push_front, pop_front，减少操作：reserve,capacity
任何插入和删除操作都可能使跌代子失效
例子：
int main() {
deque<string> coll;
coll.assign (3, string("string"));
coll.push_back ("last string");
coll.push_front ("first string");
copy (coll.begin(), coll.end(), ostream_iterator<string>(cout,"\n"));
coll.pop_front();
coll.pop_back();
for (int i=1; i<coll.size(); ++i) {
coll[i] = "another " + coll [i];
}
coll.resize (4, "resized string");
copy (coll.begin(), coll.end(), ostream_iterator<string>(cout,"\n"));
}
一般为双链表实现
#include <list>
提供双向跌代子，不能随机访问
插入删除操作非常快速
插入删除操作不会使跌代子失效
提供了一些移动元素的算法，比通用算法更快
c1.swap(c2)：交换两个链表的内容
c.remove(val)
c.remove_if(predictor)
c.unique() 删除重复元素
c.splice() 将一个链表中的元素切一部分到另一个链表
c.sort() 排序
c.merge() 合并两个链表
c.reverse() 倒置
例
void printLists (const list<int>& 11, const list<int>& 12) {
cout << "list1: ";
copy (l1.begin(), l1.end(), ostream_iterator<int>(cout," "));
cout << endl << "list2: ";
copy (12.begin(), 12.end(), ostream_iterator<int>(cout," "));
cout << endl << endl;
}
int main() {
list<int> list1, list2;
for (int i=0; i<6; ++i) {
list1.push_back(i);
list2.push_front(i);
}
printLists(list1, list2);
list2.splice(find(list2.begin(),list2.end(), 3), list1);
printLists(list1, list2);
list2.splice(list2.end(), list2, list2.begin());
printLists(list1, list2);
list2.sort();
list1 = list2;
list2.unique();
printLists(list1, list2);
list1.merge(list2);
printLists(list1, list2);
}
#include <stack>
namespace std {
template <class T, class Container = deque<T> >
class stack;
}
实现：
主要操作
push() 入栈
top() 取栈顶元素
pop() 出栈
例：
int main() {
stack<int> st;
st.push(l);
st.push(2);
st.push(3);
cout << st.top() << ' ';
st.pop() ;
cout << st.top() << ' ';
st.pop() ;
st.top() = 77;
st.push(4);
st.push(5);
st.pop() ;
while (!st.empty()) {
cout << st.top() << ' ';
st.pop() ;
}
cout << endl;
}
#include <queue>
namespace std {
template <class T, class Container = deque<T> >
class queue;
}
实现
主要操作：
push
pop
back
front
例
int main() {
queue<string> q;
q.push("These ");
q.push("are ");
q.push("more than ");
cout << q.front();
q.pop();
cout << q.front();
q.pop();
q.push(''four ");
q.push("words!");
q.pop();
cout << q.front();
q.pop();
cout << q.front() << endl;
q.pop();
cout << "number of elements in the queue: " << q.size() << endl;
}
按照大小顺序出队的队列
#include <queue>
namespace std {
template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type> >
class priority_queue;
}
实现：堆
push() 入队
top() 读取下一个元素
pop() 删除下一个元素
int main() {
priority_queue<float> q;
q.push(66.6);
q.push(22.2);
q.push(44.4);
cout << q.top() << ' ';
q.pop();
cout << q.top() << endl;
q.pop();
q.push(11.1);
q.push(55.5);
q.push(33.3);
q.pop();
while (!q.empty()) {
cout << q.top() << ' ';
q.pop();
}
cout << endl;
}
在这两种容器中，元素能够根据指定的排序规则自动的排序，以优化查找。两者区别是：set不允许有重复的元素，multi_set允许有重复的元素。
#include <set>
namespace std {
template <class T,
class Compare = less<T>,
class Allocator = allocator<T> >
class set;
template <class T,
class Compare = less<T>,
class Allocator = allocator<T> >
class multiset;
}
内部结构
例子：
#include <iostream>
#include <set>
using namespace std;
int main() {
typedef set<int,greater<int> > IntSet;
IntSet coll1; // empty set container
coll1.insert(4);
coll1.insert(3);
coll1.insert(5);
coll1.insert(1);
coll1.insert(6);
coll1.insert(2);
coll1.insert(5);
IntSet::iterator pos;
for (pos = coll1.begin(); pos != coll1.end(); ++pos) {
cout << *pos << ' ';
}
cout << endl;
pair<IntSet::iterator,bool> status = coll1.insert(4);
if (status.second) {
cout << "4 inserted as element "<< distance (coll1.begin(),status. first) + 1<< endl;
}else {
cout << "4 already exists" << endl;
}
set<int> coll2(coll1.begin(),
coll1.end());
copy (coll2.begin(), coll2.end(), ostream_iterator<int>(cout," "));
cout << endl;
coll2.erase (coll2.begin(), coll2.find(3));
int num;
num = coll2.erase (5);
cout << num << " element(s) removed" << endl;
copy (coll2.begin(), coll2.end(), ostream_iterator<int>(cout," "));
cout << endl;
}
存放关键字与对应值的数据结构
#include <map>
namespace std {
template <class Key, class T,
class Compare = less<Key>,
class Allocator = allocator<pair<const Key,T> > >
class map;
template <class Key, class T,
class Compare = less<Key>,
class Allocator = allocator<pair<const Key,T> > >
class multimap;
}
内部结构
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
typedef map<string,float> StringFloatMap;
StringFloatMap stocks; // create empty container
stocks["BASF"] = 369.50;
stocks["VW"] = 413.50;
stocks["Daimler"] = 819.00;
stocks["BMW"] = 834.00;
stocks["Siemens"] = 842.20;
StringFloatMap::iterator pos;
for (pos = stocks.begin(); pos != stocks.end(); ++pos) {
cout << "stock: " << pos->first << "\t" << "price: " << pos->second << endl;
}
cout << endl;
for (pos = stocks.begin(); pos != stocks.end(); ++pos) {
pos->second *= 2;
}
for (pos = stocks.begin(); pos != stocks.end(); ++pos) {
cout << "stock: " << pos->first << "\t"<< "price: " << pos->second << endl;
}
cout << endl;
stocks["Volkswagen"] = stocks["VW"];
stocks.erase("VW");
for (pos = stocks.begin(); pos != stocks.end(); ++pos) {
cout << "stock: " << pos->first << "\t"<< "price: " << pos->second << endl;
}
}
}}}