精华内容
下载资源
问答
  • C++STL容器的比较
    2022-01-03 20:24:10


    前言

    STL是c++的标准模板库,模板分为类模板和函数模板,我们所说的容器是构成STL标准模板库的一部分,STL容器大致上分为两大部分:序列容器和相联容器,而相联容器又分为两大部分:排序容器和哈希容器


    一、序列容器

    序列容器里面都可用放什么东西?例如存放int double float char 类型的元素,除此之外还可以存放自己定义的结构体元素。

    1、vector动态数组:它的长度是可以改变的,在尾部插入和删除元素的时间复杂度为o(1),支持随机访问,(其实就是数组的升级版),但是在中间某个位置插入和删除元素时间复杂度为o(n),为什么?就算它支持随机访问,能快速找到要插入和删除的位置,但是插入或者删除后要进行元素的移动。

    vector<int>a(20)//定义一个vector  a容量为20
    vector.push_back(1)//把1插入到尾部
    vector.pop_back()//删除尾部元素
    //insert函数需要借助迭代器实现在中间插入一个或者多个元素
    //erase函数需要借助迭代器实现在中间删除一个或多个元素
    

    2、deque双端队列容器:它在首位插入和删除元素的时间复杂度都是O(1),在中间插入和删除的时间复杂度和vector一样,支持随机访问。

    3、list双向链表容器:不支持随机访问,但是在任意位置上插入和删除的时间复杂度都是O(1)。

    二、相联容器:排序容器和哈希容器

    相联容器里面存放的是啥?不像序列容器,相联容器顾名思义就是存放的是一个个存在联系的键值对,并且默认根据键的大小升序排序。

    1、map映射容器的特点:map容器存储的各个键值对,既不能重复,也不能被修改,键的类型会用const修饰。
    2、set容器的特点:使用 set 容器存储的各个键值对,要求键 key 和值 value 必须相等。


    总结

    加油加油

    更多相关内容
  • C++ STL容器 内容详解

    2021-04-30 18:54:40
    C++ STL容器 简单来说,容器就是一些模板类的集合,但和普通模板类不同的是,容器中封装的是组织数据的方法(也就是数据结构)。 STL提供三类标准容器:序列容器、排序容器和哈希容器,其中后两类容器也称为关联容器...

    C++ STL容器

     简单来说,容器就是一些模板类的集合,但和普通模板类不同的是,容器中封装的是组织数据的方法(也就是数据结构)。

     STL提供三类标准容器:序列容器排序容器哈希容器,其中后两类容器也称为关联容器



    序列容器

     所谓序列容器,即以线性排列(类似普通数组的存储方式)来存储某一指定类型的数据。之所以被称为序列容器,是因为元素在容器中的位置与元素的值无关,即容器不是排序的,该类容器并不会自动对存储的元素按照值的大小进行排序。也就是说,将元素插入容器时,指定在什么位置,元素就会位于什么位置。

     序列容器主要包括:

    array数组容器

    array<T,N>:表示可以存储N个T类型的元素,是C++本身提供的一种容器。
    此类容器一旦建立,其长度就是固定不变的,这意味着不能增加或删除元素,只能改变某个元素的值。
    在这里插入图片描述

    vector向量容器

    vector< T >:用来存放T类型的元素,是一个长度可变的序列容器,即在存储空间不足时,会自动申请更多的内存。
    使用此容器,在尾部增加或删除元素的效率最高(O(1)),在其它位置插入或删除元素的效率较差(O(n),其中n是容器中元素的个数)。
    66666

    deque双端队列容器

    deque< T >:和vector非常相似,区别在于使用该容器不仅尾部插入和删除元素高效,在头部插入或删除元素也同样高效,时间复杂度均为O(1),但是在容器中某一位置插入或删除元素的时间复杂度仍为O(n)。
    在这里插入图片描述

    list链表容器

    list< T >:是一个长度可变、由T类型元素组成的序列,它以双向链表的形式组织元素,在这个序列的任何地方都可以高效的增加或删除元素(O(1)),但访问容器中任意元素的速度要比前三种容器慢,这是因为list< T >必须从第一个元素或最后一个元素开始访问,需要沿着链表移动,直到到达想要访问的元素。
    在这里插入图片描述

    forward_list正向链表容器

    forward_list< T >:和list容器非常类似,只不过它以单链表的形式组织元素,它内部的元素只能从第一个元素开始访问,是一类比链表容器快、更节省内存的容器。
    在这里插入图片描述


    关联容器

    关联式容器在存储元素值的同时,还会为各元素额外再配备一个值,又称为“键”,其本质也是一个C++基础数据类型或自定义类型的元素,它的功能是在使用关联式容器的过程中,如果已知目标元素的键的值,则直接通过该键就可以找到目标元素, 而无需通过遍历整个容器的方式。
    也就是说,使用关联式容器存储的元素,都是一个个的键值对(<key,value>),这是和序列式容器最大的不同。除此之外,使用关联式存储的元素,默认会根据各元素的键值的大小做升序排序。



    排序容器

     排序容器中的元素默认是由小到大顺序排好的,即便是插入元素,元素也会插入到适当位置。所以关联容器在查找时具有非常好的性能。
     排序容器主要包括:

    set集合容器

    定义在< set >头文件中,使用该容器存储的数据,各个元素的键和值完全相同,且各个元素的值不能重复(保证了各元素键的唯一性)。该容器会自动根据各个元素的键(其实也就是元素的值)的大小进行升序排序(调用std::less< T >)。

    multiset多重集合容器

    定义在<set>头文件中,和set容器唯一的不同在于,multiset容器中存储元素的值可以重复(一旦值重复,则意味着键也是重复的)。

    map映射容器

    定义在< map >头文件中,使用该容器存储的数据,其各个元素的键必须是唯一的,不能重复,该容器会根据各元素键的大小,默认进行升序排序(调用std::less< T >)。

    multimap多重映射容器

    定义在< map >头文件中,和map容器唯一的不同在于,multimap容器中存储元素的键可以重复。


    哈希容器(无序关联容器、无序容器)

     哈希容器中的元素是未排序的,元素的位置由哈希函数确定
     和关联式容器一样,无序容器也使用键值对(pair类型)的方式存储数据
     但是,关联式容器和无序容器之间有本质上的不同:关联式容器的底层实现采用的树存储结构,更确切的说是红黑树结构;无序容器的底层实现采用的是哈希表的存储结构(C++底层采用哈希表实现无序容器时,会将数据存储到一整块连续的内存空间中,并且当数据存储位置发生冲突时,采用“开链法”解决)。

    基于底层实现采用了不同的数据结构,因此和关联式容器相比,无序容器具有以下两个特点

    1. 无序容器内部存储的键值对是无序的,各键值对的存储位置取决于键值对中的键。
    2. 和关联式容器相比,无序容器擅长通过指定键查找对应的值(O(1)),但对于使用迭代器遍历容器中存储的元素,无序容器的执行效率则不如关联式容器。

    C++ 11中新添加4中关联式容器:

    unordered_set哈希集合

    不再以键值对的形式存储数据,而是直接存储数据元素本身(也可以理解为,该容器存储的全部都是键key和值value相等的键值对,正因为它们相等,因此只存储value即可)。另外,该容器存储的元素不能重复,且容器内部存储的元素也是无序的。

    unordered_multiset哈希多重集合

    和unordered_set唯一的区别在于,该容器允许存储值相同的元素。

    unordered_map哈希映射

    存储键值对<key, value>类型的元素,其中各个键值对的键不允许重复,且该容器中存储的键值对是无序的。

    unordered_multimap哈希多重映射

    和unordered_map唯一的区别在于,该容器允许存储多个键相同的键值对

     很容易发现,以上4种无序容器的名称,是前面4种关联式容器名称的基础上添加了"unordered_",以 map 和 unordered_map 为例,其实它们之间只有一个区别:即 map 容器内存会对存储的键值对进行排序,而 unordered_map 不会。

     无序容器其实就是在已提供的4种关联式容器的基础上,又新增了各自的"unordered"版本,提高了查找指定元素的效率。

     既然无序容器和之前所学的关联式容器类似,那么在实际使用中应该选哪种容器呢?
     总的来说,实际场景中如果涉及大量遍历容器的操作,建议首选关联式容器;反之,如果更多的操作是通过键获取对应的值,则应首选无序容器

    本文中链接的内容持续更新中。。。

    展开全文
  • C++ STL容器

    2020-09-27 09:40:54
    STL(标准模板库),是目前C++内置支持的library。它的底层利用了C++类模板和函数模板的机制,由三大部分组成:容器、算法和迭代器。 目前STL有六大组件 容器 container 算法 algorthm 迭代器 iterator 仿函数 ...

    STL(标准模板库),是目前C++内置支持的library。它的底层利用了C++类模板和函数模板的机制,由三大部分组成:容器、算法和迭代器。

    目前STL有六大组件

    • 容器 container
    • 算法 algorthm
    • 迭代器 iterator
    • 仿函数 function object
    • 适配器 adaptor
    • 空间配置器 allocator

    下面,我们会一一进行介绍。

    STL初探

    容器是STL中很重要的一种数据结构。常见的容器包括

    • vector容器
    • deque双端数组
    • stack栈模型
    • queue队列模型
    • list链表模型
    • priotriy_queue优先级队列
    • set与multiset容器
    • map与multimap容器

    除了容器,STL还封装了强大的算法,能够实现查找、删除、替换、删除等很多常见操作。后面会重点讲解。

    另外,迭代器也是STL重要的一环,通过迭代器,我们可以很方便对容器中的元素进行遍历,以及操作容器。后面我们会穿插讲解迭代器。

    STL中的string

    string是STL的字符串类型,在C语言中,我们通常用char *或者char[]字符数组来表示字符串。C++的string和C语言的char *有什么区别呢?

    • string是一个类,char *是指向字符的指针
    • string封装了char *,管理这个字符串,是一个char *类型的容器
    • string不用考虑内存释放和数组越界
    • string提供了一些列的字符串操作函数

    string的构造函数

    既然string是一个类,那么也就有构造函数,我们研究下string的构造函数。

    #include <iostream>
    using namespace std;
    int main(int argc, const char * argv[]) {
        
        //通过const char * 初始化
        string s1 = "aaaa";
        
        //构造函数初始化
        string s2("bbbbb");
        
        //通过拷贝构造函数来初始化对象s3
        string s3 = s2;
        
        //用10个'a'字符来初始化字符串
        string s4(10, 'a');
        
        return 0;
    }
    

    字符串的遍历

    字符串的遍历,有三种遍历的方式

    • 数组方式遍历,通过[]操作符遍历 (不会抛出异常)
    • at()方法遍历,根据index取值 (会抛出异常)
    • 通过STL迭代器遍历
    int main(int argc, const char * argv[]) {
        
        //创建字符串对象
        string str("abcdefg");
        
        //数组形式遍历
        for (int i = 0; i < str.length(); i++) {
            cout<< str[i] << endl;
        }
        
        //at方法遍历
        for (int i = 0; i < str.length(); i++) {
            cout << str.at(i) << endl;
        }
        
        //迭代器遍历
        for (string::iterator it = str.begin(); it != str.end(); it++) {
            cout << *it << endl;
        }
    
        return 0;
    }
    

    数组方式和at方法方式,有一个明显的不同

    • 数组方式,如果出现越界或者其他错误,不会抛出异常,程序直接终端。
    • at()方法遍历,出现越界或其他错误,会抛出异常,程序可以处理异常。

    迭代器其实可以看作是一个字符的指针,上个例子中string::iterator it = str.begin()就是定义一个string类型的迭代器,指向str的第一次位置。*it就表示当前的字符。注意str.end()表示字符串最后一个字符的后面一个位置。如果it == str.end()就表示已经遍历到终点了。

    string与char *的转换

    string提供了成员函数c_str来将string对象转化成const char *。string提供了copy(buf,size,begin)成员函数来讲string从begin位置开始的size个字符拷贝到buf中。需要注意的是:

    • 如果buf容纳不下,会越界
    • 拷贝过去后,不会转变成C风格的字符串,也就是不会在buf后面添加'\0'
    int main(int argc, const char * argv[]) {
        
        //1 string转char *
        string str("aaaaaa");
        const char *p = str.c_str();
        
        //2 char *转string
        const char *p1 = "12345";
        string str2 = p1;
        
        //3 string拷贝到buf[]中
        char buf[128] = {0};
        //从0开始,拷贝3个字符到buf指向的内存空间
        //如果buf空间容纳不下,会越界
        //拷贝过去时,不会给buf末尾添加\0
        str.copy(buf, 3, 0);
    
        return 0;
    }
    

    string的拼接

    string为我们提供了两种字符串拼接方式,一种是重写了 + 操作符,我们可以直接将连个字符串相加,类似于java的语法。另一种是string提供了成员函数append()供我们拼接连个字符串。

    int main(int argc, const char * argv[]) {
        
        string s1 = "123456";
        string s2 = "abcdef";
        
        //直接使用加号运算符拼接
        string s3 = s1 + s2;
        
        //使用成员函数拼接
        string s4 = s1.append(s2);
        
        cout<<s3<<endl;
        cout<<s4<<endl;
        
        return 0;
    }
    

    string的查找和替换

    string类提供了find函数,用来查找字符串中指定的字符。提供了replace函数,用来替换字符串中指定位置的字符串。

    replace函数是,先删除指定位置,指定长度的字符,然后在当前指定位置插入新的字符。

    int main(int argc, const char * argv[]) {
        
        
        string s1 = "hello hello hello hello hello hello 1234 7876";
        
        //从0位置开始查找第一个hello出现的首位位置
        size_t index1 = s1.find("hello",0);
        cout << index1 << endl;
        
        //查找第一个hello出现时的首位位置
        size_t index2 = s1.find_first_of("hello");
        cout << index2 << endl;
        
        //查找最后一个hello出现时的末尾位置
        size_t index3 = s1.find_last_of("hello");
        cout << index3 << endl;
        
        //求hello出现的次数,以及对应的下标
        int count = 0;
        size_t offindex = s1.find("hello",0);
        while (offindex != string::npos) {  //如果 offindex != -1
            //找到了
            cout << "索引:" << offindex <<endl;
            count++;
            offindex++;
            offindex = s1.find("hello", offindex);
        }
        
        //把hello替换成welcome
        size_t offindex1 = s1.find("hello", 0);
        while (offindex1 != string::npos) {
            
            //从offindex1的位置开始删除5个位置,并插入新的字符串welcome
            s1.replace(offindex1, strlen("hello"), "welcome");
            
            //从后面的位置开始
            offindex1 += strlen("welcome");
            
            //继续查找
            offindex1 = s1.find("hello", offindex1);
        }
        cout << "替换后的字符串:" << s1 <<endl;
    
        return 0;
    }
    

    string区间删除和插入

    string提供了inserterase分别实现插入和删除操作。

    插入:pos位置插入字符串s,返回新的string。

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

    插入:pos位置插入n个字符c,返回string。

    • string &insert(int pos, int n, char c)

    删除:删除从pos位置开始的n个字符,返回新的string

    • string &erase(int pos, int n)

    删除:删除指定迭代器的位置,返回当前迭代器位置

    • string::iterator erase(string::iterator it)

    删除:删除迭代器之间的字符,左闭右开区间

    • string::iterator erase(string::iterator beginIt, string::iterator endIt)
    int main(int argc, const char * argv[]) {
        
        string s1 = "hello1 world!";
        
        //1 删除字符串中的'1'
        //---通过find函数,查找'1'所在的迭代器位置
        string::iterator it = find(s1.begin(), s1.end(), '1');
        //---删除
        if (it != s1.end()) {
            s1.erase(it);
        }
        cout << s1 << endl;
        
        //2 删除起始迭代器位置的字符
        s1.erase(s1.begin(), s1.begin() + 3);
        cout << s1 << endl;
        
        //3 在0位置插入"AAA"
        s1.insert(0, "AAA");
        cout << s1 << endl;
        
        return 0;
    }
    

    string算法相关

    目前常见的string的算法是大小写转换。一般使用函数transform来进行转换。

    int main(int argc, const char * argv[]) {
        
        string s1 = "abcdefg";
        string s2 = "AEDLFLKJDLKJFL";
        
        //小写全部转换成大写,转换的结果放在s1.begin()的位置,后面的操作需要强制转换成指定的函数类型
        transform(s1.begin(), s1.end(), s1.begin(), (int (*)(int))toupper);
        cout << s1 <<endl;
        
        //大写全部转换成小写
        transform(s2.begin(), s2.end(), s2.begin(), (int (*)(int))tolower);
        cout << s2 <<endl;
       
        return 0;
    }
    
    

    STL中的vector容器

    vector是将元素放到动态数组中加以管理的容器。vector容器可以随机存取元素,也就是说支持[]运算符和at方式存取。

    • vector在尾部添加或者移除元素非常快,在中间操作非常耗时,因为它需要移动元素

    vector的基本用法

    既然vector是容器,那么就可以向这个容器添加删除元素。

    基本用法:

    • front()返回头部元素的引用,可以当左值
    • back()返回尾部元素的引用,可以当左值
    • push_back()添加元素,只能尾部添加
    • pop_back()移除元素,只能在尾部移除
    int main(int argc, const char * argv[]) {
        
        //定义一个vector容器
        vector<int> v1;
        
        //插入元素(尾部插入)
        v1.push_back(1);
        v1.push_back(2);
        v1.push_back(3);
        
        //迭代器遍历打印
        for (vector<int>::iterator it = v1.begin(); it != v1.end(); it++) {
            cout << *it << " ";
        }
        cout << endl;
        
        //修改头部元素的值(front()返回是引用,可以当左值)
        v1.front() = 44;
        
        //输出头部元素
        cout<< "头部元素:" << v1.front() << endl;
        
        //修改尾部的值(back()返回是引用,可以当左值)
        v1.back() = 99;
        
        //输出尾部元素
        cout << "尾部元素" << v1.back() <<endl;
        
        //删除元素(从尾部删除)
        v1.pop_back();
        
        //迭代器遍历打印
        for (vector<int>::iterator it = v1.begin(); it != v1.end(); it++) {
            cout << *it << " ";
        }
        cout << endl;
        
        return 0;
    }
    

    vector的初始化

    vector有4种方式初始化,有直接初始化,也要通过拷贝构造函数初始化。

    int main(int argc, const char * argv[]) {
    
        //直接构造函数初始化
        vector<int> v1;
        v1.push_back(1);
        v1.push_back(2);
        v1.push_back(3);
        v1.push_back(4);
        
        //通过拷贝构造函数初始化
        vector<int> v2 = v1;
        
        //使用部分元素来构造
        vector<int> v3(v1.begin(), v1.begin() + 1);
        vector<int> v4(v1.begin(), v1.end());
        
        //存放三个元素,每个元素都是9
        vector<int> v5(3,9);
        
        return 0;
    }
    

    vector的遍历

    vector的遍历有多种方式,可以根据[]或者迭代器遍历。

    需要主要的是:

    • []方式,如果越界或出现其他错误,不会抛出异常,可能会崩溃,可能数据随机出现
    • at方式,如果越界或出现其他错误,会抛出异常,需要捕获异常并处理
    • 迭代器提供了逆向遍历,可以通过迭代器来实现逆向遍历,当然上面两种方式也可以
    int main(int argc, const char * argv[]) {
        
        //创建vector
        vector<int> v1;
        
        //插入元素
        for (int i = 0; i < 10; i++) {
            v1.push_back(i);
        }
        
        //遍历-[]取值
        for (int i = 0; i < v1.size(); i++) {
            cout << v1[i] << " ";
        }
        cout << endl;
       
        //遍历-at取值
        for (int i = 0; i < v1.size(); i++) {
            cout << v1.at(i) << " ";
        }
        cout << endl;
    
        //遍历-迭代器遍历
        for (vector<int>::iterator it = v1.begin(); it != v1.end(); it++) {
            cout << *it << " ";
        }
        cout << endl;
        
        //遍历-迭代器逆向遍历
        for (vector<int>::reverse_iterator it = v1.rbegin(); it != v1.rend(); it++) {
            cout << *it << " ";
        }
        cout << endl;
        
        //测试越界
        cout << "[]越界:" << v1[20] << endl;      //不会抛出异常,可能会崩溃,可能会乱码
        cout << "at越界:" << v1.at(20) << endl;   //会抛出异常,需要捕获异常
        
        return 0;
    }
    

    vector的push_back强化

    push_back是在当前vector的内存末尾拷贝元素进入容器。注意这个地方可能产生浅拷贝,所以容器中的对象要支持拷贝操作。另外,如果vector初始化了个数,而不初始化具体的值,push_back也只会在最后面追加。

    int main(int argc, const char * argv[]) {
        
        //初始化10个元素的容器
        vector<int> v(10);
        
        //打印容器大小
        cout << v.size() << endl;
        
        //push_back添加元素
        v.push_back(100);
        
        //打印容器大小
        cout << v.size() << endl;
        
        //遍历后的结果是  0 0 0 0 0 0 0 0 0 0 100
        for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
            cout << *it << " ";
        }
        cout << endl;
        
        return 0;
    }
    

    vector的元素删除

    vector的删除,是根据位置进行删除,如果想要删除某个元素,需要找到当前元素的迭代器位置,再进行删除。

    erase(iterator)函数,删除后会返回当前迭代器的下一个位置。

    int main(int argc, const char * argv[]) {
        
        //1 创建容器并初始化
        vector<int> v1(10);
        for (int i = 0; i < v1.size(); i++) {
            v1[i] = i;
        }
        
        //2 区间删除
        //--2.1 删除前3个元素
        v1.erase(v1.begin(), v1.begin() + 3);
        
        //--2.2 删除指定位置的元素
        v1.erase(v1.begin() +3);
        
        //3 根据元素的值进行删除,删除值为2的元素
        v1.push_back(2);
        v1.push_back(2);
        vector<int>::iterator it = v1.begin();
        while (it != v1.end()) {
            if (*it == 2) {
                it = v1.erase(it);   //删除后,迭代器指针会执行下一个位置并返回。
            }else{
                it++;
            }
        }
        
        //4 遍历打印
        for (vector<int>::iterator it = v1.begin(); it != v1.end(); it++) {
            cout << *it << " ";
        }
        cout << endl;
        
        return 0;
    }
    

    vector的插入元素

    vector提供了insert函数,结合迭代器位置插入指定的元素。

    如果迭代器位置越界,会抛出异常。

    int main(int argc, const char * argv[]) {
        
        //初始化vector对象
        vector<int> v1(10);
        
        //在指定的位置插入元素10的拷贝
        v1.insert(v1.begin() + 3, 10);
        
        //在指定的位置插入3个元素11的拷贝
        v1.insert(v1.begin(), 3, 11);
        
        //遍历
        for (vector<int>::iterator it = v1.begin(); it != v1.end(); it++) {
            cout << *it << " ";
        }
        cout << endl;
        
        return 0;
    }
    
    

    STL中的deque容器

    deque是一个双端数组容器:可以在头部和尾部操作元素。

    • push_back 从尾部插入元素
    • push_front 从头部插入元素
    • pop_back 从尾部删除元素
    • pop_front 从头部删除元素

    知识点:

    distance函数可以求出当前的迭代器指针it距离头部的位置,也就是容器的指针

    用法: distance(v1.begin(), it)

    int main(int argc, const char * argv[]) {
        
        //定义deque对象
        deque<int> d1;
        
        //尾部插入元素
        d1.push_back(10);
        d1.push_back(20);
        d1.push_back(30);
        
        //头部插入元素
        d1.push_front(1);
        d1.push_front(2);
        d1.push_front(3);
        
        //尾部删除元素
        d1.pop_back();
        
        //头部删除元素
        d1.pop_front();
        
        //修改头部和尾部的值
        d1.front() = 111;
        d1.back()  = 222;
        
        //查找元素为1的下标
        //通过distance求取下标
        deque<int>::iterator it = d1.begin();
        while (it != d1.end()) {
            if (*it == 1) {
                cout << "下标:" << distance(d1.begin(), it) << endl;
            }
            it++;
        }
        
        //遍历
        for (deque<int>::iterator it = d1.begin(); it != d1.end(); it++) {
            cout << *it << " ";
        }
        cout << endl;
        
        return 0;
    }
    

    STL中的stack栈容器

    在数据结构中,栈是一种先入后出的容器,增加元素叫压栈或者入栈。移除元素通常叫做出栈。

    STL提供的stack容器,也是这种基本类型。这里我们演示一下基本元素类型和复杂元素类型。

    ▽ 基础数据类型的stack

    int main(int argc, const char * argv[]) {
        
        //定义stack对象
        stack<int> s1;
        
        //入栈
        s1.push(1);
        s1.push(2);
        s1.push(3);
        s1.push(4);
        
        //打印栈顶元素,并出栈
        while (!s1.empty()) {
            //取出栈顶元素
            cout << "当前栈顶元素" << s1.top() << endl;
            
            //获取栈的大小
            cout << "当前栈的大小" << s1.size() << endl;
            
            //出栈
            s1.pop();
        }
        
        return 0;
    }
    

    ▽ 复杂数据类型的stack

    //定义类
    class Teacher {
        
    public:
        
        char name[32];
        int  age;
        
        void printT()
        {
            cout << "age = " << age << endl;
        }
        
    };
    
    int main(int argc, const char * argv[]) {
        
        Teacher t1, t2, t3;
        t1.age = 22;
        t2.age = 33;
        t3.age = 44;
        
        //定义栈容器
        stack<Teacher> s1;
        
        //入栈
        s1.push(t1);
        s1.push(t2);
        s1.push(t3);
        
        //出栈并打印
        while (!s1.empty()) {
            //打印栈顶元素
            Teacher tmp = s1.top();
            tmp.printT();
            
            //出栈
            s1.pop();
        }
    
        return 0;
    }
    

    STL中的queue队列容器

    队列是一种数据结构,具备队头和队尾。常见的有FIFO(先入先出)队列等。

    #include <queue>
    
    void main()
    {
        queue<int> q;
        q.push(1);
        q.push(2);
        q.push(3);
        
        cout << "对头元素" << q.front() <<endl;
        cout << "队列的大小 " << q.size() <<endl;
        
        while (!q.empty())�{
        
            int tmp = q.front();
            cout << tmp << " ";
            q.pop();
        }
    }
    
    
    
    class Teacher
    {
    public:
        int age;
        char name[32];
        
        void printT()
        {
            cout << "age :" << age <<endl;
        }
    }
    
    void main()
    {
        Teacher t1,t2,t3;
        t1.age = 31;
        t2.age = 32;
        t3.age = 33;
        
        queue<Teacher > q;
        q.push(t1);
        q.push(t2);
        q.push(t3);
        
        while (!q.empty())�{
        
            Teacher tmp = q.front();
            tmp.printT();
            q.pop();
        }
        
    }
    

    STL中的list容器

    list容器具有如下特性:

    • 可以在头部和尾部插入和删除元素
    • 不能随机访问元素,也就是迭代器只能只能++,不能一次性跳转

    list的基本操作

    int main(int argc, const char * argv[]) {
        
        //创建list对象
        list<int> l;
        
        //尾部添加元素
        for (int i = 0; i < 10; i++) {
            l.push_back(i);
        }
        
        //头部添加元素
        l.push_front(111);
        
        //遍历
        for (list<int>::iterator it = l.begin(); it != l.end(); it++) {
            cout << *it << " ";
        }
        cout << endl;
        
        //list不能随机访问
        list<int>::iterator it = l.begin();
        it++;
        it++;
        cout << *it <<endl;
    //    it = it + 1;  //编译报错,不能随机访问
    //    it = it + 5;  //编译报错,不能随机访问
        
        
        return 0;
    }
    

    list的删除

    list提供了两个函数用来删除元素,分别是eraseremove

    • erase是通过位置或者区间来删除,主要结合迭代器指针来操作
    • remove是通过值来删除
    int main(int argc, const char * argv[]) {
        
        //创建list对象
        list<int> l;
        
        //添加数据
        for (int i = 0; i < 10; i++) {
            l.push_back(i);
        }
        l.push_back(100);
        l.push_back(100);
        
        //删除头部元素
        l.erase(l.begin());
        
        //删除某个区间
        list<int>::iterator it = l.begin();
        it++;
        it++;
        it++;
        l.erase(l.begin(), it);
        
        //移除值为100的所有元素
        l.remove(100);
        
        //遍历
        for (list<int>::iterator it = l.begin(); it != l.end(); it++) {
            cout << *it << " ";
        }
        cout << endl;
        
        return 0;
    }
    

    STL中的priority_queue优先级队列容器

    优先级队列分为:最小值优先队列和最大值优先队列。

    此处的最大值、最小值是指队头的元素(增序、降序)。默认,是创建最大值优先级队列。

    定义优先级的方法:

    • priority_queue<int>默认定义int类型的最大值队列
    • priority_queue<int, vector<int>, less<int>>定义int型的最大值优先队列
    • priority_queue<int, vector<int>, greater<int>>定义int型的最小值队列

    上面的定义中,lessgreater相当于谓词,是预定义好的排序函数,我们称之为“仿函数”。后面会介绍它的用法。

    void main()
    {
        //定义优先级队列(默认是最大值优先级队列)
        priority_queue<int> p1;
        
        //定义一个最大优先级队列
        //less是提前定义好的预定义函数 相当于谓词
        priority_queue<int, vector<int>, less<int>> p2;
        
        //定义一个最小值优先级队列v
        priority_queue<int, vector<int>, greater<int>> p3;
        
        //给默认的最大优先级队列入栈
        p1.push(33);
        p1.push(11);
        p1.push(55);
        p1.push(22);
        
        //打印最大优先级的对头元素
        cout<<"对头元素:"<< p1.top() <<endl;
        cout<<"队列的大小:"<< p1.size() <<endl;
        
        //给最小值优先级队列入栈
        p3.push(33);
        p3.push(11);
        p3.push(55);
        p3.push(22);
        
        //打印最小优先级队列的对头元素
        cout<<"对头元素:"<< p3.top() <<endl;
        cout<<"队列的大小:"<< p3.size() <<endl;
        
    }
    

    STL中的set和multiset集合容器

    set是一个集合,Objective-C语言中也有集合的概念。C++中的集合与OC中的集合也有不同的地方。

    • C++的set容器,其中包含的元素是唯一的,而且是有序的。
    • C++的set容器,是按照顺序插入的,不能在指定位置插入。
    • C++的set容器,其结构是红黑二叉树,插入数据的效率比vector快

    set元素的插入和删除

    set提供了inserterase函数,用来对元素进行插入和删除操作。

    • 基础类型数据,如果插入的是重复的元素,则插入失败,返回值是一个pair类型
    • pair类型类似于swift语言中的元组的概念,通过其判断是否插入成功
    • 复杂类型数据,需要通过仿函数来确定元素的顺序,进入判断是否是重复元素。在“自定义对象的排序”里面讲解。
    void main()
    {
        set<int> set1;
        
        //插入元素
        for (int i = 0; i<5; i++) {
            int tmp = rand();
            set1.insert(tmp);
        }
        
        //重复插入元素(会插入不成功,下一节会分析如果根据返回值判断是否插入成功)
        set1.insert(100);
        set1.insert(100);
        set1.insert(100);
        set1.insert(100);
        
        for (set<int>::iterator it = set1.begin(); it != set1.end(); it++) {
            cout << *it <<" ";
        }
        
        
        //删除集合
        while(!set1.empty())
        {
            //获取头部
            set<int>::iterator it = set1.begin();
            
            //打印头部元素
            cout << *it << endl;
            
            //从头部删除元素
            set1.erase(set1.begin());
        }
        
    }
    

    普通数据类型的排序

    set容器是有序的集合,默认的顺序是从小到大的。

    创建集合的方式:

    • set<int>创建默认的从小到大的int类型的集合
    • set<int,less<int>>创建一个从小打到大的int类型的集合
    • set<int,greater<int>>创建一个从大到小的int类型的集合

    上面的less和greater就是仿函数,集合会根据这个仿函数的返回值是否为真类进行排序。

    //仿函数的原型,下面是C++提供的默认的greater的仿函数(删除了宏定义后的)
    struct greater
    {
        bool operator()(const int &left, const int &right) const
        {
            //如果左值>右值,为真。从大到小的排列
            return left > right;
        }
    };
    

    我们可以测试下,添加进set集合的元素确实是有顺的。

    void main()
    {
        //默认,从小到大
        set<int> set1;
        //从小到大--默认就是
        set<int, less<int>> set2;
        //从大到小
        set<int, greater<int>> set3;
    
        //添加元素
        for (int i = 0; i < 5; i++) {
            int tmp = rand();
            set3.insert(tmp);
        }
        
        //遍历
        for (set<int>::iterator it = set3.begin(); it != set3.end(); it++) {
            cout<< *it << " ";
        }
    }
    

    自定义对象的排序

    上面,我们看到了基础的数据类型的集合,是可以排序的。但是,如果集合里面放的是特殊的自定义对象,该如何满足set有序的特性呢?

    通过上面的例子,我们知道,基础数据类型的set是有序的关键原因是greater和less仿函数。所以,自定义对象的有序也是通过我们自定义仿函数来保证的。

    仿函数,之所以叫仿函数,是因为它跟函数很像,但并不是一个函数。它的结果如下,只要我们实现了这个仿函数,我们也可以对自定义对象进行排序。

    //定义仿函数的结构体
    struct FunctionName
    {
        //重载了()运算符,实现两个自定义对象的比较
        bool opeartor() (Type &left, Type &right)
        {
            //左值大于右值,从大到小的顺序
            if(left > right) 
                return true;
            else
                return false;
            
        }
    };
    
    

    下面,我们自定义一个Student对象,根据年龄进行排序,将对象加入到set集合中,并进行打印。

    如果仿函数实现了根据年龄进行排序,因为set是元素唯一的,所以在插入对象的时候,如果年龄是重复的,则插入不进去了。

    //定义student对象
    class Student {
    public:
        Student(const char *name, int age)
        {
            strcpy(this->name, name);
            this->age = age;
        }
        
    public:
        char name[64];
        int  age;
    };
    
    //提供仿函数,用于自定义对象的set进行排序,要写一个仿函数,用来排序
    struct FuncStudent
    {
        //重载了括号操作符,用来比较大小
        bool operator() (const Student &left, const Student &right)
        {
            //如果左边比右边小,从小到大按照年龄排序
            if(left.age < right.age)
                return true;
            else
                return false;
        }
        
    };
    
    void main()
    {
        Student s1("s1",32);
        Student s2("s2",22);
        Student s3("s3",44);
        Student s4("s4",11);
        Student s5("s5",22); 
        
        //创建集合,采用从小到大的排序
        set<Student, FuncStudent> set1;
        
        //插入数据
        set1.insert(s1);
        set1.insert(s2);
        set1.insert(s3);
        set1.insert(s4);
        //插入不进去(年龄有重复的,所以插不进去了),要通过返回值来确保是否插入成功
        set1.insert(s5);    
        
        //遍历
        for (set<Student>::iterator it = set1.begin(); it != set1.end(); it++) {
            cout << it->age << "\t" << it->name <<endl;
        }
        
    }
    

    pair类型的返回值

    pair类型,就类似于Swift语言中的“元组”的概念,这个类型包含了多个数据类型,在函数返回的时候,可以同时返回多个值。

    我们来看一下pair类型的定义它实际上是一个结构体。它包含了两个属性,firstsecond

    template <class _T1, class _T2>
    struct pair
    {
        typedef _T1 first_type;
        typedef _T2 second_type;
    
        _T1 first;
        _T2 second;
    }
    

    上面的例子中,我们知道set集合中的元素是唯一的,重复的元素插入会失败。如果判断是否插入成功,我们可以通过insert函数的返回值来判断,它的返回值是一个pair类型。我们来看一下insert函数的原型:

    pair<iterator,bool> insert(const value_type& __v)
    

    返回的是pair<iterator, bool>类型,pair的第一个属性表示当前插入的迭代器的位置,第二个属性表示插入是否成功的bool值。所以,我们可以通过第二个属性来判断元素是否插入成功。

    //pair的使用判断set的insert函数的返回值
    void test3()
    {
        Student s1("s1",32);
        Student s2("s2",22);
        Student s3("s3",44);
        Student s4("s4",11);
        Student s5("s5",22);
        
        //创建集合,采用从小到大的排序
        set<Student, FuncStudent> set1;
    
        //插入数据,接收返回值
        pair<set<Student, FuncStudent>::iterator, bool> pair1 = set1.insert(s1);
        if (pair1.second == true) {
            cout << "插入s1成功" <<endl;
        }else{
            cout << "插入s1失败" <<endl;
        }
    }
    

    set容器数据的查找

    set容器提供了多个函数用来查找元素

    • iterator find(const key_type& __k) find函数查找元素为k的迭代器位置
    • iterator lower_bound(const key_type& __k) lower_bound函数查找小于等于元素k的迭代器位置
    • iterator upper_bound(const key_type& __k) upper_bound函数查找大于元素k的迭代器位置
    • pair<iterator,iterator> equal_range(const key_type& __k) equal_range函数返回一个pair类型,第一个属性表示大于等于k的迭代器位置,第二个是大于k的迭代器位置
    void test4()
    {
        set<int> set1;
        
        for (int i = 0; i < 10; i++) {
            set1.insert(i+1);
        }
        
        //遍历
        for (set<int>::iterator it = set1.begin(); it != set1.end(); it++) {
            cout << *it <<endl;
        }
        
        //查找元素是5的迭代器位置
        set<int>::iterator it0 = set1.find(5);
        cout << "it0:" << *it0 <<endl;
        
        //查找小于等于5的元素迭代器位置
        set<int>::iterator it1 = set1.lower_bound(5);
        cout << "it1:" << *it1 <<endl;
        
        //查找大于5的元素迭代器位置
        set<int>::iterator it2 = set1.upper_bound(5);
        cout << "it2:" << *it2 <<endl;
        
        //返回的pair第一个迭代器是>=5,另一个是>5
        pair<set<int>::iterator, set<int>::iterator> mypair = set1.equal_range(5);
        set<int>::iterator it3 = mypair.first;
        set<int>::iterator it4 = mypair.second;
        cout << "it3:" << *it3 <<endl;
        cout << "it4:" << *it4 <<endl; 
    }
    

    multiset容器

    multiset容器,与set容器相似,但是multiset容器中的元素可以重复。另外,他也是自动排序的,容器内部的值不能随便修改,因为有顺序的。

    void test5()
    {
        //定义multiset
        multiset<int> set1;
        
        //从键盘不停的接收值
        int tmp = 0;
        printf("请输入multiset集合的值:");
        scanf("%d", &tmp);
        while (tmp != 0) {
            set1.insert(tmp);
            scanf("%d", &tmp);
        }
        
        //迭代器遍历
        for (multiset<int>::iterator it = set1.begin(); it != set1.end(); it++) {
            cout<< *it <<" ";
        }
        cout <<endl;
       
        //删除
        while (!set1.empty()) {
            multiset<int>::iterator it = set1.begin();
            cout << *it << " ";
            set1.erase(it);
        }
    }
    

    STL中的map和multimap映射容器

    map和multimap是一个键值映射的容器。map中的键值对都是唯一的,但是multimap中一个键可以对应多个值。

    • map和multimap是关联式容器,键值成对存在
    • map和multimap是红黑变体的平衡二叉树结构
    • map只支持唯一的键值对,集合中的元素是按照一定的顺序排列的
    • multimap中的键可以出现多次
    • map和multimap的元素插入过程是按照顺序插入的

    map元素的增删改查

    map元素的插入,有两种方式:

    1. 调用insert函数插入pair类型的键值对
    2. 直接使用[]来对键进行复制,类似于Objective-C中的NSMutableDictionary赋值一样。

    map的insert函数返回的是pair类型,pair的第二个参数表示是否插入成功。如果插入的元素键名相同,则插入失败。

    map元素的删除,跟上面其他的容器一样,都是直接调用erase函数.

    int main()
    {
        map<int, string> map1;
        
        //insert方法插入
        //--1 通过pair<int, string>(1,”chenhua“) 构造pair元素
        map1.insert(pair<int, string>(1,"chenhua"));
        //--2 通过make_pair构造pair元素
        map1.insert(make_pair(2,"mengna"));
        //--3 通过value_type构造pair元素
        map1.insert(map<int, string>::value_type(3,"chenmeng"));
        
        //[]直接插入
        map1[4] = "menghua";
        
        //重复插入(插入会不成功)
        pair<map<int, string>::iterator, bool> pair1 = map1.insert(make_pair(2, "haha"));
        if (pair1.second) {
            cout << "重复插入成功" << endl;
        }else{
            cout << "重复插入失败" << endl;
        }
        
        //元素的修改
        //map[1] = "22"的方式,如果不存在键则插入,存在键则修改
        map1[2] = "haha";
        
        //元素的删除
        //--删除值为"haha"的元素
        for (map<int, string>::iterator it = map1.begin(); it != map1.end(); it++) {
            if (it->second.compare("haha") == 0) {
                map1.erase(it);
            }
        }
        
        //遍历
        for (map<int, string>::iterator it = map1.begin(); it != map1.end(); it++) {
            cout << it->first << "\t" << it->second << endl;
        }
        
        return 0;
    }
    

    map元素的查找

    map提供了两个函数进行key的查找:find和equal_range。

    int main()
    {
        //定义map
        map<int ,string> map1;
        map1[1] = "chenhua";
        map1[2] = "mengna";
        
        //查找key=100的键值对
        map<int, string>::iterator it = map1.find(100);
        if (it != map1.end()) {
            cout << "存在key=100的键值对";
        }else{
            cout << "不存在" << endl;
        }
        
        
        //查找key = 1000的位置
        //返回两个迭代器,第一个表示<=1000的迭代器位置,第二个是>1000的迭代器位置
        pair<map<int, string>::iterator, map<int, string>::iterator> mypair = map1.equal_range(1000);
        if (mypair.first == map1.end()) {
            cout << "大于等于5的位置不存在" << endl;
        }else{
            cout << mypair.first->first << "\t" << mypair.first->second << endl;
        }
        
        if (mypair.second == map1.end()) {
            cout << "大于5的位置不存在" << endl;
        }else{
            cout << mypair.second->first << "\t" << mypair.second->second << endl;
        }
        
        return 0;
    }
    

    multimap容器

    multimap容器,与map容器的唯一区别是:multimap支持多个键值。

    由于支持多个键值,multimap提供了cout函数来计算同一个key的元素个数。

    class Person {
        
        
    public:
        
        string name;    //姓名
        int age;        //年龄
        string tel;     //电话
        double sal;     //工资
        
    };
    
    void test()
    {
        Person p1,p2,p3,p4,p5;
        p1.name = "王1";
        p1.age  = 31;
        
        p2.name = "王2";
        p2.age  = 31;
        
        p3.name = "张3";
        p3.age  = 31;
        
        p4.name = "张4";
        p4.age  = 31;
        
        p5.name = "钱5";
        p5.age  = 31;
        
        
        multimap<string, Person> map2;
        
        //sale部门
        map2.insert(make_pair("sale", p1));
        map2.insert(make_pair("sale", p2));
        
        //development部门
        map2.insert(make_pair("development", p3));
        map2.insert(make_pair("development", p4));
        
        //Finanncial部门
        map2.insert(make_pair("Finanncial", p5));
        
        
        //遍历
        for (multimap<string, Person>::iterator it = map2.begin(); it != map2.end(); it++) {
            
            
            cout << it->first << "\t" << it->second.name << endl;
            
        }
        
        //按部门显示员工信息
        int developNum = (int) map2.count("development");
        cout << "development部门人数:" << developNum << endl;
        multimap<string,Person>::iterator it2 = map2.find("development");
        int tag = 0;
        while (it2 != map2.end() && tag < developNum) {
            cout << it2->first << "\t" << it2->second.name <<endl;
            it2 ++;
            tag ++;
        }
        
        //把age=32 修改name= 32
        for (multimap<string, Person>::iterator it = map2.begin(); it != map2.end(); it++) {
            if (it->second.age == 32) {
                it->second.name = "32";
            }
        }
    }
    
    int main(int argc, const char * argv[]) {
     
        test();
        
        return 0;
    }
    

    STL容器的通用性探究

    到这里,STL的容器我们基本讲解完毕了。STL的容器主要利用了C++的模板特性来实现。需要注意:

    • 容器缓存了节点,节点类要确保支持拷贝(否则出现浅拷贝问题,导致崩溃)
    • 容器中的一般节点类,需要提供拷贝构造函数,并重载等号操作符(用来赋值)
    • 容器在插入元素时,会自动进行元素的拷贝。

    针对容器,容器之间也支持拷贝。所以需要注意:

    • 除了queue和stack外,每个容器都提供了可返回迭代器的函数,运用返回的跌打器就可以访问元素
    • 通常STL不会抛出异常,要求使用者确保传入正确的参数
    • 每个容器都提供了一个默认构造函数和一个默认拷贝构造函数

    STL容器的元素拷贝

    下面,我们演示一下,如果容器元素如果没有实现拷贝构造函数,出现浅拷贝后的崩溃问题。

    #include <iostream>
    #include <string>
    #include <vector>
    using namespace std;
    
    
    class Student {
        
    public:
        Student(const char *name, int age)
        {
            cout << "构造函数" << endl;
            
            //分配内存空间
            m_name = new char[strlen(name) + 1];
            //值拷贝
            strcpy(m_name, name);
            
            m_age = age;
        }
        
        
        ~Student()
        {
            printf("%p 指向的空间 调用析构函数\n", m_name);
            if (m_name != NULL) {
                delete []m_name;
                m_age = 0;
            }
        }
        
    private:
        char *m_name;
        int   m_age;
        
    };
    
    
    int main()
    {
        Student s1("chenhua",24);
        
        vector<Student> v1;
        v1.push_back(s1);
        
        return 0;
    }
    

    上面的代码段,运行后的结果如下:

    构造函数
    0x100302a00 指向的空间 调用析构函数
    0x100302a00 指向的空间 调用析构函数
    

    运行后,打印出结果后并报错。报错原因是同一个内存空间被释放了2次,导致的崩溃。其根本原因是,v1将s1拷贝到容器,由于Student没有重写拷贝构造函数,从而出现了浅拷贝,只拷贝了地址。释放的时候毫无疑问出现错误。

    如果我们给Student重写了拷贝构造函数和重载了等号操作符,则上面的错误就不会出现。

    //重写拷贝构造函数
    Student(const Student &obj)
    {
        //分配内存空间
        m_name = new char[strlen(obj.m_name) + 1];
        //值拷贝
        strcpy(m_name, obj.m_name);
        
        m_age = obj.m_age;
    }
        
    //重载等号运算符
    Student & operator=(const Student &obj)
    {
        //释放旧值
        if (m_name != NULL) {
            delete [] m_name;
            m_age = 0;
        }
        
        //分配内存空间并赋值
        m_name = new char[strlen(obj.m_name) + 1];
        strcpy(m_name, obj.m_name);
        m_age = obj.m_age;
        
        return *this;
    }
    

    STL容器的比较

    STL提供了很多容器,每种容器有其自身的特点,我们该如何使用它们呢?

     vectordequelistsetmutlisetmapmultimap
    内存结构单端数组双端数组双向链表二叉树二叉树二叉树二叉树
    随机存取对key而言是
    查找速度非常慢对key而言快对key而言快
    插入删除尾端头尾两端任何位置---$1
    展开全文
  • 主要介绍了C++ STL容器stack和queue详解的相关资料,需要的朋友可以参考下
  • C++STL容器总结

    万次阅读 多人点赞 2019-02-27 16:34:46
    持续更新中!!! 各大容器的特点: ...1.可以用下标访问的容器有(既可以插入也可以赋值):vector、deque、map; 特别要注意一下,vector和deque如果没有预先指定大小,是不能用下标法插入元素的...

    各大容器的特点:

    1.可以用下标访问的容器有(既可以插入也可以赋值):vector、deque、map;

    特别要注意一下,vector和deque如果没有预先指定大小,是不能用下标法插入元素的!

    2. 序列式容器才可以在容器初始化的时候制定大小,关联式容器不行;

    3.注意,关联容器的迭代器不支持it+n操作,仅支持it++操作。

                                                              序列式容器:

    一、vector

    当需要使用数组的情况下,可以考虑使用vector

     1.特点:

     (1) 一个动态分配的数组(当数组空间内存不足时,都会执行: 分配新空间-复制元素-释放原空间);

     (2) 当删除元素时,不会释放限制的空间,所以向量容器的容量(capacity)大于向量容器的大小(size);

     (3) 对于删除或插入操作,执行效率不高,越靠后插入或删除执行效率越高;

     (4) 高效的随机访问的容器。

     

     2.创建vecotr对象:

     (1) vector<int> v1;

     (2) vector<int> v2(10);  

     

     3.基本操作:

     v.capacity();  //容器容量

     v.size();      //容器大小

     v.at(int idx); //用法和[]运算符相同

     v.push_back(); //尾部插入

     v.pop_back();  //尾部删除

     v.front();     //获取头部元素

     v.back();      //获取尾部元素

     v.begin();     //头元素的迭代器

     v.end();       //尾部元素的迭代器

     v.insert(pos,elem); //pos是vector的插入元素的位置

     v.insert(pos, n, elem) //在位置pos上插入n个元素elem

     v.insert(pos, begin, end);

     v.erase(pos);   //移除pos位置上的元素,返回下一个数据的位置

     v.erase(begin, end); //移除[begin, end)区间的数据,返回下一个元素的位置

     

     reverse(pos1, pos2); //将vector中的pos1~pos2的元素逆序存储

     

     

     

    二分查找

    #include<iostream>

    #include<algorithm>

    #include<vector>

    #include<deque>

    #include<map>

    #include<cstring>

    using namespace std;

    int  main()

    {

        vector<int> v(10);

        int num;

        vector<int>::iterator beg = v.begin();

        vector<int>::iterator end = v.end();

        vector<int>::iterator mid = v.begin() + (end - beg) / 2;

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

        {

             v[i] = i;

        }

        cin >> num;

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

        while (*mid != num &&  beg <= end)

        {

             if (num < *mid)

             {

                 end = mid;

             }

             else

             {

                 beg = mid + 1;

             }

             mid = beg + (end - beg) / 2;

        }

        if (*mid == num)

        {

             cout << "Find" << endl;

        }

        else

        {

             cout << "Not Find" << endl;

        }

        return 0;

    }

     二、deque

    1.特点:

    (1) deque(double-ended queue 双端队列);

    (2) 具有分段数组、索引数组, 分段数组是存储数据的,索引数组是存储每段数组的首地址;

    (3) 向两端插入元素效率较高!

        (若向两端插入元素,如果两端的分段数组未满,既可插入;如果两端的分段数组已满,

        则创建新的分段函数,并把分段数组的首地址存储到deque容器中即可)。

        中间插入元素效率较低!

     

    2. 创建deque对象

    (1) deque<int> d1;

    (2) deque<int> d2(10);

     

    3. 基本操作:

    (1) 元素访问:

    d[i];

    d.at[i];

    d.front();

    d.back();

    d.begin();

    d.end();

     

    (2) 添加元素:

    d.push_back();

    d.push_front();

    d.insert(pos,elem); //pos是vector的插入元素的位置

    d.insert(pos, n, elem) //在位置pos上插入n个元素elem

    d.insert(pos, begin, end);

     

    (3) 删除元素:

    d.pop_back();

    d.pop_front();

    d.erase(pos);   //移除pos位置上的元素,返回下一个数据的位置

    d.erase(begin, end); //移除[begin, end)区间的数据,返回下一个元素的位置

     

    三、list

    1. 特点:

    (1) 双向链表

     

    2.创建对象:

    list<int> L1;

    list<int> L2(10);

     

    3.基本操作:

    (1) 元素访问:

    lt.front();

    lt.back();

    lt.begin();

    lt.end();

     

    (2) 添加元素:

    lt.push_back();

    lt.push_front();

    lt.insert(pos, elem);

    lt.insert(pos, n , elem);

    lt.insert(pos, begin, end);

     

    lt.pop_back();

    lt.pop_front();

    lt.erase(begin, end);

    lt.erase(elem);

     

    (3)sort()函数、merge()函数、splice()函数:

    sort()函数就是对list中的元素进行排序;

    merge()函数的功能是:将两个容器合并,合并成功后会按从小到大的顺序排列;

    比如:lt1.merge(lt2); lt1容器中的元素全都合并到容器lt2中。

    splice()函数的功能是:可以指定合并位置,但是不能自动排序!

     

    这些函数用到的次数较少,要用时再加深印象!!!

     

                                                                关联式容器:

    1. 特点:

    (1) 关联式容器都是有序的,升序排列,自动排序;

    (2) 实现的是一个平衡二叉树,每个元素都有一个父节点和两个子节点,

    左子树的所有元素都比自己小,右子树的所有元素都比自己大;

     

    四、set/multiset

    1. 特点:

    构造set集合的主要目的是为了快速检索,去重与排序

    (1) set存储的是一组无重复的元素,而multiset允许存储有重复的元素;

    (2) 如果要修改某一个元素值,必须先删除原有的元素,再插入新的元素。

     

    2.创建对象:

    set<T> s;

    set<T, op(比较结构体)> s;     //op为排序规则,默认规则是less<T>(升序排列),或者是greater<T>(降序规则)。

    函数对象:

    class Sum

    {

    public:

        int operator()(int a, int b){return a+b;}

    };

     

    Sum sum;  //利用了()运算符的重载

     

    3. 基本操作:

    s.size();      //元素的数目

    s.max_size();  //可容纳的最大元素的数量

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

    s.find(elem);  //返回值是迭代器类型

    s.count(elem); //elem的个数,要么是1,要么是0,multiset可以大于一

    s.begin();

    s.end();

    s.rbegin();

    s.rend();

    s.insert(elem);

    s.insert(pos, elem);

    s.insert(begin, end);

    s.erase(pos);

    s.erase(begin,end);

    s.erase(elem);

    s.clear();//清除a中所有元素;

     

    pair类模板

    1. 主要作用是将两个数据组成一个数据,用来表示一个二元组或一个元素对,

    两个数据可以是同一个类型也可以是不同的类型。

    当需要将两个元素组合在一起时,可以选择构造pair对象,

    set的insert返回值为一个pair<set<int>::iterator,bool>。bool标志着插入是否成功,而iterator代表插入的位置,若该键值已经在set中,则iterator表示已存在的该键值在set中的位置。

    如:set<int> a;

               a.insert(1);

               a.insert(2);

               a.insert(2);//重复的元素不会被插入;

     

    注意一下:make_pair()函数内调用的仍然是pair构造函数

     

    set中的erase()操作是不进行任何的错误检查的,比如定位器的是否合法等等,所以用的时候自己一定要注意。

    创建pair对象:

    pair<int, float> p1;   //调用构造函数来创建pair对象

    make_pair(1,1.2);      //调用make_pair()函数来创建pair对象

     

    pair对象的使用:

    pair<int, float> p1(1, 1.2);

    cout<< p1.first << endl;

    cout<< p1.second << endl;

     

    顺序遍历:

    set<int> a;

    set<int>::iterator it=a.begin();

    for(;it!=a.end();it++)

        cout<<*it<<endl;

     

    反序遍历:

    set<int> a;

    set<int>::reverse_iterator rit=a.rbegin();

    for(;rit!=a.rend();rit++)

    cout<<*rit<<endl;

     

    find(key_value);//如果找到查找的键值,则返回该键值的迭代器位置,否则返回集合最后一个元素后一个位置的迭代器,即end();

    如:int b[]={1,2,3,4,5};     set<int> a(b,b+5);

            set<int>::iterator it;

            it=a.find(3);

            if(it!=a.end())  cout<<*it<<endl;

            else cout<<“该元素不存在”<<endl;

            it=a.find(10);

            if(it!=a.end())  cout<<*it<<endl;

            else cout<<“该元素不存在”<<endl;

     

    定义比较函数

         set容器在判定已有元素a和新插入元素b是否相等时,是这么做的:

    (1)将a作为左操作数,b作为右操作数,调用比较函数,并返回比较值 ;

    (2)将b作为左操作数,a作为右操作数,再调用一次比较函数,并返回比较值。

         也就是说,假设有比较函数f(x,y),要对已有元素a和新插入元素b进行比较时,会先进行f(a,b)操作,再进行f(b,a)操作,然后返回两个bool值。

    如果1、2两步的返回值都是false,则认为a、b是相等的,则b不会被插入set容器中;

    如果1返回true而2返回false,那么认为b要排在a的后面,反之则b要排在a的前面;

    如果1、2两步的返回值都是true,则可能发生未知行为。

     

    (1)自定义比较结构体;

    首先,定义比较结构体

    struct myComp

    {

         bool operator() (const 类型 &a, const 类型 &b)//重载“()”操作符

              {

                     ……

                    return  ……;

              }

    };

    然后,定义set:

    set<类型,myComp> s;

     

    (2)重载“<”操作符

    首先,在结构体中,重载“<”操作符,自定义排序规则

    struct 结构体

    {

            bool operator < (const 结构体类型 &a)

            {

                   ……

                   return(…);

             }

    };

    然后,定义set

    set<类型> s;

     

    【第四届蓝桥杯预选赛】错误票据

    题目描述:

    某涉密单位下发了某种票据,并要在年终全部收回。

    每张票据有唯一的ID号。全年所有票据的ID号是连续的,但ID的开始数码是随机选定的。

    因为工作人员疏忽,在录入ID号的时候发生了一处错误,造成了某个ID断号,另外一个ID重号。

    你的任务是通过编程,找出断号的ID和重号的ID。

    假设断号不可能发生在最大和最小号。

    要求程序首先输入一个整数N(N<100)表示后面数据行数。

    接着读入N行数据。

    每行数据长度不等,是用空格分开的若干个(不大于100个)正整数(不大于100000)

    每个整数代表一个ID号。

    要求程序输出1行,含两个整数m n,用空格分隔。

    其中,m表示断号ID,n表示重号ID

    输入:

    要求程序首先输入一个整数N(N<100)表示后面数据行数。

    接着读入N行数据。

    每行数据长度不等,是用空格分开的若干个(不大于100个)正整数(不大于100000)

    每个整数代表一个ID号。

    输出:

    要求程序输出1行,含两个整数m n,用空格分隔。

    其中,m表示断号ID,n表示重号ID

     

    样例输入:

    2

    5 6 8 11 9

    10 12 9

    样例输出:

    7 9

    五、map/multimap

    去重类问题

    可以打乱重新排列的问题

    有清晰的一对一关系的问题

    1. 特点:

    (1) map为单重映射、multimap为多重映射;

    (2) 主要区别是map存储的是无重复键值的元素对,而multimap允许相同的键值重复出现,既一个键值可以对应多个值。

    (3) map内部自建了一颗红黑二叉树,可以对数据进行自动排序,所以map里的数据都是有序的,这也是我们通过map简化代码的原因。

    (4)自动建立key-value的对应关系,key和value可以是你需要的任何类型。

    (5) key和value一一对应的关系可以去重。

     

    2. 创建对象:

    map<T1,T2> m;

    map<T1,T2, op> m;  //op为排序规则,默认规则是less<T>

     

    3. 基本操作:

    m.at(key);

    m[key];

    m.count(key);

    m.max_size(); //求算容器最大存储量

    m.size();  //容器的大小

    m.begin();

    m.end();

    m.insert(elem);

    m.insert(pos, elem);

    m.insert(begin, end);

     

    注意一下:该容器存储的是键值对,所以插入函数与其他容器稍有不同

    (1) 使用pair<>构造键值对对象

    map<int, float> m;

    m.insert(pair<int, float>(10,2.3));

     

    (2)使用make_pair()函数构建键值对对象

    map<int,float> m;

    m.insert(make_pair(10,2.3));

     

    (2) 使用value_type标志

    map<int, float> m;

    m.insert(map<int,float>::value_type(10,2.3));

     

    m[key] = value;   //m只能是map容器,不适用于multimap

     

    m.erase(pos);

    m.erase(begin,end);

    m.erase(key);

     

    使用 begin()和end()遍历map

     

    使用数组的方法遍历map

     

    使用find()查找

    用find函数来定位数据出现位置它返回的一个迭代器。

    当数据出现时,它返回数据所在位置的迭代器。

    如果map中没有要查找的数据,它返回的迭代器等于end函数返回的迭代器。

     

    map在题目中的应用

     

    去重:利用映射的一一对应性,把可能出现重复的数据设置为key值以达到去重的目的。

    排序:自定义Compare类(依葫芦画瓢)

    比如我建了一个学生-成绩的map,原先是按照学生名字的字典序              

    排序的。  

    如果我想按照降序呢?学生姓名长度呢?

    按照默认cmp的输出:

    降序输出:

    自定义cmp按照长度升序输出:

     

    计数

    假设定义一个map<string,int>map1,输入数据s,记为first,如果这个数据存在,map1[s]++;如果不存在,map1[s]=1;

    展开全文
  • 众所周知,STL容器不是线程安全的。对于vector,即使写方(生产者)是单线程写入,但是并发读的时候,由于潜在的内存重新申请和对象复制问题,会导致读方(消费者)的迭代器失效。实际表现也就是招致了core dump。...
  • 深度解析C++ STL容器vector原理及用法

    千次阅读 多人点赞 2021-12-31 15:13:50
    vector是表示可以改变大小的数组的序列容器. 就像数组一样,向量为它们的元素使用连续的存储位置,这意味着它们的元素也可以使用指向其元素的常规指针上的偏移量来访问,并且与在数组中一样有效. 但与数组不同的是,...
  • C++STL容器大全

    2020-03-23 11:12:55
    STL(标准模板库),是目前C++内置支持的library。它的底层利用了C++类模板和函数模板的机制,由三大部分组成:容器、算法和迭代器。 目前STL有六大组件 容器 container 算法 algorthm 迭代器 iterator 仿函数 ...
  • C++ STL容器底层实现原理

    千次阅读 多人点赞 2019-03-16 00:13:39
    1、vector 容器 vector 的数据安排以及操作方式,与 array 非常相似。两者的唯一区别在于空间的运用的灵活性。array 是静态空间,一旦配置了就不能改变,vector 是动态数组。在堆上分配空间。vector 是动态空间,...
  • } STL容器 vector 翻转 reverse(v.begin(), v.end()); 遍历 vector<Student> student; for (auto &x:student) { // 带上引用可以避免重复复制,降低时间成本消耗 } for(int i = 0; i (); i++) { // 根据下标遍历 ...
  • 从实现的角度来看,STL容器是一种class template 2、算法(algorithms):各种算法如sort,search,copy,earse。STL算法是一种 function template。 3、迭代器(iterators):扮演容器与算法之间的胶合剂,是所谓的...
  • 里我们不涉及容器的基本操作之类,只是要讨论一下各个容器其各自的特点。STL中的常用容器包括:顺序性容器(vector、deque、list)、关联容器(map、set)、容器适配器(queue、stac)
  • Windows中VS code无法查看C++ STL容器的值 Windows中VS code debug时无法查看C++ STL容器内容 本文阅读重点< 1Windows中VS code debug时无法查看C++ STL容器内容 1.1而我相应的配置文件如下: ...
  • C++ STL容器中不能存储引用类型的原因 在正式说明问题之前,先介绍一个概念:在 C++ 中,不能声明或定义指向引用的指针。 那为什么不能定义指向引用的指针呢?原因如下: 从设计目的上来讲,设计引用的目的是为了...
  • C++ STL容器—— pair 用法详解 写在前面:用简单的语言介绍C++容器的基本成员函数, 外加实际的例子,并不涉及原理。最好的方法还是需要自己上手操作一下. 写的不好, 请大神手下留情. 下面说的 “运行之后” 表示:...
  • C++STL容器排序查找效率测试

    千次阅读 2020-03-15 00:45:51
  • C++ STL容器总结之vector(超详细版)

    万次阅读 2020-02-20 23:01:00
    vector的中文翻译为向量,是一种C++ STL中的序列容器。它的是存储方式和C++语言本身提供的数组一样都是顺序存储,因此vector的操作和数组十分相似。但是和数组不一样的是,数组的存储空间是静态的,一旦配置了就不能...
  • c++ STL容器的内存分配

    千次阅读 2016-10-27 23:59:59
    要了解问题的原因,我们就要了解C++stl容器的内存分配策略。我们才知道在哪些操作下可能导致迭代器失效,引用(指针)失效。二.问题分类首先我们把以上的问题分成两类: 容器的迭代器为什么会失效? 容器元素的引用...
  • c++STL容器讲义与演示

    2018-01-25 16:04:17
    c++STL容器讲义与演示,对STL初学者帮助很大。。。。。。
  • 参考文献: 【1】迭代器失效问题:STL容器如何正确删除元素(迭代器失效问题) - 划水程序员 - 博客园 【2】C++迭代器失效的几种情况总结:C++迭代器失效的几种情况总结 - Boblim - 博客园 【3】C++容器和迭代器:...
  • C++STL容器共通操作之初始化(Initialization) ** c++stl每个容器都提供了一个default构造函数,一个copy构造函数和一个析构函数。你可以以某个已知区间的内容作为容器初始值,自c++11起你也可以指定一个初值列...
  • STL 就是所谓的标准模板库(Standard Template Library),这可能是C++程序员的一大利器。 总的来说,STL包括几个部分:容器,算法(泛型算法),迭代器三个主要部分(当然还包含仿函数,适配器等其他部分),下...
  • C++ STL常见容器

    2021-10-10 20:35:16
    1.vector(数组) 1.1 介绍 vector为可变长数组(动态数组),定义的vector数组可以随时添加数值和删除元素。 头文件 #include < vector > 初始化: //初始化 //方式一:初始化一维可变长数组 ...//no
  • C++ STL容器类型的内存释放

    千次阅读 2018-05-31 15:45:28
    C++ 的大部分STL容器类型不会随着生命周期的结束而自动释放内存,接下来将依次对其说明:1. vector 类型经测试,直到C++11的vector类型,用clear或者erase都无法释放内存,只有显示调用swap:std::vector&lt;T&...
  • STL容器介绍及选择方式容器类型容器优缺点一 序列容器vectordequelistforward_list(C++11)queuepriority_queuestackarray二 关联容器setmultisetmapmultimap三 无序关联容器 容器类型 以前的11个容易分别是deque、...
  • C++ STL容器时间复杂度下的最佳选择

    万次阅读 多人点赞 2017-06-21 16:24:11
    STLC++11中还算是火热,想必大家早有耳闻,对于泛型编程而言,或者数据结构而言,STL都显得尤为重要。今天让我们来了解一下,根据时间复杂度这个条件,挑选最适合自己程序的STL
  • C++STL容器之set容器

    千次阅读 多人点赞 2018-08-08 16:51:41
    set是C++标准库中的一种关联容器。所谓关联容器就是通过键(key)来读取和修改元素。与map关联容器不同,它只是单纯键的集合。 set集合容器实现了红黑树(Red-Black Tree)的平衡二叉检索树的数据结构,在插入元素...
  • C++ STL 容器基本使用详解:

    千次阅读 2020-02-07 22:37:51
    C++ STL 容器C++ STL vector 容器 vector容器的概念 vector在英文中是矢量的意思。 我们知道,一个数组必须要有固定的长度,在开一个数组的时候,这个长度也就被静态地确定下来了。但是vector却是数组的“加强版...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 73,734
精华内容 29,493
关键字:

c++stl容器

c++ 订阅