c++复习:STL之容器

时间:2022-11-29 16:55:14

1 STL的string

1 String概念

  • string是STL的字符串类型,通常用来表示字符串。而在使用string之前,字符串通常是用char*表示的。string与char*都可以用来表示字符串,那么二者有什么区别呢。

string和char*的比较

  • string是一个类, char*是一个指向字符的指针。

string封装了char*,管理这个字符串,是一个char*型的容器。

  • string不用考虑内存释放和越界。

string管理char*所分配的内存。每一次string的复制,取值都由string类负责维护,不用担心复制越界和取值越界等。

  • string提供了一系列的字符串操作函数(这个等下会详讲)

    查找find,拷贝copy,删除erase,替换replace,插入insert

2string的构造函数

  • 默认构造函数:

string();     //构造一个空的字符串string s1。

  • 拷贝构造函数:

string(const string &str);    //构造一个与str一样的string。如string s1(s2)。

  • 带参数的构造函数

        string(const char *s); //用字符串s初始化

        string(int n,char c); //用n个字符c初始化

3string的存取字符操作

  • string类的字符操作:

    const char &operator[] (int n) const;

    const char &at(int n) const;

    char &operator[] (int n);

    char &at(int n);

  • operator[]和at()均返回当前字符串中第n个字符,但二者是有区别的。

主要区别在于at()在越界时会抛出异常,[]在刚好越界时会返回(char)0,再继续越界时,编译器直接出错。如果你的程序希望可以通过try,catch捕获异常,建议采用at()。

4从string取得const char*的操作

  • const char *c_str() const; //返回一个以'\0'结尾的字符串的首地址

    //但是要用到强制类型转化,不然直接给你输出字符串而不是地址.

    列:cout<<"s2地址:"<<static_cast<const void *>(s2.c_str())<<endl;

    c_str是一个标准函数,不是自定义函数;

5把string拷贝到char*指向的内存空间的操作

  • int copy(char *s, int n, int pos=0) const;

把当前串中以pos开始的n个字符拷贝到以s为起始位置的字符数组中,返回实际拷贝的数目。注意要保证s所指向的空间足够大以容纳当前字符串,不然会越界。

6string的长度

int length() const; //返回当前字符串的长度。长度不包括字符串结尾的'\0'。

bool empty() const; //当前字符串是否为空

7string的赋值

string &operator=(const string &s);//把字符串s赋给当前的字符串

string &assign(const char *s); //把字符串s赋给当前的字符串

string &assign(const char *s, int n); //把字符串s的前n个字符赋给当前的字符串

string &assign(const string &s); //把字符串s赋给当前字符串

string &assign(int n,char c); //用n个字符c赋给当前字符串

string &assign(const string &s,int start, int n); //把字符串s中从start开始的n个字符赋给当前字符串

8string字符串连接

string &operator+=(const string &s); //把字符串s连接到当前字符串结尾

string &operator+=(const char *s);//把字符串s连接到当前字符串结尾

string &append(const char *s); //把字符串s连接到当前字符串结尾

string &append(const char *s,int n); //把字符串s的前n个字符连接到当前字符串结尾

string &append(const string &s); //同operator+=()

string &append(const string &s,int pos, int n);//把字符串s中从pos开始的n个字符连接到当前字符串结尾

string &append(int n, char c); //在当前字符串结尾添加n个字符c

9string的比较

int compare(const string &s) const; //与字符串s比较

int compare(const char *s) const; //与字符串s比较

compare函数在>时返回 1,<时返回 -1,==时返回 0。比较区分大小写,比较时参考字典顺序,排越前面的越小。大写的A比小写的a小。

10string的子串

string substr(int pos=0, int n=npos) const; //返回由pos开始的n个字符组成的子字符串

11string的查找 和 替换

查找

int find(char c,int pos=0) const; //从pos开始查找字符c在当前字符串的位置

int find(const char *s, int pos=0) const; //从pos开始查找字符串s在当前字符串的位置

int find(const string &s, int pos=0) const; //从pos开始查找字符串s在当前字符串中的位置

find函数如果查找不到,就返回-1

int rfind(char c, int pos=npos) const; //从pos开始从后向前查找字符c在当前字符串中的位置

int rfind(const char *s, int pos=npos) const;

int rfind(const string &s, int pos=npos) const;

//rfind是反向查找的意思,如果查找不到, 返回-1

 

替换

string &replace(int pos, int n, const char *s);//删除从pos开始的n个字符,然后在pos处插入串s

string &replace(int pos, int n, const string &s); //删除从pos开始的n个字符,然后在pos处插入串s

//是先删除,在插入;不计算结束符'\0'。

void swap(string &s2); //交换当前字符串与s2的值,注意,此函数不支持链式编程,因为它没有返回值

 

//4 字符串的查找和替换

void main()

{

    string s1 = "wbm hello wbm 111 wbm 222 wbm 333";

    size_t index = s1.find("wbm", 0);

    cout << "index: " << index;

 

 

    //求itcast出现的次数

    size_t offindex = s1.find("wbm", 0);

    while (offindex != string::npos)

    {

        cout << "在下标index: " << offindex << "找到wbm\n";

        offindex = offindex + 1;

        offindex = s1.find("wbm", offindex);

    }

 

    //替换

    string s2 = "wbm hello wbm 111 wbm 222 wbm 333";

    sreplace(0, 3, "wbm");

    cout << s2 << endl;

 

    //求itcast出现的次数

    offindex = sfind("wbm", 0);

    while (offindex != string::npos)

    {

        cout << "在下标index: " << offindex << "找到wbm\n";

        sreplace(offindex, 3, "WBM");

        offindex = offindex + 1;

        offindex = s1.find("wbm", offindex);

    }

    cout << "替换以后的s2:" << s2 << endl;

}

12String的区间删除和插入

string &insert(int pos, const char *s);

string &insert(int pos, const string &s);

//前两个函数在pos位置插入字符串s

string &insert(int pos, int n, char c); //在pos位置 插入n个字符c

 

string &erase(int pos=0, int n=npos); //删除pos开始的n个字符,返回修改后的字符串

 

13string算法相关

void main()

{

    string s2 = "AAAbbb";

    transform(s2.begin(), s2.end(), s2.begin(), toupper);

//将输入的操作作用与指定范围内的每个元素,并产生一个新的序列。重载版本将操作作用在一对元素上,另外一个元素来自输入的另外一个序列。结果输出到指定容器 (头文件:algorithm)

//另外,需要指出的是:在Linux下面,toupper和tolower是宏定义实现,而不是函数实现。所以这个在Linux下面会出错。

 

    cout << s2 << endl;

 

    string s3 = "AAAbbb";

    transform(s3.begin(), s3.end(), s3.begin(), tolower);

    cout << s3 << endl;

}

Linux下的版本:

char to_toupper(char c)

{

    return toupper(c);

}

char to_tolower(char c)

{

    return totolower(c);

}

void main()

{

    string s2 = "AAAbbb";

    transform(s2.begin(), s2.end(), s2.begin(), to_toupper);

 

    cout << s2 << endl;

 

    string s3 = "AAAbbb";

    transform(s3.begin(), s3.end(), s3.begin(), to_tolower);

    cout << s3 << endl;

}

 

2 Vector容器

1Vector容器简介

  • vector是将元素置于一个动态数组中加以管理的容器。
  • vector可以随机存取元素(支持索引值直接存取, 用[]操作符或at()方法,这个等下会详讲)。

vector尾部添加或移除元素非常快速。但是在中部或头部插入元素或移除元素比较费时

2vector对象的默认构造

vector采用模板类实现,vector对象的默认构造形式

vector<T> vecT;

 

vector<int> vecInt;     //一个存放int的vector容器。

vector<float> vecFloat;     //一个存放float的vector容器。

vector<string> vecString;     //一个存放string的vector容器。

...                 //尖括号内还可以设置指针类型或自定义类型。

Class CA{};

vector<CA*> vecpCA;         //用于存放CA对象的指针的vector容器。

vector<CA> vecCA;     //用于存放CA对象的vector容器。由于容器元素的存放是按值复制的方式进行的,所以此时CA必须提供CA的拷贝构造函数,以保证CA对象间拷贝正常。

3vector对象的带参数构造

理论知识

  • vector(beg,end); //构造函数将[beg, end)区间中的元素拷贝给本身。注意该区间是左闭右开的区间。
  • vector(n,elem); //构造函数将n个elem拷贝给本身。
  • vector(const vector &vec); //拷贝构造函数

 

int iArray[] = {0,1,2,3,4};

vector<int> vecIntA( iArray, iArray+5 );

 

vector<int> vecIntB ( vecIntA.begin() , vecIntA.end() ); //用构造函数初始化容器vecIntB

vector<int> vecIntB ( vecIntA.begin() , vecIntA.begin()+3 );

vector<int> vecIntC(3,9); //此代码运行后,容器vecIntB就存放3个元素,每个元素的值是9。

 

vector<int> vecIntD(vecIntA);

 

4vector的赋值

理论知识

  • vector.assign(beg,end); //将[beg, end)区间中的数据拷贝赋值给本身。注意该区间是左闭右开的区间。
  • vector.assign(n,elem); //将n个elem拷贝赋值给本身。
  • vector& operator=(const vector &vec);    //重载等号操作符
  • vector.swap(vec); // 将vec与本身的元素互换。
  • 使用[]和at()可以单个赋值;

 

vector<int> vecIntA, vecIntB, vecIntC, vecIntD;

int iArray[] = {0,1,2,3,4};

vecIntA.assign(iArray,iArray+5);

 

vecIntB.assign( vecIntA.begin(), vecIntA.end() ); //用其它容器的迭代器作参数。

 

vecIntC.assign(3,9);

 

vector<int> vecIntD;

vecIntD = vecIntA;

 

vecIntA.swap(vecIntD);

5vector的大小

理论知识

  • vector.size();     //返回容器中元素的个数
  • vector.empty();     //判断容器是否为空
  • vector.resize(num); //重新指定容器的长度为num,若容器变长,则以默认值填充新位置。如果容器变短,则末尾超出容器长度的元素被删除。
  • vector.resize(num, elem); //重新指定容器的长度为num,若容器变长,则以elem值填充新位置。如果容器变短,则末尾超出容器长度的元素被删除。

    //是拓展到num那么长,而不是重新拓展(即删除在拓展)。

 

例如 vecInt是vector<int> 声明的容器,现已包含1,2,3元素。

int iSize = vecInt.size();        //iSize == 3;

bool bEmpty = vecInt.empty();    // bEmpty == false;

执行vecInt.resize(5); //此时里面包含1,2,3,0,0元素。

再执行vecInt.resize(8,3); //此时里面包含1,2,3,0,0,3,3,3元素。

再执行vecInt.resize(2); //此时里面包含1,2元素。

 

6vector末尾的添加移除操作

vector<int> vecInt;

vecInt.push_back(1); //在容器尾部加入一个元素

vecInt.push_back(3);

vecInt.push_back(5);

vecInt.push_back(7);

vecInt.push_back(9);

vecInt.pop_back(); //移除容器中最后一个元素

vecInt.pop_back();

//{5 ,7 ,9}

7vector的数据存取

理论知识

vec.at(idx);     //返回索引idx所指的数据,如果idx越界,抛出out_of_range异常。

vec[idx];     //返回索引idx所指的数据,越界时,运行直接报错

 

vector<int> vecInt; //假设包含1 ,3 ,5 ,7 ,9

vecInt.at(2) == vecInt[2]    ;        //5

vecInt.at(2) = 8; 或 vecInt[2] = 8;

vecInt 就包含 1, 3, 8, 7, 9值

 

int iF = vector.front();    //iF==1

int iB = vector.back();    //iB==9

vector.front() = 11;    //vecInt包含{11,3,8,7,9}

vector.back() = 19;    //vecInt包含{11,3,8,7,19}

8迭代器基本原理

  • 迭代器是一个"可遍历STL容器内全部或部分元素"的对象。
  • 迭代器指出容器中的一个特定位置。
  • 迭代器就如同一个指针。
  • 迭代器提供对一个容器中的对象的访问方法,并且可以定义了容器中对象的范围。
  • 这里大概介绍一下迭代器的类别。

输入迭代器:也有叫法称之为"只读迭代器",它从容器中读取元素,只能一次读入一个元素向前移动,只支持一遍算法,同一个输入迭代器不能两遍遍历一个序列。

输出迭代器:也有叫法称之为"只写迭代器",它往容器中写入元素,只能一次写入一个元素向前移动,只支持一遍算法,同一个输出迭代器不能两遍遍历一个序列。

正向迭代器:组合输入迭代器和输出迭代器的功能,还可以多次解析一个迭代器指定的位置,可以对一个值进行多次读/写。

双向迭代器:组合正向迭代器的功能,还可以通过--操作符向后移动位置。

随机访问迭代器:组合双向迭代器的功能,还可以向前向后跳过任意个位置,可以直接访问容器中任何位置的元素。

  • 目前本系列教程所用到的容器,都支持双向迭代器或随机访问迭代器,下面将会详细介绍这两个类别的迭代器。

9双向迭代器与随机访问迭代器

双向迭代器支持的操作:

it++, ++it, it--, --it,*it, itA = itB,

itA == itB,itA != itB

其中list,set,multiset,map,multimap支持双向迭代器。

随机访问迭代器支持的操作:

在双向迭代器的操作基础上添加

it+=i, it-=i, it+i(或it=it+i),it[i],

itA<itB, itA<=itB, itA>itB, itA>=itB 的功能。

其中vector,deque支持随机访问迭代器。

10vector与迭代器的配合使用

c++复习:STL之容器

vector<int> vecInt; //假设包含1,3,5,7,9元素

vector<int>::iterator it;        //声明容器vector<int>的迭代器。

it = vecInt.begin(); // *it == 1

++it;                //或者it++; *it == 3 ,前++的效率比后++的效率高,前++返回引用,后++返回值。

it += 2;        //*it == 7

it = it+1;        //*it == 9

++it;                // it == vecInt.end(); 此时不能再执行*it,会出错!

 

 

正向遍历:

for(vector<int>::iterator it=vecInt.begin(); it!=vecInt.end(); ++it)

{

int iItem = *it;

cout << iItem; //或直接使用 cout << *it;

}

这样子便打印出1 3 5 7 9

 

逆向遍历:

for(vector<int>::reverse_iterator rit=vecInt.rbegin(); rit!=vecInt.rend(); ++rit) //注意,小括号内仍是++rit

{

        int iItem = *rit;

cout << iItem;    //或直接使用cout << *rit;

}

此时将打印出9,7,5,3,1

注意,这里迭代器的声明采用vector<int>::reverse_iterator,而非vector<int>::iterator。

 

 

迭代器还有其它两种声明方法:

vector<int>::const_iterator 与 vector<int>::const_reverse_iterator

 

以上两种分别是vector<int>::iterator 与vector<int>::reverse_iterator 的只读形式,使用这两种迭代器时,不会修改到容器中的值。

备注:不过容器中的insert和erase方法仅接受这四种类型中的iterator,其它三种不支持。《Effective STL》建议我们尽量使用iterator取代const_iterator、reverse_iterator和const_reverse_iterator。

 

当我使用函数模板来使用迭代器的时候:比如这样:↓

template <typename T>

void out(vector<T> &cer )

{

for(typename vector<T>::iterator it=cer.begin();it!=cer.end();++it )

cout<<*it<<endl;

}

看到那个突出的地方了嘛?那是必须的(我在Linux下面测试的,vs下我就不清楚了。)另外,只读迭代器应该用const_iterator,避免被意外的改变;

 

11vector的插入

理论知识

  • vector.insert(pos,elem); //在pos位置插入一个elem元素的拷贝,返回新数据的位置。
  • vector.insert(pos,n,elem); //在pos位置插入n个elem数据,无返回值。
  • vector.insert(pos,beg,end); //在pos位置插入[beg,end)区间的数据,无返回值

简单案例

vector<int> vecA;

    vector<int> vecB;

 

    vecA.push_back(1);

    vecA.push_back(3);

    vecA.push_back(5);

    vecA.push_back(7);

    vecA.push_back(9);

 

    vecB.push_back(2);

    vecB.push_back(4);

    vecB.push_back(6);

    vecB.push_back(8);

    

    vecA.insert(vecA.begin(), 11);        //{11, 1, 3, 5, 7, 9}

    vecA.insert(vecA.begin()+1,2,33);        //{11,33,33,1,3,5,7,9}

    vecA.insert(vecA.begin() , vecB.begin() , vecB.end() );    //{2,4,6,8,11,33,33,1,3,5,7,9}

12vector的删除

理论知识

  • vector.clear();    //移除容器的所有数据
  • vec.erase(beg,end); //删除[beg,end)区间的数据,返回下一个数据的位置。
  • vec.erase(pos); //删除pos位置的数据,返回下一个数据的位置。

简单案例:

删除区间内的元素

vecInt是用vector<int>声明的容器,现已包含按顺序的1,3,5,6,9元素。

vector<int>::iterator itBegin=vecInt.begin()+1;

vector<int>::iterator itEnd=vecInt.begin()+2;

vecInt.erase(itBegin,itEnd);

//此时容器vecInt包含按顺序的1,6,9三个元素。

 

假设 vecInt 包含1,3,2,3,3,3,4,3,5,3,删除容器中等于3的元素

for(vector<int>::iterator it=vecInt.being(); it!=vecInt.end(); ) //小括号里不需写 ++it

{

if(*it == 3)

{

it = vecInt.erase(it); //以迭代器为参数,删除元素3,并把数据删除后的下一个元素位置返回给迭代器。

//此时,不执行 ++it;

}

else

{

++it;

}

}

 

//删除vecInt的所有元素

vecInt.clear();            //容器为空

 

13vector小结

这一讲,主要讲解如下要点:

容器的简介,容器的分类,各个容器的数据结构

        vector,deque,list,set,multiset,map,multimap

容器vector的具体用法(包括迭代器的具体用法)。

vertor简介,vector使用之前的准备,vector对象的默认构造,vector末尾的添加移除操作,vector的数据存取,迭代器的简介,双向迭代器与随机访问迭代器

vector与迭代器的配合使用,vector对象的带参数构造,vector的赋值,vector的大小,vector的插入,vector的删除。

3 Deque容器

Deque简介

  • deque是"double-ended queue"的缩写,和vector一样都是STL的容器,deque是双端数组,而vector是单端的。
  • deque在接口上和vector非常相似,在许多操作的地方可以直接替换。
  • deque可以随机存取元素(支持索引值直接存取, 用[]操作符或at()方法,这个等下会详讲)。
  • deque头部和尾部添加或移除元素都非常快速。但是在中部安插元素或移除元素比较费时。
  • #include <deque>

deque对象的默认构造

deque采用模板类实现,deque对象的默认构造形式:deque<T> deqT;

deque <int> deqInt; //一个存放int的deque容器。

deque <float> deq Float; //一个存放float的deque容器。

deque <string> deq String; //一个存放string的deque容器。

...                

//尖括号内还可以设置指针类型或自定义类型。

 

deque末尾的添加移除操作

理论知识:

  • deque.push_back(elem);    //在容器尾部添加一个数据
  • deque.push_front(elem);    //在容器头部插入一个数据
  • deque.pop_back();         //删除容器最后一个数据
  • deque.pop_front();        //删除容器第一个数据

 

deque<int> deqInt;

    deqInt.push_back(1);

    deqInt.push_back(3);

    deqInt.push_back(5);

    deqInt.push_back(7);

    deqInt.push_back(9);

    deqInt.pop_front();

    deqInt.pop_front();

    deqInt.push_front(11);

    deqInt.push_front(13);

    deqInt.pop_back();

    deqInt.pop_back();

//deqInt { 13,11,5}

 

deque的数据存取

理论知识:

  • deque.at(idx); //返回索引idx所指的数据,如果idx越界,抛出out_of_range。
  • deque[idx]; //返回索引idx所指的数据,如果idx越界,不抛出异常,直接出错。
  • deque.front(); //返回第一个数据。
  • deque.back(); //返回最后一个数据

        deque<int> deqInt;

        deqInt.push_back(1);

        deqInt.push_back(3);

        deqInt.push_back(5);

        deqInt.push_back(7);

        deqInt.push_back(9);

 

        int iA = deqInt.at(0);        //1

        int iB = deqInt[1];            //3

        deqInt.at(0) = 99;            //99

        deqInt[1] = 88;            //88

 

        int iFront = deqInt.front();    //99

        int iBack = deqInt.back();    //9

        deqInt.front() = 77;            //77

        deqInt.back() = 66;            //66

deque与迭代器

理论知识

  • deque.begin(); //返回容器中第一个元素的迭代器。
  • deque.end(); //返回容器中最后一个元素之后的迭代器。
  • deque.rbegin(); //返回容器中倒数第一个元素的迭代器。
  • deque.rend(); //返回容器中倒数最后一个元素之后的迭代器。

 

deque<int> deqInt;

        deqInt.push_back(1);

        deqInt.push_back(3);

        deqInt.push_back(5);

        deqInt.push_back(7);

        deqInt.push_back(9);

 

        for (deque<int>::iterator it=deqInt.begin(); it!=deqInt.end(); ++it)

        {

            cout << *it;

            cout << "";

        }

    // 1 3 5 7 9

 

        for (deque<int>::reverse_iterator rit=deqInt.rbegin(); rit!=deqInt.rend(); ++rit)

        {

            cout << *rit;

            cout << "";

        }

    //9 7 5 3 1

deque对象的带参数构造

理论知识

  • deque(beg,end); //构造函数将[beg, end)区间中的元素拷贝给本身。注意该区间是左闭右开的区间。
  • deque(n,elem); //构造函数将n个elem拷贝给本身。
  • deque(const deque &deq); //拷贝构造函数。

 

deque<int> deqIntA;

        deqIntA.push_back(1);

        deqIntA.push_back(3);

        deqIntA.push_back(5);

        deqIntA.push_back(7);

        deqIntA.push_back(9);

 

        deque<int> deqIntB(deqIntA.begin(),deqIntA.end());        //1 3 5 7 9

        deque<int> deqIntC(5,8);                            //8 8 8 8 8

        deque<int> deqIntD(deqIntA);                        //1 3 5 7 9

deque的赋值

理论知识

  • deque.assign(beg,end); //将[beg, end)区间中的数据拷贝赋值给本身。注意该区间是左闭右开的区间。
  • deque.assign(n,elem); //将n个elem拷贝赋值给本身。
  • deque& operator=(const deque &deq);    //重载等号操作符
  • deque.swap(deq); // 将vec与本身的元素互换

 

deque<int> deqIntA,deqIntB,deqIntC,deqIntD;

        deqIntA.push_back(1);

        deqIntA.push_back(3);

        deqIntA.push_back(5);

        deqIntA.push_back(7);

        deqIntA.push_back(9);

 

        deqIntB.assign(deqIntA.begin(),deqIntA.end());    // 1 3 5 7 9

        

        deqIntC.assign(5,8);                        //8 8 8 8 8

 

        deqIntD = deqIntA;                            //1 3 5 7 9

 

        deqIntC.swap(deqIntD);                        //互换

deque的大小

理论知识

  • deque.size();     //返回容器中元素的个数
  • deque.empty();     //判断容器是否为空
  • deque.resize(num); //重新指定容器的长度为num,若容器变长,则以默认值填充新位置。如果容器变短,则末尾超出容器长度的元素被删除。
  • deque.resize(num, elem); //重新指定容器的长度为num,若容器变长,则以elem值填充新位置。如果容器变短,则末尾超出容器长度的元素被删除。

 

        deque<int> deqIntA;

        deqIntA.push_back(1);

        deqIntA.push_back(3);

        deqIntA.push_back(5);

 

        int iSize = deqIntA.size(); //3

 

        if (!deqIntA.empty())

        {

            deqIntA.resize(5);        //1 3 5 0 0

            deqIntA.resize(7,1);    //1 3 5 0 0 1 1

            deqIntA.resize(2);        //1 3

        }

deque的插入

理论知识

  • deque.insert(pos,elem); //在pos位置插入一个elem元素的拷贝,返回新数据的位置。
  • deque.insert(pos,n,elem); //在pos位置插入n个elem数据,无返回值。
  • deque.insert(pos,beg,end); //在pos位置插入[beg,end)区间的数据,无返回值。

 

deque<int> deqA;

    deque<int> deqB;

 

    deqA.push_back(1);

    deqA.push_back(3);

    deqA.push_back(5);

    deqA.push_back(7);

    deqA.push_back(9);

 

    deqB.push_back(2);

    deqB.push_back(4);

    deqB.push_back(6);

    deqB.push_back(8);

    

    deqA.insert(deqA.begin(), 11);        //{11, 1, 3, 5, 7, 9}

    deqA.insert(deqA.begin()+1,2,33);        //{11,33,33,1,3,5,7,9}

    deqA.insert(deqA.begin() , deqB.begin() , deqB.end() );    //{2,4,6,8,11,33,33,1,3,5,7,9}

deque的删除

理论知识

  • deque.clear();    //移除容器的所有数据
  • deque.erase(beg,end); //删除[beg,end)区间的数据,返回下一个数据的位置。
  • deque.erase(pos); //删除pos位置的数据,返回下一个数据的位置。

 

删除区间内的元素

deqInt是用deque<int>声明的容器,现已包含按顺序的1,3,5,6,9元素。

deque<int>::iterator itBegin=deqInt.begin()+1;

deque<int>::iterator itEnd=deqInt.begin()+3;

deqInt.erase(itBegin,itEnd);

//此时容器deqInt包含按顺序的1,6,9三个元素。

 

 

 

假设 deqInt 包含1,3,2,3,3,3,4,3,5,3,删除容器中等于3的元素

for(deque<int>::iterator it=deqInt.being(); it!=deqInt.end(); ) //小括号里不需写 ++it

{

if(*it == 3)

{

it = deqInt.erase(it); //以迭代器为参数,删除元素3,并把数据删除后的下一个元素位置返回给迭代器。

//此时,不执行 ++it;

}

else

{

++it;

}

}

 

//删除deqInt的所有元素

deqInt.clear();            //容器为空

 

4 stack容器

Stack简介

  • stack是堆栈容器,是一种"先进后出"的容器。
  • stack是简单地装饰deque容器而成为另外的一种容器。
  • #include <stack>

stack对象的默认构造

stack采用模板类实现, stack对象的默认构造形式: stack <T> stkT;

stack <int> stkInt; //一个存放int的stack容器。

stack <float> stkFloat; //一个存放float的stack容器。

stack <string> stkString; //一个存放string的stack容器。

...                

//尖括号内还可以设置指针类型或自定义类型。

stack的push()与pop()方法

stack.push(elem); //往栈头添加元素

stack.pop(); //从栈头移除第一个元素

 

stack<int> stkInt;     

stkInt.push(1);stkInt.push(3);stkInt.pop();

stkInt.push(5);stkInt.push(7);

stkInt.push(9);stkInt.pop();     

stkInt.pop();

此时stkInt存放的元素是1,5

stack对象的拷贝构造与赋值

stack(const stack &stk);         //拷贝构造函数

stack& operator=(const stack &stk);    //重载等号操作符

 

        stack<int> stkIntA;

        stkIntA.push(1);

        stkIntA.push(3);

        stkIntA.push(5);

        stkIntA.push(7);

        stkIntA.push(9);

 

        stack<int> stkIntB(stkIntA);        //拷贝构造

        stack<int> stkIntC;

        stkIntC = stkIntA;                //赋值

stack的数据存取

  • stack.top();     //返回最后一个压入栈元素

        stack<int> stkIntA;

        stkIntA.push(1);

        stkIntA.push(3);

        stkIntA.push(5);

        stkIntA.push(7);

        stkIntA.push(9);

 

        int iTop = stkIntA.top();        //9

        stkIntA.top() = 19;            //19

stack的大小

  • stack.empty(); //判断堆栈是否为空
  • stack.size();      //返回堆栈的大小

 

        stack<int> stkIntA;

        stkIntA.push(1);

        stkIntA.push(3);

        stkIntA.push(5);

        stkIntA.push(7);

        stkIntA.push(9);

 

        if (!stkIntA.empty())

        {

            int iSize = stkIntA.size();        //5

        }

 

5 Queue容器

Queue简介

  • queue是队列容器,是一种"先进先出"的容器。
  • queue是简单地装饰deque容器而成为另外的一种容器。
  • #include <queue>

queue对象的默认构造

queue采用模板类实现,queue对象的默认构造形式:queue<T> queT; 如:

queue<int> queInt; //一个存放int的queue容器。

queue<float> queFloat; //一个存放float的queue容器。

queue<string> queString; //一个存放string的queue容器。

...                

//尖括号内还可以设置指针类型或自定义类型。

 

queue的push()与pop()方法

queue.push(elem); //往队尾添加元素

queue.pop(); //从队头移除第一个元素

 

queue<int> queInt;

queInt.push(1);queInt.push(3);

queInt.push(5);queInt.push(7);

queInt.push(9);queInt.pop();

queInt.pop();

此时queInt存放的元素是5,7,9

queue对象的拷贝构造与赋值

queue(const queue &que);         //拷贝构造函数

queue& operator=(const queue &que);    //重载等号操作符

 

        queue<int> queIntA;

        queIntA.push(1);

        queIntA.push(3);

        queIntA.push(5);

        queIntA.push(7);

        queIntA.push(9);

 

        queue<int> queIntB(queIntA);    //拷贝构造

        queue<int> queIntC;

        queIntC = queIntA;                //赋值

queue的数据存取

  • queue.back(); //返回最后一个元素
  • queue.front(); //返回第一个元素

 

        queue<int> queIntA;

        queIntA.push(1);

        queIntA.push(3);

        queIntA.push(5);

        queIntA.push(7);

        queIntA.push(9);

 

        int iFront = queIntA.front();        //1

        int iBack = queIntA.back();        //9

 

        queIntA.front() = 11;            //11

        queIntA.back() = 19;            //19

queue的大小

  • queue.empty(); //判断队列是否为空
  • queue.size();      //返回队列的大小

        queue<int> queIntA;     

        queIntA.push(1);     

        queIntA.push(3);         

        queIntA.push(5);        

        queIntA.push(7);        

        queIntA.push(9);        

 

        if (!queIntA.empty())

        {

            int iSize = queIntA.size();        //5

        }

6 List容器

List简介

  • list是一个双向链表容器,可高效地进行插入删除元素。
  • list不可以随机存取元素,所以不支持at.(pos)函数与[]操作符。It++(ok) it+5(err)
  • #include <list>

 

list对象的默认构造

list采用采用模板类实现,对象的默认构造形式:list<T> lstT; 如:

list<int> lstInt; //定义一个存放int的list容器。

list<float> lstFloat; //定义一个存放float的list容器。

list<string> lstString; //定义一个存放string的list容器。

...                

//尖括号内还可以设置指针类型或自定义类型。

list头尾的添加移除操作

  • list.push_back(elem);     //在容器尾部加入一个元素
  • list.pop_back(); //删除容器中最后一个元素
  • list.push_front(elem); //在容器开头插入一个元素
  • list.pop_front(); //从容器开头移除第一个元素

 

    list<int> lstInt;

    lstInt.push_back(1);

    lstInt.push_back(3);

    lstInt.push_back(5);

    lstInt.push_back(7);

    lstInt.push_back(9);

    lstInt.pop_front();

    lstInt.pop_front();

    lstInt.push_front(11);

    lstInt.push_front(13);

    lstInt.pop_back();

    lstInt.pop_back();

// lstInt {13,11,5}

list的数据存取

  • list.front(); //返回第一个元素。
  • list.back(); //返回最后一个元素。

 

list<int> lstInt;

    lstInt.push_back(1);

    lstInt.push_back(3);

    lstInt.push_back(5);

    lstInt.push_back(7);

    lstInt.push_back(9);

 

    int iFront = lstInt.front();    //1

    int iBack = lstInt.back();        //9

    lstInt.front() = 11;            //11

    lstInt.back() = 19;            //19

list与迭代器

  • list.begin(); //返回容器中第一个元素的迭代器。
  • list.end(); //返回容器中最后一个元素之后的迭代器。
  • list.rbegin(); //返回容器中倒数第一个元素的迭代器。
  • list.rend(); //返回容器中倒数最后一个元素的后面的迭代器。

 

    list<int> lstInt;

    lstInt.push_back(1);

    lstInt.push_back(3);

    lstInt.push_back(5);

    lstInt.push_back(7);

    lstInt.push_back(9);

 

    for (list<int>::iterator it=lstInt.begin(); it!=lstInt.end(); ++it)

    {

        cout << *it;

        cout << " ";

    }

 

    for (list<int>::reverse_iterator rit=lstInt.rbegin(); rit!=lstInt.rend(); ++rit)

    {

        cout << *rit;

        cout << " ";

    }

list对象的带参数构造

  • list(beg,end); //构造函数将[beg, end)区间中的元素拷贝给本身。注意该区间是左闭右开的区间。
  • list(n,elem); //构造函数将n个elem拷贝给本身。
  • list(const list &lst); //拷贝构造函数。

 

list<int> lstIntA;

    lstIntA.push_back(1);

    lstIntA.push_back(3);

    lstIntA.push_back(5);

    lstIntA.push_back(7);

    lstIntA.push_back(9);

 

    list<int> lstIntB(lstIntA.begin(),lstIntA.end());        //1 3 5 7 9

    list<int> lstIntC(5,8);                            //8 8 8 8 8

    list<int> lstIntD(lstIntA);                        //1 3 5 7 9

list的赋值

  • list.assign(beg,end); //将[beg, end)区间中的数据拷贝赋值给本身。注意该区间是左闭右开的区间。
  • list.assign(n,elem); //将n个elem拷贝赋值给本身。
  • list& operator=(const list &lst);    //重载等号操作符
  • list.swap(lst); // 将lst与本身的元素互换。

 

    list<int> lstIntA,lstIntB,lstIntC,lstIntD;

    lstIntA.push_back(1);

    lstIntA.push_back(3);

    lstIntA.push_back(5);

    lstIntA.push_back(7);

    lstIntA.push_back(9);

 

    lstIntB.assign(lstIntA.begin(),lstIntA.end());        //1 3 5 7 9

    lstIntC.assign(5,8);                            //8 8 8 8 8

    lstIntD = lstIntA;                            //1 3 5 7 9

    lstIntC.swap(lstIntD);                        //互换

list的大小

  • list.size();     //返回容器中元素的个数
  • list.empty();     //判断容器是否为空
  • list.resize(num); //重新指定容器的长度为num,若容器变长,则以默认值填充新位置。如果容器变短,则末尾超出容器长度的元素被删除。
  • list.resize(num, elem); //重新指定容器的长度为num,若容器变长,则以elem值填充新位置。如果容器变短,则末尾超出容器长度的元素被删除。

 

    list<int> lstIntA;

    lstIntA.push_back(1);

    lstIntA.push_back(3);

    lstIntA.push_back(5);

 

    if (!lstIntA.empty())

    {

        int iSize = lstIntA.size();        //3

        lstIntA.resize(5);            //1 3 5 0 0

        lstIntA.resize(7,1);            //1 3 5 0 0 1 1

        lstIntA.resize(2);            //1 3

    }

list的插入

  • list.insert(pos,elem); //在pos位置插入一个elem元素的拷贝,返回新数据的位置。
  • list.insert(pos,n,elem); //在pos位置插入n个elem数据,无返回值。
  • list.insert(pos,beg,end); //在pos位置插入[beg,end)区间的数据,无返回值。

 

    list<int> lstA;

    list<int> lstB;

 

    lstA.push_back(1);

    lstA.push_back(3);

    lstA.push_back(5);

    lstA.push_back(7);

    lstA.push_back(9);

 

    lstB.push_back(2);

    lstB.push_back(4);

    lstB.push_back(6);

    lstB.push_back(8);

 

    lstA.insert(lstA.begin(), 11);        //{11, 1, 3, 5, 7, 9}

    lstA.insert(++lstA.begin(),2,33);        //{11,33,33,1,3,5,7,9}

    lstA.insert(lstA.begin() , lstB.begin() , lstB.end() );    //{2,4,6,8,11,33,33,1,3,5,7,9}

list的删除

  • list.clear();        //移除容器的所有数据
  • list.erase(beg,end); //删除[beg,end)区间的数据,返回下一个数据的位置。
  • list.erase(pos); //删除pos位置的数据,返回下一个数据的位置。
  • lst.remove(elem); //删除容器中所有与elem值匹配的元素。

 

删除区间内的元素

lstInt是用list<int>声明的容器,现已包含按顺序的1,3,5,6,9元素。

list<int>::iterator itBegin=lstInt.begin();

++ itBegin;

list<int>::iterator itEnd=lstInt.begin();

++ itEnd;

++ itEnd;

++ itEnd;

lstInt.erase(itBegin,itEnd);

//此时容器lstInt包含按顺序的1,6,9三个元素。

 

 

 

假设 lstInt 包含1,3,2,3,3,3,4,3,5,3,删除容器中等于3的元素的方法一

for(list<int>::iterator it=lstInt.being(); it!=lstInt.end(); ) //小括号里不需写 ++it

{

if(*it == 3)

{

it = lstInt.erase(it); //以迭代器为参数,删除元素3,并把数据删除后的下一个元素位置返回给迭代器。

//此时,不执行 ++it;

}

else

{

++it;

}

}

 

删除容器中等于3的元素的方法二

lstInt.remove(3);

 

删除lstInt的所有元素

lstInt.clear();            //容器为空

list的反序排列

  • lst.reverse(); //反转链表,比如lst包含1,3,5元素,运行此方法后,lst就包含5,3,1元素。

 

    list<int> lstA;

    

    lstA.push_back(1);

    lstA.push_back(3);

    lstA.push_back(5);

    lstA.push_back(7);

    lstA.push_back(9);

 

    lstA.reverse();            //9 7 5 3 1

 

小结:

  • 一、容器deque的使用方法

    适合    在头尾添加移除元素。使用方法与vector类似。

  • 二、容器queue,stack的使用方法

    适合队列,堆栈的操作方式。

  • 三、容器list的使用方法

    适合在任意位置快速插入移除元素

7优先级队列priority_queue

  • 最大值优先级队列、最小值优先级队列
  • 优先级队列适配器 STL priority_queue
  • 用来开发一些特殊的应用,请对stl的类库,多做扩展性学习

    priority_queue<int, deque<int>>     pq;

    priority_queue<int, vector<int>>     pq;

    pq.empty()

    pq.size()

    pq.top()

    pq.pop()

    pq.push(item)

#include <iostream>

using namespace std;

#include "queue"

void main()

{

    priority_queue<int> p1; //默认是 最大值优先级队列

    //priority_queue<int, vector<int>, less<int> > p1; //相当于这样写

    priority_queue<int, vector<int>, greater<int>> p2; //最小值优先级队列

 

    p1.push(33);

    p1.push(11);

    p1.push(55);

    p1.push(22);

    cout <<"队列大小" << p1.size() << endl;

    cout <<"队头" << p1.top() << endl;

 

    while (p1.size() > 0)

    {

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

        p1.pop();

    }

    cout << endl;

 

    cout << "测试 最小值优先级队列" << endl;

    ppush(33);

    ppush(11);

    ppush(55);

    ppush(22);

    while (psize() > 0)

    {

        cout << ptop() << " ";

        ppop();

 

    }

}

 

8 Set和multiset容器

set/multiset的简介

  • set是一个集合容器,其中所包含的元素是唯一的,集合中的元素按一定的顺序排列元素插入过程是按排序规则插入,所以不能指定插入位置。
  • set采用红黑树变体的数据结构实现,红黑树属于平衡二叉树。在插入操作和删除操作上比vector快。
  • set不可以直接存取元素。(不可以使用at.(pos)与[]操作符)。
  • multiset与set的区别:set支持唯一键值,每个元素值只能出现一次;而multiset中同一值可以出现多次
  • 不可以直接修改set或multiset容器中的元素值,因为该类容器是自动排序的。如果希望修改一个元素值,必须先删除原有的元素,再插入新的元素。
  • #include <set>

 

 

c++复习:STL之容器

set/multiset对象的默认构造

set<int> setInt; //一个存放int的set容器。

set<float> setFloat; //一个存放float的set容器。

set<string> setString; //一个存放string的set容器。

multiset<int> mulsetInt; //一个存放int的multi set容器。

multi set<float> multisetFloat; //一个存放float的multi set容器。

multi set<string> multisetString; //一个存放string的multi set容器。

set的插入与迭代器

  • set.insert(elem); //在容器中插入元素。
  • set.begin(); //返回容器中第一个数据的迭代器。
  • set.end(); //返回容器中最后一个数据之后的迭代器。
  • set.rbegin(); //返回容器中倒数第一个元素的迭代器。
  • set.rend(); //返回容器中倒数最后一个元素的后面的迭代器。

 

set<int> setInt;

setInt.insert(3); setInt.insert(1);setInt.insert(5);setInt.insert(2);

for(set<int>::iterator it=setInt.begin(); it!=setInt.end(); ++it)

{

int iItem = *it;

cout << iItem; //或直接使用cout << *it

}

//这样子便顺序输出 1 2 3 5。

 

set.rbegin()与set.rend()。略。

 

Set集合的元素排序

  • set<int,less<int> > setIntA; //该容器是按升序方式排列元素。
  • set<int,greater<int>> setIntB; //该容器是按降序方式排列元素。
  • set<int> 相当于 set<int,less<int>>。
  • less<int>与greater<int>中的int可以改成其它类型,该类型主要要跟set容纳的数据类型一致。
  • 疑问1:less<>与greater<>是什么?
  • 疑问2:如果set<>不包含int类型,而是包含自定义类型,set容器如何排序?
  • 要解决如上两个问题,需要了解容器的函数对象,也叫伪函数,英文名叫functor。
  • 下面将讲解什么是functor,functor的用法。

 

使用stl提供的函数对象

set<int,greater<int>> setIntB;

setIntB.insert(3);

setIntB.insert(1);

setIntB.insert(5);

setIntB.insert(2);

此时容器setIntB就包含了按顺序的5,3,2,1元素

函数对象functor的用法

  • 尽管函数指针被广泛用于实现函数回调,但C++还提供了一个重要的实现回调函数的方法,那就是函数对象。
  • functor,翻译成函数对象,伪函数,算符,是重载了"()"操作符的普通类对象。从语法上讲,它与普通函数行为类似。
  • greater<>与less<>就是函数对象。
  • 下面举出greater<int>的简易实现原理。

 

下面举出greater<int>的简易实现原理。

struct greater

{

bool operator() (const int& iLeft, const int& iRight)

{

return (iLeft>iRight); //如果是实现less<int>的话,这边是写return (iLeft<iRight);

}

}

容器就是调用函数对象的operator()方法去比较两个值的大小。

 

题目:学生包含学号,姓名属性,现要求任意插入几个学生对象到set容器中,使得容器中的学生按学号的升序排序。

 

解:

//学生类

class CStudent

{

    public:

        CStudent(int iID, string strName)

        {

            m_iID = iID;

            m_strName = strName;

        }

int m_iID;        //学号

string m_strName;     //姓名

}

//为保持主题鲜明,本类不写拷贝构造函数,不过本类也不需要写拷贝构造函数。但大家仍要有考虑拷贝构造函数的习惯。

 

//函数对象

struct StuFunctor

{

        bool operator() (const CStudent &stu1, const CStudent &stu2)

        {

            return (stu1.m_iID<stum_iID);

        }

}

 

//main函数

void main()

{

        set<CStudent, StuFunctor> setStu;

        setStu.insert(CStudent(3,"小张"));

        setStu.insert(CStudent(1,"小李"));

        setStu.insert(CStudent(5,"小王"));

        setStu.insert(CStudent(2,"小刘"));

        //此时容器setStu包含了四个学生对象,分别是按姓名顺序的"小李","小刘","小张","小王"

}

 

set对象的拷贝构造与赋值

set(const set &st);         //拷贝构造函数

set& operator=(const set &st);    //重载等号操作符

set.swap(st);                //交换两个集合容器

 

set<int> setIntA;

    setIntA.insert(3);

    setIntA.insert(1);

    setIntA.insert(7);

    setIntA.insert(5);

    setIntA.insert(9);

 

    set<int> setIntB(setIntA); //1 3 5 7 9

    

    set<int> setIntC;

    setIntC = setIntA;        //1 3 5 7 9

 

    setIntC.insert(6);

    setIntC.swap(setIntA);     //交换

set的大小

  • set.size();    //返回容器中元素的数目
  • set.empty();//判断容器是否为空

 

set<int> setIntA;

    setIntA.insert(3);

    setIntA.insert(1);

    setIntA.insert(7);

    setIntA.insert(5);

    setIntA.insert(9);

 

    if (!setIntA.empty())

    {

        int iSize = setIntA.size();        //5

    }

set的删除

  • set.clear();        //清除所有元素
  • set.erase(pos);    //删除pos迭代器所指的元素,返回下一个元素的迭代器。
  • set.erase(beg,end);     //删除区间[beg,end)的所有元素    ,返回下一个元素的迭代器。
  • set.erase(elem); //删除容器中值为elem的元素。

 

删除区间内的元素

setInt是用set<int>声明的容器,现已包含按顺序的1,3,5,6,9,11元素。

set<int>::iterator itBegin=setInt.begin();

++ itBegin;

set<int>::iterator itEnd=setInt.begin();

++ itEnd;

++ itEnd;

++ itEnd;

setInt.erase(itBegin,itEnd);

//此时容器setInt包含按顺序的1,6,9,11四个元素。

 

删除容器中第一个元素

setInt.erase(setInt.begin());        //6,9,11

 

删除容器中值为9的元素

set.erase(9);

 

 

删除setInt的所有元素

setInt.clear();            //容器为空

set的查找

  • set.find(elem); //查找elem元素,返回指向elem元素的迭代器。
  • set.count(elem); //返回容器中值为elem的元素个数。对set来说,要么是0,要么是1。对multiset来说,值可能大于1。
  • set.lower_bound(elem); //返回第一个>=elem元素的迭代器。
  • set.upper_bound(elem);     // 返回第一个>elem元素的迭代器。
  • set.equal_range(elem);        //返回容器中与elem相等的上下限的两个迭代器。上限是闭区间,下限是开区间,如[beg,end)。
  • 以上函数返回两个迭代器,而这两个迭代器被封装在pair中。
  • 以下讲解pair的含义与使用方法。

 

set<int> setInt;

    setInt.insert(3);

    setInt.insert(1);

    setInt.insert(7);

    setInt.insert(5);

    setInt.insert(9);

 

    set<int>::iterator itA = setInt.find(5);

    int iA = *itA;        //iA == 5

    int iCount = setInt.count(5);    //iCount == 1

 

    set<int>::iterator itB = setInt.lower_bound(5);

    set<int>::iterator itC = setInt.upper_bound(5);

    int iB = *itB;    //iB == 5

    int iC = *itC; //iC == 7

 

pair< set<int>::iterator, set<int>::iterator > pairIt = setInt.equal_range(5); //pair是什么?

pair的使用

  • pair译为对组,可以将两个值视为一个单元。
  • pair<T1,T2>存放的两个值的类型,可以不一样,如T1为int,T2为float。T1,T2也可以是自定义类型。
  • pair.first是pair里面的第一个值,是T1类型。
  • pair.second是pair里面的第二个值,是T2类型。

 

set<int> setInt;

... //往setInt容器插入元素1,3,5,7,9

pair< set<int>::iterator , set<int>::iterator > pairIt = setInt.equal_range(5);

set<int>::iterator itBeg = pairIt.first;

set<int>::iterator itEnd = pairIt.second;

//此时 *itBeg==5 而 *itEnd == 7

小结

  • 一、容器set/multiset的使用方法;

            红黑树的变体,查找效率高,插入不能指定位置,插入时自动排序。

  • 二、functor的使用方法;

类似于函数的功能,可用来自定义一些规则,如元素比较规则。

  • 三、pair的使用方法。

    对组,一个整体的单元,存放两个类型(T1,T2,T1可与T2一样)的两个元素。

 

案例:

    int x;

scanf("%ld",&x);

multiset<int> h;//建立一个multiset类型,变量名是h,h序列里面存的是int类型,初始h为空

while(x!=0){

h.insert(x);//将x插入h中

scanf("%ld",&x);

}

 

    pair< multiset<int>::iterator , multiset<int>::iterator > pairIt = h.equal_range(22);

    multiset<int>::iterator itBeg = pairIt.first;

    multiset<int>::iterator itEnd = pairIt.second;

 

    int nBeg = *itBeg;

    int nEnd = *itEnd;

 

while(!h.empty()){// 序列非空h.empty()==true时表示h已经空了

        multiset<int>::iterator c = h.begin();//c指向h序列中第一个元素的地址,第一个元素是最小的元素

printf("%ld ",*c);//将地址c存的数据输出

h.erase(c);//从h序列中将c指向的元素删除

}    

 

9 Map和multimap容器

map/multimap的简介

  • map是标准的关联式容器,一个map是一个键值对序列,即(key,value)对。它提供基于key的快速检索能力。
  • map中key值是唯一的。集合中的元素按一定的顺序排列。元素插入过程是按排序规则插入,所以不能指定插入位置。
  • map的具体实现采用红黑树变体的平衡二叉树的数据结构。在插入操作和删除操作上比vector快。
  • map可以直接存取key所对应的value,支持[]操作符,如map[key]=value。
  • multimap与map的区别:map支持唯一键值,每个键只能出现一次;而multimap中相同键可以出现多次。multimap不支持[]操作符。
  • #include <map>

 

c++复习:STL之容器

map/multimap对象的默认构造

map/multimap采用模板类实现,对象的默认构造形式:

map<T1,T2> mapTT;

multimap<T1,T2> multimapTT;

如:

map<int, char> mapA;

map<string,float> mapB;

//其中T1,T2还可以用各种指针类型或自定义类型

map的插入与迭代器

  • map.insert(...); //往容器插入元素,返回pair<iterator,bool>
  • 在map中插入元素的三种方式:

    假设 map<int, string> mapStu;

  • 一、通过pair的方式插入对象

    mapStu.insert( pair<int,string>(3,"小张") );

  • 二、通过pair的方式插入对象

    mapStu.inset(make_pair(-1, "校长-1"));

  • 三、通过value_type的方式插入对象

    mapStu.insert( map<int,string>::value_type(1,"小李") );

  • 四、通过数组的方式插入值

    mapStu[3] = "小刘";

    mapStu[5] = "小王";

    

  • 前三种方法,采用的是insert()方法,该方法返回值为pair<iterator,bool>
  • 第四种方法非常直观,但存在一个性能的问题。插入3时,先在mapStu中查找主键为3的项,若没发现,则将一个键为3,值为初始化值的对组插入到mapStu中,然后再将值修改成"小刘"。若发现已存在3这个键,则修改这个键对应的value。
  • string strName = mapStu[2]; //取操作或插入操作
  • 只有当mapStu存在2这个键时才是正确的取操作,否则会自动插入一个实例,键为2,值为初始化值。

     

     

假设 map<int, string> mapA;

pair< map<int,string>::iterator, bool > pairResult = mapA.insert(pair<int,string>(3,"小张"));            //插入方式一

 

int iFirstFirst = (pairResult.first)->first;        //iFirst == 3;

string strFirstSecond = (pairResult.first)->second;        //strFirstSecond为"小张"

bool bSecond = pairResult.second;                            //bSecond == true;

        

mapA.insert(map<int,string>::value_type(1,"小李"));            //插入方式二

 

mapA[3] = "小刘";            //修改value

mapA[5] = "小王";            //插入方式三

 

string str1 = mapA[2];            //执行插入 string() 操作,返回的str1的字符串内容为空。

string str2 = mapA[3];            //取得value,str2为"小刘"

 

 

//迭代器遍历

    for (map<int,string>::iterator it=mapA.begin(); it!=mapA.end(); ++it)

    {

        pair<int, string> pr = *it;

        int iKey = pr.first;

        string strValue = pr.second;

    }

map.rbegin()与map.rend() 略。

 

 

  • map<T1,T2,less<T1> > mapA; //该容器是按键的升序方式排列元素。未指定函数对象,默认采用less<T1>函数对象。
  • map<T1,T2,greater<T1>> mapB; //该容器是按键的降序方式排列元素。
  • less<T1>与greater<T1> 可以替换成其它的函数对象functor。
  • 可编写自定义函数对象以进行自定义类型的比较,使用方法与set构造时所用的函数对象一样。
  • map.begin(); //返回容器中第一个数据的迭代器。
  • map.end(); //返回容器中最后一个数据之后的迭代器。
  • map.rbegin(); //返回容器中倒数第一个元素的迭代器。
  • map.rend(); //返回容器中倒数最后一个元素的后面的迭代器。

 

map对象的拷贝构造与赋值

map(const map &mp);         //拷贝构造函数

map& operator=(const map &mp);    //重载等号操作符

map.swap(mp);                //交换两个集合容器

例如:

        map<int, string> mapA;

        mapA.insert(pair<int,string>(3,"小张"));    

        mapA.insert(pair<int,string>(1,"小杨"));    

        mapA.insert(pair<int,string>(7,"小赵"));    

        mapA.insert(pair<int,string>(5,"小王"));    

 

        map<int ,string> mapB(mapA);            //拷贝构造

        

        map<int, string> mapC;

        mapC = mapA;                                //赋值

 

        mapC[3] = "老张";

        mapC.swap(mapA);            //交换

map的大小

  • map.size();    //返回容器中元素的数目
  • map.empty();//判断容器是否为空

        map<int, string> mapA;

        mapA.insert(pair<int,string>(3,"小张"));    

        mapA.insert(pair<int,string>(1,"小杨"));    

        mapA.insert(pair<int,string>(7,"小赵"));    

        mapA.insert(pair<int,string>(5,"小王"));    

 

        if (mapA.empty())

        {

            int iSize = mapA.size();        //iSize == 4

        }

map的删除

  • map.clear();        //删除所有元素
  • map.erase(pos);    //删除pos迭代器所指的元素,返回下一个元素的迭代器。
  • map.erase(beg,end);     //删除区间[beg,end)的所有元素    ,返回下一个元素的迭代器。
  • map.erase(keyElem); //删除容器中key为keyElem的对组。

map<int, string> mapA;

        mapA.insert(pair<int,string>(3,"小张"));    

        mapA.insert(pair<int,string>(1,"小杨"));    

        mapA.insert(pair<int,string>(7,"小赵"));    

        mapA.insert(pair<int,string>(5,"小王"));    

 

        //删除区间内的元素

        map<int,string>::iterator itBegin=mapA.begin();

        ++ itBegin;

        ++ itBegin;

        map<int,string>::iterator itEnd=mapA.end();

        mapA.erase(itBegin,itEnd);            //此时容器mapA包含按顺序的{1,"小杨"}{3,"小张"}两个元素。

 

        mapA.insert(pair<int,string>(7,"小赵"));    

        mapA.insert(pair<int,string>(5,"小王"));    

 

        //删除容器中第一个元素

        mapA.erase(mapA.begin());        //此时容器mapA包含了按顺序的{3,"小张"}{5,"小王"}{7,"小赵"}三个元素

 

        //删除容器中key为5的元素

        mapA.erase(5);

 

 

        //删除mapA的所有元素

        mapA.clear();            //容器为空

map的查找

  • map.find(key); 查找键key是否存在,若存在,返回该键的元素的迭代器;若不存在,返回map.end();
  • map.count(keyElem); //返回容器中key为keyElem的对组个数。对map来说,要么是0,要么是1。对multimap来说,值可能大于1。

map<int,string>::iterator it=mapStu.find(3);

if(it == mapStu.end())

{

        //没找到

}

else

{

     //找到了

pair<int, string> pairStu = *it;

     int iID = pairStu.first;        //或 int iID = it->first;

string strName = pairStu.second;    //或 string strName = it->second;

 

  • map.lower_bound(keyElem); //返回第一个key>=keyElem元素的迭代器。
  • map.upper_bound(keyElem);     // 返回第一个key>keyElem元素的迭代器。

例如: mapStu是用map<int,string>声明的容器,已包含{1,"小李"}{3,"小张"}{5,"小王"}{7,"小赵"}{9,"小陈"}元素。map<int,string>::iterator it;

it = mapStu.lower_bound(5); //it->first==5 it->second=="小王"

it = mapStu.upper_bound(5); //it->first==7 it->second=="小赵"

it = mapStu.lower_bound(6); //it->first==7 it->second=="小赵"

it = mapStu.upper_bound(6); //it->first==7 it->second=="小赵"

 

 

  • map.equal_range(keyElem);        //返回容器中key与keyElem相等的上下限的两个迭代器。上限是闭区间,下限是开区间,如[beg,end)。

 

以上函数返回两个迭代器,而这两个迭代器被封装在pair中。

 

例如 map<int,string> mapStu;

... //往mapStu容器插入元素{1,"小李"}{3,"小张"}{5,"小王"}{7,"小赵"}{9,"小陈"}

pair< map<int,string>::iterator , map<int,string>::iterator > pairIt = mapStu.equal_range(5);

map<int, string>::iterator itBeg = pairIt.first;

map<int, string>::iterator itEnd = pairIt.second;

//此时 itBeg->first==5 , itEnd->first == 7,

itBeg->second=="小王", itEnd->second=="小赵"

 

 

Multimap 案例:

//1个key值可以对应多个valude =è分组

//公司有销售部 sale (员工2名)、技术研发部 development (1人)、财务部 Financial (2人)

//人员信息有:姓名,年龄,电话、工资等组成

//通过 multimap进行 信息的插入、保存、显示

//分部门显示员工信息

10 容器共性机制研究

10.1容器的共通能力

C++模板是容器的概念。

c++复习:STL之容器

理论提高:所有容器提供的都是值(value)语意,而非引用(reference)语意。容器执行插入元素的操作时,内部实施拷贝动作。所以STL容器内存储的元素必须能够被拷贝(必须提供拷贝构造函数)。

 

  • 除了queue与stack外,每个容器都提供可返回迭代器的函数,运用返回的迭代器就可以访问元素。
  • 通常STL不会丢出异常。要求使用者确保传入正确的参数。
  • 每个容器都提供了一个默认构造函数跟一个默认拷贝构造函数。
  • 如已有容器vecIntA。
  • vector<int> vecIntB(vecIntA); //调用拷贝构造函数,复制vecIntA到vecIntB中。
  • 与大小相关的操作方法(c代表容器):

    c.size(); //返回容器中元素的个数

    c.empty(); //判断容器是否为空

  • 比较操作(c1,c2代表容器):

    c1 == c2 判断c1是否等于c2

    c1 != c2 判断c1是否不等于c2

    c1 = c2 把c2的所有元素指派给c1

 

c++复习:STL之容器10.2各个容器的使用时机

 

 

 

  • Vector的使用场景:比如软件历史操作记录的存储,我们经常要查看历史记录,比如上一次的记录,上上次的记录,但却不会去删除记录,因为记录是事实的描述。
  •  deque的使用场景:比如排队购票系统,对排队者的存储可以采用deque,支持头端的快速移除,尾端的快速添加。如果采用vector,则头端移除时,会移动大量的数据,速度慢。
  • vector与deque的比较:
  • 一:vector.at()比deque.at()效率高,比如vector.at(0)是固定的,deque的开始位置却是不固定的。
  • 二:如果有大量释放操作的话,vector花的时间更少,这跟二者的内部实现有关。
  • 三:deque支持头部的快速插入与快速移除,这是deque的优点。
  • list的使用场景:比如公交车乘客的存储,随时可能有乘客下车,支持频繁的不确实位置元素的移除插入。
  • set的使用场景:比如对手机游戏的个人得分记录的存储,存储要求从高分到低分的顺序排列。 
  • map的使用场景:比如按ID号存储十万个用户,想要快速要通过ID查找对应的用户。二叉树的查找效率,这时就体现出来了。如果是vector容器,最坏的情况下可能要遍历完整个容器才能找到该用户。