标题: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的内部元素依据其值自动排序,每个元素值只能出现一次,不允许重复,multisetset相同,只不过它允许重复元素。

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

stack适配器的默认的参数中容器是用deque实现的,可选择的容器有listdequevector,实现后进先出的值的排列(栈结构)

适配器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

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

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

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

 

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

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/multimapset/multiset都是关联容器。setmap不同的地方在于:set仅有key_type类型,它的value_type 也就是key_type;而且set不提供下标操作。

stack

       STL中提供了三个常用的容器适配器:stackqueuepriority_queue。适配器都是包装了vectorlistdeque中某个顺序容器的包装器,也可以看作由其他容器实现的容器。适配器没有提供迭代器,也不能同时插入或删除多个元素。

其中stack适配器的默认的参数中容器是用deque实现的,可选择的容器有listdequevector,实现后进先出的值的排列(栈结构)。

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;

}

 

下面举一个stackqueue使用非默认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模板库是非多线程安全的。所以,在多线程程序里,需要自己处理同步与互斥。




看文字不过瘾?点击我,进入腾讯课堂视频教学
麦洛科菲长期致力于IT安全技术的推广与普及,我们更专业!我们的学员已经广泛就职于BAT360等各大IT互联网公司。详情请参考我们的 业界反馈 《周哥教IT.C语言深学活用》视频

我们的微信公众号,敬请关注