标题：stl:vector,list,deque,set,map,stack,queue

STL容器是每次C++面试容易涉及到的内容。比如最常见的问题就是各个容器的底层数据结构是什么？比如平时编程的时候是否用过STL模板库？

STL模板库为程序员提供了容器，迭代器，算法。其中，容器（container）用来管理对象的集合，迭代器（iterators）用来在对象的群集中遍历所有元素，这个群集或许是容器也或许是容器的一部分。算法用来处理群集内的元素，搜索，排序，修改，使用元素。

STL模板库提供了如下几种通用容器：

l 序列容器：vector, list, deque；

l 关联容器：set, map；

l 适配器：stack, queue, priority_queue

STL模板库还提供了两种迭代器（类似于指针）：

l iterator为读/写模式

l const_iterator为只读模式

STL提供了一些常用的算法：

l sort()

l reverse()

l find()

l copy()

模板库的底层数据结构：

容器vector的底层数据结构为数组，为连续内存，支持[]操作符，支持尾部操作。

容器list的底层数据结构为链表，为非连续内存，不支持[]操作符，支持任意位置操作

容器deque的底层数据结构为队列，支持头部和尾部操作，支持[]操作符

容器se/multiset的底层数据结构为红黑树。set的内部元素依据其值自动排序，每个元素值只能出现一次，不允许重复，multiset跟set相同，只不过它允许重复元素。

容器map/multimap的底层数据结构为红黑树，map是键值对（key-value），每一个元素都有一个键，是排序的基础，每个键只能出现一次，不允许重复，multimap跟map相同，只不过允许重复键，可用来当作字典。

stack适配器的默认的参数中容器是用deque实现的，可选择的容器有list，deque，vector，实现后进先出的值的排列（栈结构）

适配器queue可以采用deque，或者list作为底层数据结构，不能用vector（因为vector没有提供front()函数）。默认的底层数据结构为deque。

对于STL模板库，需要掌握它们的底层数据结构和它们的基本使用方法。下面就来具体分析这些容器的底层数据结构和它们的基本使用方法。

vector

容器vector的底层数据结构为数组，为连续内存，支持[]操作符，支持尾部操作。下面的代码展示了vector的用法：

int main(int argc, char *argv[])

{

vector<int> v;

int i;

for (i = 1; i <= 6; ++i)

{

v.push_back(i);

}

for (i = 0; i < v.size(); ++i)

{

cout << v[i] << " ";

}

cout << endl;

}

list

容器list的底层数据结构为链表，为非连续内存，不支持[]操作符，支持任意位置操作。下面的代码展示了list的使用方法：

int main(int argc, char *argv[])

{

list<char> list;

if ( char c = 'a'; c < 'z' ; ++c)

{

list.push_back(c);

}

list<char>::const_iterator pos;

for (pos = list.begin(); pos != list.end(); ++pos)

{

cout << *pos << " ";

}

cout << endl;

}

deque

容器deque的底层数据结构为队列，支持头部和尾部操作，支持[]操作符。下面的代码展示了deque的使用方法：

int main(int argc, char *argv[])

{

deque<float> deq;

for (int i = 1; i <= 6; ++i)

{

deq.push_front(i * 1.1);

}

for (int i = 0; i< deq.size(); ++i)

{

cout << deq[i] << " ";

}

cout << endl;

}

set/multiset

Set的使用方法如下：

int main(int argc, char *argv[])

{

set<int> set;

set<int>::iterator p;

set.insert(5);

set.insert(8);

set.insert(34);

set.insert(6);

set.insert(12);

p=set.begin();

for(p;p!=set.end();p++)

{

cout<<*p<<" ";

}

cout<<endl;

}

map/multimap

//自定义关键字比较函数

struct ltstr

{

bool operator()(const char* s1, const char* s2) const

{

return strcmp(s1, s2) < 0;

}

};

int main(int argc, char *argv[])

{

//multimap容器的声明

multimap<const char*, int, ltstr> m;

multimap<const char*, int, ltstr>::iterator it;

//multimap的初始化

m.insert(pair<const char* const, int>("a", 1));

m.insert(pair<const char* const, int>("c", 2));

m.insert(pair<const char* const, int>("b", 3));

m.insert(pair<const char* const, int>("b", 4));

m.insert(pair<const char* const, int>("a", 5));

m.insert(pair<const char* const, int>("b", 6));

//键值的统计

cout << "Number of elements with key a: " << m.count("a") << endl;

cout << "Number of elements with key b: " << m.count("b") << endl;

cout << "Number of elements with key c: " << m.count("c") << endl;

//multimap的遍历

cout << "Elements in m: " << endl;

for (it = m.begin();it != m.end();++it)

cout << " [" << (*it).first << ", " << (*it).second << "]" << endl;

}

Map/multimap，set/multiset都是关联容器。set与map不同的地方在于：set仅有key_type类型，它的value_type 也就是key_type；而且set不提供下标操作。

stack

在STL中提供了三个常用的容器适配器：stack和queue和priority_queue。适配器都是包装了vector、list、deque中某个顺序容器的包装器，也可以看作由其他容器实现的容器。适配器没有提供迭代器，也不能同时插入或删除多个元素。

其中stack适配器的默认的参数中容器是用deque实现的，可选择的容器有list，deque，vector，实现后进先出的值的排列（栈结构）。

stack的操作主要有：

l push(x) 将元素压入栈

l pop() 弹出栈顶元素（无返回值）

l top() 获取栈顶元素（不弹出）

l empty() 栈为空则返回1，不为空返回0

l size() 返回栈中元素的个数

int main(int argc, char *argv[])

{

stack<int > s;

for( int i=0; i < 10; i++ )

s.push(i);

while( !s.empty() )

{

cout << s.top() << " ";

s.pop();

}

queue/priority_queue

适配器queue可以采用deque，或者list作为底层数据结构，不能用vector（因为vector没有提供front()函数）。默认的底层数据结构为deque。它实现的是先进先出的值的排列（队列结构）。

queue的操作主要有：

l push() 将元素压入队列

l pop() 弹出首部元素

l front() 获取首部元素

l back() 获取尾部元素

l empty() 队列为空则返回1，不为空返回0

l size() 返回队列中元素的个数

应用实例：

int main(int argc, char *argv[])

{

int i;

queue<int> q;

for(i=0;i<5;i++)

q.push(i);

while(q.size())

{

cout<<q.front();

q.pop();

}

return 0;

}

下面举一个stack和queue使用非默认deque作为容器的例子：

int main(int argc, char *argv[])

{

stack<int,vector<int> > s; //stack使用了vector作为底层数据结构

s.push(1);

s.push(2);

s.push(3);

cout <<"Content are: "<<endl;

while(!s.empty())

{

cout<<s.top()<,endl;

s.pop();

}

queue<int,list<int> > q; // queue使用list作为底层数据结构

q.push(1);

q.push(2);

q.push(3);

cout <<"Content are: "<<endl;

while(!q.empty())

{

cout<<q.front()<<endl;

q.pop()

}

return 0;

}

此外，priority_queue也是一个队列，其元素按有序顺序排列，但不采用严格的先进先出的顺序，而是按照优先级，给定时刻位于队头的元素正是有最高优先级的元素。如果两个元素有相同的优先级，那么它们在队列中的顺序就遵循先进先出的语义，它默认适配的底层容器是vector，也可以使用deque，但list不能用，因为 priority_queue要求能对元素随机访问以便进行排序。

priority_queue的操作主要有：

l push(x) 将元素压入队列

l pop() 弹出首部元素（无返回值）

l top() 获取首部元素（不弹出）

l empty() 队列为空则返回1，不为空返回0

l size() 返回队列中元素的个数

int main(int argc, char *argv[])

{

priority_queue< int,vector< int> , less< int> > pq;

int a;

while(cin> > a)

{

pq.push(a);

}

while(!pq.empty())

{

cout < < pq.top() < < endl;

pq.pop();

}

return 1;

}

bitset

using namespace std;

using std::bitset;

// 使用无符号整数初始化位集

unsigned long n = 0xf0f0ff00;

bitset<32> bits1 (n); //位集从高到低：11110000111100001111111100000000

bitset<16> bits2 (n); //位集从高到低：1111111100000000

bitset<40> bits3 (n); //位集从高到低：0000000011110000111100001111111100000000

// 使用字符串初始化位集

string str = "1111111100000000";

bitset<16> strbits1 (str); //位集从高到低：1111111100000000

bitset<10> strbits2 (str); //位集从高到低：1111111100

bitset<20> strbits3 (str); //位集从高到低：00001111111100000000

set () 位集置为全1

set (n) 第n位置为1

reset () 位集置为全0

reset (n) 第n位置为0

flip () 位集取反

flip(n) N位取反

to_string 位集转换为字符串

to_ulong 位集转换为无符号整数。如果位集size大于ulong的位数，则舍弃位集高位。

count 返回位集中1的个数

size 返回位集的容量

any 如果位集中有1，则返回true

none 如果位集中没有1，则返回true

test (n) 如果第n位为1，则返回true

算法

STL为大家提供了很多高效的算法，可以在实际应用中进行运用。下面的代码向大家展示了在vector中如何使用算法：

int main(int argc, char *argv[])

{

vector<int> v;

vector<int>::itertor pos;

v.push_back(1);

v.push_back(0);

v.push_back(3);

v.push_back(7);

v.push_back(5);

v.push_back(9);

// 在指定区间内获取最小的元素迭代器

pos = min_element(v.begin(), v.end());

cout << "min" << *pos << endl;

// 在指定区间内获取最大的元素迭代器

pos = max_element(v.begin(), v.end());

cout << "max" << *pos << endl;

// 排序，默认按升序

sort(v.begin(), v.end());

// 在指定区间内，寻找为3的元素，返回迭代器

pos = find(v.begin(), v.end(), 3);

// 将指定区间内的元素反转

reverse(pos, v.end());

}

注意，STL模板库是非多线程安全的。所以，在多线程程序里，需要自己处理同步与互斥。