STL常用容器详细解析

2023-05-16

STL容器的实现原理

STL共有六大组件
1、容器。2、算法。3、迭代器。4、仿函数。6、适配器。

STL容器的实现原理

STL来管理数据十分方便,省去了我们自己构建数据结构的时间.其实,STL的实现也是基于我们常见的数据结构.

序列式容器：
vector-数组，元素不够时再重新分配内存，拷贝原来数组的元素到新分配的数组中。
list－单链表。
deque-分配中央控制器map(并非map容器)，map记录着一系列的固定长度的数组的地址.记住这个map仅仅保存的是数组的地址,真正的数据在数组中存放着.deque先从map中央的位置(因为双向队列，前后都可以插入元素)找到一个数组地址，向该数组中放入数据，数组不够时继续在map中找空闲的数组来存数据。当map也不够时重新分配内存当作新的map,把原来map中的内容copy的新map中。所以使用deque的复杂度要大于vector，尽量使用vector。

stack-基于deque。

queue-基于deque。
heap-完全二叉树，使用最大堆排序，以数组(vector)的形式存放。
priority_queue-基于heap。
slist-双向链表。

关联式容器：
set,map,multiset,multimap-基于红黑树(RB-tree)，一种加上了额外平衡条件的二叉搜索树。

hash table-散列表。将待存数据的key经过映射函数变成一个数组(一般是vector)的索引，例如：数据的key%数组的大小＝数组的索引(一般文本通过算法也可以转换为数字)，然后将数据当作此索引的数组元素。有些数据的key经过算法的转换可能是同一个数组的索引值(碰撞问题，可以用线性探测，二次探测来解决)，STL是用开链的方法来解决的，每一个数组的元素维护一个list，他把相同索引值的数据存入一个list，这样当list比较短时执行删除，插入，搜索等算法比较快。

hash_map,hash_set,hash_multiset,hash_multimap-基于hash table。

综上所述大家应该知道了什么情况下该使用哪一个STL容器更合适,可以在适当时候避免使用一些影响效率的STL容器.

这里我们不涉及容器的基本操作之类，只是要讨论一下各个容器其各自的特点STL中的常用容器包括：顺序性容器（vector、deque、list）、关联容器（map、set）、容器适配器（queue、stac）

STL是C/C++开发中一个非常重要的模板，而其中定义的各种容器也是非常方便我们大家使用。下面，我们就浅谈某些常用的容器。这里我们不涉及容器的基本操作之类，只是要讨论一下各个容器其各自的特点。STL中的常用容器包括：顺序性容器（vector、deque、list）、关联容器（map、set）、容器适配器（queue、stac）。

1、顺序性容器

（1）vector
vector是一种动态数组，在内存中具有连续的存储空间，支持快速随机访问。由于具有连续的存储空间，所以在插入和删除操作方面，效率比较慢。vector有多个构造函数，默认的构造函数是构造一个初始长度为0的内存空间，且分配的内存空间是以2的倍数动态增长的，即内存空间增长是按照20,21,22,23.....增长的，在push_back的过程中，若发现分配的内存空间不足，则重新分配一段连续的内存空间，其大小是现在连续空间的2倍，再将原先空间中的元素复制到新的空间中，性能消耗比较大，尤其是当元素是非内部数据时(非内部数据往往构造及拷贝构造函数相当复杂)。vector的另一个常见的问题就是clear操作。clear函数只是把vector的size清为零，但vector中的元素在内存中并没有消除，所以在使用vector的过程中会发现内存消耗会越来越多，导致内存泄露，现在经常用的方法是swap函数来进行解决：

vector<int> V;V.push_back(1); V.push_back(2);V.push_back(1); V.push_back(2);
vector<int>().swap(V); 或者 V.swap(vector<int>());

利用swap函数，和临时对象交换，使V对象的内存为临时对象的内存，而临时对象的内存为V对象的内存。交换以后，临时对象消失，释放内存。

-------------------

STL: 知道vector吗，一个自然数数组，要删除其中的奇数，写出代码。这个需要注意的是erase删除结点，则该结点的iterator会失效，同时erase会返回下一个有效迭代器，所以iter++只有在偶数的时候才运行。继续问到iter++和++iter的区别，回答前者会产生一个临时变量，后者的效率更高，如果前面有=的话，得到的值不一样。 vector是怎么存储的，如果让你实现vector，你怎么做，首先说了下STL里面的vector，内存如何分配的，构造函数等等。开始用数组实现vector，然后问一定要写成类似MS提供的STL里面的vector，提示说不用，写个基本框架就可以了，就直接写vector代码，然后写vector的插入操作，注意vector满时

-------------------

（2）deque
deque和vector类似，支持快速随机访问。二者最大的区别在于，vector只能在末端插入数据，而deque支持双端插入数据。deque的内存空间分布是小片的连续，小片间用链表相连，实际上内部有一个map的指针。deque空间的重新分配要比vector快，重新分配空间后，原有的元素是不需要拷贝的。

（3）list
list是一个双向链表，因此它的内存空间是可以不连续的，通过指针来进行数据的访问，这使list的随机存储变得非常低效，因此list没有提供[]操作符的重载。但list可以很好地支持任意地方的插入和删除，只需移动相应的指针即可。

（4）在实际使用时，如何选择这三个容器中哪一个，应根据你的需要而定，一般应遵循下面的原则：
　　1) 如果你需要高效的随即存取，而不在乎插入和删除的效率，使用vector
　　2) 如果你需要大量的插入和删除，而不关心随即存取，则应使用list
　　3) 如果你需要随即存取，而且关心两端数据的插入和删除，则应使用deque

2、关联容器

（1）map
map是一种关联容器，该容器用唯一的关键字来映射相应的值，即具有key-value功能。map内部自建一棵红黑树（一种自平衡二叉树），这棵树具有数据自动排序的功能，所以在map内部所有的数据都是有序的，以二叉树的形式进行组织。这是map的模板：

template < class Key, class T, class Compare= less<Key>, class Allocator=allocator< pair<const Key,T> > > class map;

从模板中我们可以看出，再构造map时，是按照一定的顺序进行的。map的插入和删除效率比其他序列的容器高，因为对关联容器来说，不需要做内存的拷贝和移动，只是指针的移动。由于map的每个数据对应红黑树上的一个节点，这个节点在不保存你的数据时，是占用16个字节的，一个父节点指针，左右孩子指针，还有一个枚举值（标示红黑色），所以map的其中的一个缺点就是比较占用内存空间。

map简介

　map是STL的一个关联容器（associative container）之一，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）的数据处理能力，由于这个特性，它完成有可能在我们处理一对一数据的时候，在编程上提供快速通道。这里说下map内部数据的组织，map内部自建一颗红黑树(一种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的。　

一个map是一个键值对序列，

即（key ,value）对。它提供基于key的快速检索能力，在一个map中key值是唯一的。map提供双向迭代器，即有从前往后的（iterator），也有从后往前的（reverse_iterator）。

map中key值是唯一

例子：如果已存在一个键值对(编号,用户名):(1001,"jack")，而我们还想插入一个键值对(1001,"mike") 运行时会报错（不是报错，准确的说是，返回插入不成功！）。而我们又的确想这样做，即一个键对应多个值，幸运的是multimap可是实现这个功能。

map中的类型定义

关联数组（associative array）是最有用的用户定义类型之一，经常内置在语言中用于文本处理等。一个关联数组通常也称为map，有时也称字典（dictionary），保存一对值。第一个值称为key、第二个称为映射值mapped-value。

// map::begin/end
#include <iostream>
#include <map>

int main ()
{
  std::map<char,int> mymap;
  std::map<char,int>::iterator it;

  mymap['z'] = 100;
  mymap['a'] = 200;
  mymap['z'] = 300;

  // show content:
  for (std::map<char,int>::iterator it=mymap.begin(); it!=mymap.end(); ++it)
    std::cout << it->first << " => " << it->second << '\n';

  return 0;
}

a => 200
z => 300

（2）set
set也是一种关联性容器，它同map一样，底层使用红黑树实现，插入删除操作时仅仅移动指针即可，不涉及内存的移动和拷贝，所以效率比较高。set中的元素都是唯一的，而且默认情况下会对元素进行升序排列。所以在set中，不能直接改变元素值，因为那样会打乱原本正确的顺序，要改变元素值必须先删除旧元素，再插入新元素。不提供直接存取元素的任何操作函数，只能通过迭代器进行间接存取。set模板原型：

template <class Key, class Compare=class<Key>, class Alloc=STL_DEFAULT_ALLOCATOR(Key) > class set;
set支持集合的交(set_intersection)、差(set_difference)、并(set_union)及对称差(set_symmetric_difference) 等一些集合上的操作。

3、容器适配器

（1）queue
queue是一个队列，实现先进先出功能，queue不是标准的STL容器，却以标准的STL容器为基础。queue是在deque的基础上封装的。之所以选择deque而不选择vector是因为deque在删除元素的时候释放空间，同时在重新申请空间的时候无需拷贝所有元素。其模板为：
template < TYPENAME _Sequence="deque<_TP" typeneam _Tp,> > class queue;

（2）stack
stack是实现先进后出的功能，和queue一样，也是内部封装了deque，这也是为啥称为容器适配器的原因吧（纯属猜测）。自己不直接维护被控序列的模板类，而是它存储的容器对象来为它实现所有的功能。stack的源代码原理和实现方式均跟queue相同。

下面是他们的区别：

我们常用到的STL容器有vector、list、deque、map、multimap、set和multiset，它们究竟有何区别，各自的优缺点是什么，为了更好的扬长避短，提高程序性能，在使用之前需要我们了解清楚。

verctor

vector类似于C语言中的数组，它维护一段连续的内存空间，具有固定的起始地址，因而能非常方便地进行随机存取，即 [] 操作符，但因为它的内存区域是连续的，所以在它中间插入或删除某个元素，需要复制并移动现有的元素。此外，当被插入的内存空间不够时，需要重新申请一块足够大的内存并进行内存拷贝。值得注意的是，vector每次扩容为原来的两倍，对小对象来说执行效率高，但如果遇到大对象，执行效率就低了。

list

list类似于C语言中的双向链表，它通过指针来进行数据的访问，因此维护的内存空间可以不连续，这也非常有利于数据的随机存取，因而它没有提供 [] 操作符重载。

deque

deque类似于C语言中的双向队列，即两端都可以插入或者删除的队列。queue支持 [] 操作符，也就是支持随机存取，而且跟vector的效率相差无几。它支持两端的操作：push_back,push_front,pop_back,pop_front等，并且在两端操作上与list的效率
也差不多。或者我们可以这么认为，deque是vector跟list的折中。

map

map类似于数据库中的１:１关系，它是一种关联容器，提供一对一(C++ primer中文版中将第一个译为键，每个键只能在map中出现一次，第二个被译为该键对应的值)的数据处理能力，这种特性了使得map类似于数据结构里的红黑二叉树。

multimap

multimap类似于数据库中的１:Ｎ关系，它是一种关联容器,提供一对多的数据处理能力。

set

set类似于数学里面的集合，不过set的集合中不包含重复的元素，这是和vector的第一个区别，第二个区别是set内部用平衡二叉树实现，便于元素查找，而vector是使用连续内存存储，便于随机存取。

multiset

multiset类似于数学里面的集合，集合中可以包含重复的元素。

小结

在实际使用过程中，到底选择这几种容器中的哪一个，应该根据遵循以下原则：

１、如果需要高效的随机存取，不在乎插入和删除的效率，使用vector；

2、如果需要大量的插入和删除元素，不关心随机存取的效率，使用list；

3、如果需要随机存取，并且关心两端数据的插入和删除效率，使用deque；

4、如果打算存储数据字典，并且要求方便地根据key找到value，一对一的情况使用map，一对多的情况使用multimap；

5、如果打算查找一个元素是否存在于某集合中，唯一存在的情况使用set，不唯一存在的情况使用multiset。

常用ＳＴＬ容器举例

一常用容器举例

1 vector：

       vector类似于动态数组，直接访问元素，从后面快速插入或者删除，示例代码如下：

[cpp] view plain copy

#include <iostream>
#include <vector>//包含vector
using namespace std;//指定命名空间

int main()
{
    cout<<"----------vector test-----------"<<endl;

    //定义一个vector
    vector <int> vect;
    vector <int> vect1(12);//12个int类型元素，每个元素的初始值均为0
    vector <int> vect2(12,9);//12个int，初试值均为9


    //使用数组初始化vector
    int a[]={0,1,2,3,4,5,6,7,8,9,0};
    //vector <数据类型> <容器名> (<开始地址>,<结束地址的下一个地址> )。执行过vt中元素为1,2,3
    vector <int> vt(a+1,a+4);
    //在尾部压入3个值
    vt.push_back(1);
    vt.push_back(2);
    vt.push_back(3);

    //定义迭代器iterator
    vector <int>::iterator iter=vt.begin();//起始地址
    vector <int>::iterator iter_end=vt.end();//结束地址,两个地址都是指针类型
    //遍历vt
    for(;iter!=iter_end;iter++)
    {
        cout<<*iter<<endl;
    }

    //弹出一个元素
    vt.pop_back();

    //以下两行重新获得起始和结尾地址
    iter=vt.begin();
    iter_end=vt.end();
    cout<<"----------executed pop_back------"<<endl;
    for(;iter!=iter_end;iter++)
    {
        cout<<*iter<<endl;
    }

    //插入元素
    cout<<"----------insert into------------"<<endl;
    //插入格式：vector.insert(<起始地址>,<插入的数量>,<元素值>);如果插入的数量为1，则第二个参数可以被省略
    vt.insert(vt.begin()+1,3,9);
    iter=vt.begin();
    iter_end=vt.end();
    for(;iter!=iter_end;iter++)
    {
        cout<<*iter<<endl;
    }

    //删除元素
    cout<<"----------erase-------------------"<<endl;
    //删除格式1为：vector.erase(<删除元素的地址>);
    //删除格式2为：vector.erase(<删除元素的起始地址>，<终止地址>);
    iter=vt.begin();
    iter_end=vt.end();
    vt.erase(iter+1,iter_end);//删除第二个到最后一个的元素
    iter_end=vt.end();
    for(;iter!=iter_end;iter++)
    {
        cout<<*iter<<endl;
    }
    return 1;
}

   2 list

list 为双向链表，可以从任何地方插入或者删除的，其示例代码如下：

[cpp] view plain copy

#include <iostream>
#include <list>
using namespace std;

void main()
{
    list<int> c1;
    c1.push_back(1);//从尾部push数据（结点）到list中
    c1.push_back(2);
    c1.push_back(3);
    c1.push_back(4);

    c1.push_front(0);//从头部push数据（结点）到list中

    c1.pop_back();//从尾部pop数据（结点）出去
    int& i = c1.back();//获取list中尾部数据（结点）
    const int& ii = c1.front();//获取list中头部数据（结点）


    cout << "The last integer of c1 is " << i << endl;
    cout << "The front interger of c1 is " << ii << endl;

    cout << "for循环读出数据举例：" << endl;
    //循环遍历数据举例
    list<int>::iterator it; //定义遍历指示器(类似于int i=0)
    for(it = c1.begin() ; it != c1.end() ;it++)
    {
        cout << *it << endl;
    }
    system("pause");
}

3 deque：

deque: 是一个double-ended queue,
1)支持随即存取，也就是[]操作符，
2)支持两端操作，push(pop)-back(front)，在两端操作上与list效率差不多

因此在实际使用时，如何选择这三个容器中哪一个，应根据你的需要而定，一般应遵循下面的原则：
1、如果你需要高效的随即存取，而不在乎插入和删除的效率，使用vector
2、如果你需要大量的插入和删除，而不关心随即存取，则应使用list
3、如果你需要随即存取，而且关心两端数据的插入和删除，则应使用deque。

示例代码如下：

[cpp] view plain copy

/*deque: 是一个double-ended queue,
    1)支持随即存取，也就是[]操作符，
    2)支持两端操作，push(pop)-back(front)，在两端操作上与list效率差不多

    因此在实际使用时，如何选择这三个容器中哪一个，应根据你的需要而定，一般应遵循下面的原则：
    1、如果你需要高效的随即存取，而不在乎插入和删除的效率，使用vector
    2、如果你需要大量的插入和删除，而不关心随即存取，则应使用list
    3、如果你需要随即存取，而且关心两端数据的插入和删除，则应使用deque。
*/

#include <iostream>
#include <deque>
using namespace std;

void printDeque(const deque<int>& d)
{
    cout<<"\n使用下标:\n";
    for (unsigned int i = 0; i < d.size(); i++)
    {
    cout<<"d["<<i<<"] = "<<d[i]<<", ";
    }


    cout<<"\n使用迭代器\n";
    deque<int>::const_iterator iter = d.begin();
    for (;iter != d.end(); iter ++)
    {
    cout<<"d["<<iter-d.begin()<<"] = "<<(*iter)<<", ";
    }
    cout<<endl;
}

void main()
{
//创建deque
deque<int> d1;                          //创建一个没有任何元素的deque对象
deque<int> d2(10);                      //创建一个具有10个元素的deque对象，每个元素值为默认
deque<double> d3(10, 5.5);              //创建一个具有10个元素的deque对象,每个元素的初始值为5.5
deque<double> d4(d3);                   //通过拷贝一个deque对象的元素值, 创建一个新的deque对象

//初始化赋值：同vector一样,使用尾部插入函数push_back()
for (int i = 1; i < 6 ; i++)
   d1.push_back(i*10);


//遍历元素: 1-下标方式 2-迭代器方式反向遍历（略）
cout<<"printDeque(d1) : "<<endl;
printDeque(d1);

//元素插入：尾部插入用push_back()，头部插入用push_front()，其它位置插入用insert(&pos, elem)
cout<<"d1.push_front(100): "<<endl;
d1.push_front(100);
printDeque(d1);
cout<<"d1.insert(d1.begin()+3, 200): "<<endl; //支持随机存取(即[]操作符)，所以begin()可以+3
d1.insert(d1.begin()+2,200);
printDeque(d1);

//元素删除尾部删除用pop_back();头部删除用pop_front();
//任意迭代位置或迭代区间上的元素删除用erase(&pos)/erase(&first, &last)；删除所有元素用clear();
cout<<"d1.pop_front(): "<<endl;
d1.pop_front();
printDeque(d1);

cout<<"d1.erase(d1.begin()+1): "<<endl;
d1.erase(d1.begin()+1); //删除第2个元素d1[1]
printDeque(d1);

cout<<"d1.erase(d1.begin(), d1.begin() + 2) = "<<endl;
d1.erase(d1.begin(), d1.begin() + 2);
printDeque(d1);

cout<<"d1.clear() :"<<endl;
d1.clear();
printDeque(d1);



}

4 容器适配器：stack

（1）可用 vector, list, deque来实现

（2）缺省情况下，用deque实现

template<classT, class Cont = deque<T> >

               class stack { …..    }；

（3）用 vector和deque实现，比用list实现性能好

（4）stack是后进先出的数据结构，

（5）只能插入、删除、访问栈顶的元素的操作:  push:     插入元素pop:       弹出元素      top: 返回栈顶元素的引用

测试代码如下：

[cpp] view plain copy

<span style="font-size:16px;">#include <iostream>
#include <Stack>
using namespace std;

void main()
{
    stack<double> s;//可以是各种数据类型；
    for( int i=0; i < 10; i++ )
        s.push(i);
    while(!s.empty())
    {
        printf("%lf\n",s.top());
        s.pop();
    }
    cout << "the size of  s: " << s.size() << endl;
}
</span>

5 deque

可以用 list和deque实现，缺省情况下用deque实现

          template<class T, class Cont = deque<T>>

           class queue { … };

FIFO先进先出的数据结构，也有push,pop,top函数，但是push发生在队尾，pop,top发生在队头，

示例代码如下：

[cpp] view plain copy

/************************************************************************/
/*

详细用法:
定义一个queue的变量     queue<Type> M
查看是否为空范例        M.empty()    是的话返回1，不是返回0;
从已有元素后面增加元素   M.push()
输出现有元素的个数      M.size()
显示第一个元素          M.front()
显示最后一个元素        M.back()
清除第一个元素          M.pop()
                                                                     */
/************************************************************************/

#include <iostream>
#include <queue>
#include <assert.h>

using namespace std;

int main()
{
    queue <int> myQ;
    int i;
    cout<< "现在 queue 是否 empty? "<< myQ.empty() << endl;

    for( i =0; i<10 ; i++)
    {
        myQ.push(i);
    }
    for( i=0; i<myQ.size(); i++)
    {
        printf("myQ.size():%d\n",myQ.size());
        cout << myQ.front()<<endl;
        myQ.pop();
    }

    system("PAUSE");

    return 0;
}

二常用算法

1 count（）and count_if()

count()在序列中统计某个值出现的次数

count_if()在序列中统计与某谓词匹配的次数

示例代码如下：

[cpp] view plain copy

#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>

using namespace std;


void CountFuc()
{
    const int VECTOR_SIZE = 8 ;

    // Define a template class vector of strings
    typedef vector<string > StringVector ;

    //Define an iterator for template class vector of strings
    typedef StringVector::iterator StringVectorIt ;

    StringVector NamesVect(VECTOR_SIZE) ;   //vector containing names

    string value("Sea") ;  // stores the value used
    // to count matching elements

    StringVectorIt start, end, it ;

    int result = 0 ;   // stores count of elements
    // that match value.

    // Initialize vector NamesVect
    NamesVect[0] = "She" ;
    NamesVect[1] = "Sells" ;
    NamesVect[2] = "Sea" ;
    NamesVect[3] = "Shells" ;
    NamesVect[4] = "by" ;
    NamesVect[5] = "the" ;
    NamesVect[6] = "Sea" ;
    NamesVect[7] = "Shore" ;

    start = NamesVect.begin() ;   // location of first
    // element of NamesVect

    end = NamesVect.end() ;       // one past the location
    // last element of NamesVect

    // print content of NamesVect
    cout << "NamesVect { " ;
    for(it = start; it != end; it++)
        cout << *it << " " ;
    cout << " }\n" << endl ;

    // Count the number of elements in the range [first, last +1)
    // that match value.
    result = count(start, end, value) ;

    // print the count of elements that match value
    cout << "Number of elements that match \"Sea\" = "
        << result << endl  ;
}


int MatchFirstChar( const string& str)
{
    string s("S") ;
    return s == str.substr(0,1) ;
}


void CountIfFuc()
{
    const int VECTOR_SIZE = 8 ;

    // Define a template class vector of strings
    typedef vector<string > StringVector ;

    //Define an iterator for template class vector of strings
    typedef StringVector::iterator StringVectorIt ;

    StringVector NamesVect(VECTOR_SIZE) ;   //vector containing names

    StringVectorIt start, end, it ;

    int result = 0 ;   // stores count of elements
    // that match value.

    // Initialize vector NamesVect
    NamesVect[0] = "She" ;
    NamesVect[1] = "Sells" ;
    NamesVect[2] = "Sea" ;
    NamesVect[3] = "Shells" ;
    NamesVect[4] = "by" ;
    NamesVect[5] = "the" ;
    NamesVect[6] = "Sea" ;
    NamesVect[7] = "Shore" ;

    start = NamesVect.begin() ;   // location of first
    // element of NamesVect

    end = NamesVect.end() ;       // one past the location
    // last element of NamesVect

    // print content of NamesVect
    cout << "NamesVect { " ;
    for(it = start; it != end; it++)
        cout << *it << " " ;
    cout << " }\n" << endl ;

    // Count the number of elements in the range [first, last +1)
    // that start with letter 'S'
    result = count_if(start, end, MatchFirstChar) ;

    // print the count of elements that start with letter 'S'
    cout << "Number of elements that start with letter \"S\" = "
        << result << endl  ;
}


void main()
{
    CountFuc();
    CountIfFuc();
}

2 find and find_if

  find       在序列中找出某个值的第一次出现的位置
find_if     在序列中找出符合某谓词的第一个元素

示例代码如下：

[cpp] view plain copy

#include <algorithm>
#include <iostream>

using namespace std;


void FindFuc()
{
    const int ARRAY_SIZE = 8 ;
    int IntArray[ARRAY_SIZE] = { 1, 2, 3, 4, 4, 5, 6, 7 } ;

    int *location ;   // stores the position of the first
    // matching element.

    int i ;

    int value = 4 ;

    // print content of IntArray
    cout << "IntArray { " ;
    for(i = 0; i < ARRAY_SIZE; i++)
        cout << IntArray[i] << ", " ;
    cout << " }" << endl ;

    // Find the first element in the range [first, last + 1)
    // that matches value.
    location = find(IntArray, IntArray + ARRAY_SIZE, value) ;

    //print the matching element if any was found
    if (location != IntArray + ARRAY_SIZE)  // matching element found
        cout << "First element that matches " << value
        << " is at location " << location - IntArray << endl;
    else                                    // no matching element was
        // found
        cout << "The sequence does not contain any elements"
        << " with value " << value << endl ;
}

int IsOdd( int n)
{
    return n % 2 ;
}


void FindIfFuc()
{
    const int ARRAY_SIZE = 8 ;
    int IntArray[ARRAY_SIZE] = { 1, 2, 3, 4, 4, 5, 6, 7 } ;
    int *location ;   // stores the position of the first
    // element that is an odd number
    int i ;

    // print content of IntArray
    cout << "IntArray { " ;
    for(i = 0; i < ARRAY_SIZE; i++)
        cout << IntArray[i] << ", " ;
    cout << " }" << endl ;

    // Find the first element in the range [first, last -1 ]
    // that is an odd number
    location = find_if(IntArray, IntArray + ARRAY_SIZE, IsOdd) ;

    //print the location of the first element
    // that is an odd number
    if (location != IntArray + ARRAY_SIZE)  // first odd element found
        cout << "First odd element " << *location
        << " is at location " << location - IntArray << endl;
    else         // no odd numbers in the range
        cout << "The sequence does not contain any odd numbers"
        << endl ;

}


void main()
{
    FindFuc();
    FindIfFuc();
}

3 for_each()
函数声明如下：
template<class InIt, class Fun>
    Fun for_each(InIt first, InIt last, Fun f);
          在区间【first，last）上的每个元素执行f操作

示例代码如下：

[cpp] view plain copy

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


// prints the cube of integer n
void PrintCube(int n)
{
    cout << n * n * n << " " ;
}

void main()
{
    const int VECTOR_SIZE = 8 ;

    // Define a template class vector of integers
    typedef vector<int > IntVector ;

    //Define an iterator for template class vector of integer
    typedef IntVector::iterator IntVectorIt ;

    IntVector Numbers(VECTOR_SIZE) ;   //vector containing numbers

    IntVectorIt start, end, it ;

    int i ;

    // Initialize vector Numbers
    for (i = 0; i < VECTOR_SIZE; i++)
        Numbers[i] = i + 1 ;

    start = Numbers.begin() ;   // location of first
    // element of Numbers

    end = Numbers.end() ;       // one past the location
    // last element of Numbers

    // print content of Numbers
    cout << "Numbers { " ;
    for(it = start; it != end; it++)
        cout << *it << " " ;
    cout << " }\n" << endl ;

    // for each element in the range [first, last)
    // print the cube of the element
    for_each(start, end, PrintCube) ;
    cout << "\n\n" ;
}
4 unique

  unique --常用来删除重复的元素，将相邻的重复的元素移到最后，返回一个iterator指向最后的重复元素，所以用它来删除重复元素时必须先排序

示例代码如下：

[cpp] view plain copy

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;


void main()
{
    string str;
    vector<string> words;
    while(cin>>str&&str!="#")
    {
        words.push_back(str);
    }

    sort(words.begin(),words.end());
    vector<string>::iterator end_unique =
        unique(words.begin(),words.end());
    words.erase(end_unique,words.end());


    vector<string> ::iterator ite=words.begin();
    for(;ite!=words.end();ite++)
    {
        cout<<*ite<<"   ";
    }

    cout<<endl;
}

5 常用排序算法

常用排列算法如下：
1 sort    对给定区间所有元素进行排序
2 stable_sort  对给定区间所有元素进行稳定排序
3 partial_sort  对给定区间所有元素部分排序
4 partial_sort_copy 对给定区间复制并排序

示例代码如下：

[cpp] view plain copy

#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <time.h>
#include <VECTOR>
using namespace std;


const int N=10;

void print(const vector<int>& v)
{
    vector<int>::const_iterator ite=v.begin();
    for(;ite!=v.end();ite++)
    {
        cout<<*ite<<"  ";
    }

    cout<<endl;
}

void Create(vector<int>& v)
{
    srand((unsigned int)time(NULL));
    v.resize(N);
    for(int i=0;i<N;i++)
        v[i]=rand()%100;
}


// bool cmp(int arg1,int arg2)
// {
//  return arg1<arg2;
// }


void sort1(vector<int> v)
{
    sort(v.begin(),v.end());
    cout<<"after sort funtion:\n";
    print(v);
}

void sort2(vector<int> v)
{
    stable_sort(v.begin(),v.end());
    cout<<"after stable_sort funtion:\n";
    print(v);
}

void sort3(vector<int> v)
{
    partial_sort(v.begin(),v.begin()+v.size()/2,v.end()); //对前半部分排序
    cout<<"after partial_sort funtion:\n";
    print(v);
}

void sort4(vector<int> v)
{
    vector<int> temp;
    temp.resize(v.size());
    partial_sort_copy(v.begin(),v.end(),temp.begin(),temp.end()); //复制并排序
    cout<<"after partial_sort_copy funtion:\n";
    print(temp);
}


void main()
{
    vector<int> v;

    Create(v);
    cout<<"before sort:\n";
    print(v);

    sort1(v);
    sort2(v);
    sort3(v);
    sort4(v);
}

6 生成全排列

next_permutation（）的原型如下：

template<class BidirectionalIterator>
bool next_permutation(
BidirectionalIterator _First,
BidirectionalIterator _Last
);
template<class BidirectionalIterator, class BinaryPredicate>
bool next_permutation(
BidirectionalIterator _First,
BidirectionalIterator _Last,
BinaryPredicate _Comp
);
两个重载函数,第二个带谓词参数_Comp,其中只带两个参数的版本,默认谓词函数为"小于".，返回值为bool类型

示例代码如下：

[cpp] view plain copy

#include <iostream>
#include <algorithm>
using namespace std;

void permutation(char* str,int length)
{
    sort(str,str+length);
    do
    {
        for(int i=0;i<length;i++)
            cout<<str[i];
        cout<<endl;
    }while(next_permutation(str,str+length));

}
int main(void)
{
    char str[] = "acb";
    cout<<str<<"所有全排列的结果为："<<endl;
    permutation(str,3);
    system("pause");
    return 0;
}

（注：以上所有代码在vc6.0上测试通过）

您可能感兴趣的文章:

stl容器set,map,vector之erase用法与返回值详细解析
关于STL中的map容器的一些总结
浅析stl序列容器(map和set)的仿函数排序
STL各个容器性能详细比较
关于STL中vector容器的一些总结

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)