精华内容
下载资源
问答
  • 2020-04-09 14:44:04

    前言

    序列容器以线性序列的方式存储元素。它没有对元素进行排序,元素的顺序和存储它们的顺序相同。一般来说,有 5 种标准的序列容器,每种容器都具有不同的特性:

    • array<T,N> (数组容器) :是一个长度固定的序列,有N个T类型的对象,不能增加或删除元素。
    • vector<T> (向量容器) :
      是一个长度可变的序列,用来存放T类型的对象。必要时,可以自动增加容量,但只能在序列的末尾高效地增加或删除元素。
    • deque<T> (双向队列容器) :
      是一个长度可变的、可以自动增长的序列,在序列的两端都不能高效地增加或删除元素。
    • list<T> (链表容器) :
      是一个长度可变的、由 T 类型对象组成的序列,它以双向链表的形式组织元素,在这个序列的任何地方都可以高效地增加或删除元素。访问容器中任意元素的速度要比前三种容器慢,这是因为 list<T> 必须从第一个元素或最后一个元素开始访问,需要沿着链表移动,直到到达想要的元素。
    • forward list<T> (正向链表容器) :
      是一个长度可变的、由 T 类型对象组成的序列,它以单链表的形式组织元素,是一类比链表容器快、更节省内存的容器,但是它内部的元素只能从第一个元素开始访问。

    什么是序列式容器

    转载请注明文章来源:https://blog.csdn.net/y601500359/article/details/105409417
    现在我们来说说序列式容器到底是什么。

    所谓序列容器,即以线性排列(类似普通数组的存储方式)来存储某一指定类型(例如 int、double 等)的数据,需要特殊说明的是,该类容器并不会自动对存储的元素按照值的大小进行排序。

    需要注意的是,序列容器只是一类容器的统称,并不指具体的某个容器,序列容器大致包含以下几类容器:

    • array<T,N>(数组容器):
      表示可以存储 N 个 T 类型的元素,是 C++ 本身提供的一种容器。此类容器一旦建立,其长度就是固定不变的,这意味着不能增加或删除元素,只能改变某个元素的值;
    • vector<T>(向量容器):
      用来存放 T 类型的元素,是一个长度可变的序列容器,即在存储空间不足时,会自动申请更多的内存。使用此容器,在尾部增加或删除元素的效率最高(时间复杂度为 O(1) 常数阶),在其它位置插入或删除元素效率较差(时间复杂度为 O(n) 线性阶,其中 n 为容器中元素的个数);
    • deque<T>(双端队列容器):
      和 vector 非常相似,区别在于使用该容器不仅尾部插入和删除元素高效,在头部插入或删除元素也同样高效,时间复杂度都是 O(1) 常数阶,但是在容器中某一位置处插入或删除元素,时间复杂度为 O(n) 线性阶;
    • list<T>(链表容器):
      是一个长度可变的、由 T 类型元素组成的序列,它以双向链表的形式组织元素,在这个序列的任何地方都可以高效地增加或删除元素(时间复杂度都为常数阶 O(1)),但访问容器中任意元素的速度要比前三种容器慢,这是因为 list<T> 必须从第一个元素或最后一个元素开始访问,需要沿着链表移动,直到到达想要的元素。
    • forward_list<T>(正向链表容器):
      和 list 容器非常类似,只不过它以单链表的形式组织元素,它内部的元素只能从第一个元素开始访问,是一类比链表容器快、更节省内存的容器。

    注意,其实除此之外,stack<T> 和 queue<T> 本质上也属于序列容器,只不过它们都是在 deque 容器的基础上改头换面而成,通常更习惯称它们为容器适配器,有关它们的介绍,会放到后续章节中。

    下图说明了可供使用的序列容器以及它们之间的区别。
    标准的序列容器
    转载请注明文章来源:https://blog.csdn.net/y601500359/article/details/105409417

    容器中常见的函数成员

    表 2 展示了 array、vector 和 deque 容器的函数成员,它们中至少有两个容器实现了同样的函数成员。

    表 2 array、vector 和 deque 容器的函数成员

    函数成员函数功能array<T,N>vector<T>deque<T>
    begin()返回指向容器中第一个元素的迭代器。
    end()返回指向容器最后一个元素所在位置后一个位置的迭代器,通常和 begin() 结合使用。
    rbegin()返回指向最后一个元素的迭代器。
    rend()返回指向第一个元素所在位置前一个位置的迭代器。
    cbegin()和 begin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
    cend()和 end() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
    crbegin()和 rbegin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
    crend()和 rend() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
    assign()用新元素替换原有内容。-
    operator=()复制同类型容器的元素,或者用初始化列表替换现有内容。
    size()返回实际元素个数。
    max_size()返回元素个数的最大值。这通常是一个很大的值,一般是 232-1,所以我们很少会用到这个函数。
    capacity()返回当前容量。--
    empty()判断容器中是否有元素,若无元素,则返回 true;反之,返回 false。
    resize()改变实际元素的个数。-
    shrink _to_fit()将内存减少到等于当前元素实际所使用的大小。-
    front()返回第一个元素的引用。
    back()返回最后一个元素的引用。
    operator使用索引访问元素。
    at()使用经过边界检査的索引访问元素。
    push_back()在序列的尾部添加一个元素。-
    insert()在指定的位置插入一个或多个元素。-
    emplace()在指定的位置直接生成一个元素。-
    emplace_back()在序列尾部生成一个元素。-
    pop_back()移出序列尾部的元素。-
    erase()移出一个元素或一段元素。-
    clear()移出所有的元素,容器大小变为 0。-
    swap()交换两个容器的所有元素。
    data()返回指向容器中第一个元素的指针。-

    列表中 - 表明对应的容器并没有定义这个函数。

    list 和 forward_list 容器彼此非常相似,forward_list 中包含了 list 的大部分成员函数,而未包含那些需要反向遍历的函数。表 3 展示了 list 和 forward_list 的函数成员。

    表 3 list 和 forward_list 的函数成员

    函数成员函数功能list<T>forward_list<T>
    begin()返回指向容器中第一个元素的迭代器。
    end()返回指向容器最后一个元素所在位置后一个位置的迭代器。
    rbegin()返回指向最后一个元素的迭代器。-
    rend()返回指向第一个元素所在位置前一个位置的迭代器。-
    cbegin()和 begin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
    before_begin()返回指向第一个元素前一个位置的迭代器。-
    cbefore_begin()和 before_begin() 功能相同,只不过在其基础上,增加了 const 属性,即不能用该指针修改元素的值。-
    cend()和 end() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。 是
    crbegin()和 rbegin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。-
    crend()和 rend() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。-
    assign()用新元素替换原有内容。
    operator=()复制同类型容器的元素,或者用初始化列表替换现有内容。
    size()返回实际元素个数。-
    max_size()返回元素个数的最大值,这通常是一个很大的值,一般是 232-1,所以我们很少会用到这个函数。
    resize()改变实际元素的个数。
    empty()判断容器中是否有元素,若无元素,则返回 true;反之,返回 false。
    front()返回容器中第一个元素的引用。
    back()返回容器中最后一个元素的引用。是 -
    push_back()在序列的尾部添加一个元素。是 -
    push_front()在序列的起始位置添加一个元素。
    emplace()在指定位置直接生成一个元素。是 -
    emplace_after()在指定位置的后面直接生成一个元素。-
    emplace_back()在序列尾部生成一个元素。-
    cmplacc_front()在序列的起始位生成一个元索。
    insert()在指定的位置插入一个或多个元素。-
    insert_after()在指定位置的后面插入一个或多个元素。-
    pop_back()移除序列尾部的元素。-
    pop_front()移除序列头部的元素。
    reverse()反转容器中某一段的元素。
    erase()移除指定位置的一个元素或一段元素。是 -
    erase_after()移除指定位置后面的一个元素或一段元素。-
    remove()移除所有和参数匹配的元素。
    remove_if()移除满足一元函数条件的所有元素。
    unique()移除所有连续重复的元素。
    clear()移除所有的元素,容器大小变为 0。
    swap()交换两个容器的所有元素。
    sort()对元素进行排序。
    merge()合并两个有序容器。
    splice()移动指定位置前面的所有元素到另一个同类型的 list 中。-
    splice_after()移动指定位置后面的所有元素到另一个同类型的 list 中。-

    注意,大家没有必要死记这些表,它们仅供参考。在深入了解到容器是如何组织元素以后,你会本能地知道哪个容器能使用哪些成员函数。

    参考来源:http://c.biancheng.net/view/409.html

    更多相关内容
  • 序列式容器

    2022-01-15 21:00:27
    序列式容器 概念 序列容器,就是以线性排列(类似普通数组的存储方式)来存储某一指定类型的数据,并且该类容器并不会自动对存储的元素按照值的大小进行排序。 内容 array序列式容器迭代器的通用函数 由于序列式...

    序列式容器

    概念

    序列容器,就是以线性排列(类似普通数组的存储方式)来存储某一指定类型的数据,并且该类容器并不会自动对存储的元素按照值的大小进行排序。

    内容

    array(数组容器)表示可以存储N个T类型的容器,该容器一旦建立那么容量就是固定的,因此不能额外增加或删除元素,只能修改其值
    vector(向量容器)大部分与array类似,但是vector是长度可变的,可以看成是可以动态变化长度的数组,因此在其尾部增加或删除元素效率可以看成是O(1),对其他位置的操作为O(n)
    deque(双端队列容器)大部分与vector类似,但是deque在头部插入与删除也是O(1),在其中部插入与删除元素才是O(n)
    list(链表容器)一个长度可变的T类型的序列,内部采用双向链表实现,由于双向链表的特性,对其在任何位置插入与删除都将是O(1),但是由于list对应的迭代器类型为双向迭代器,决定了list的访问必须逐个访问,因此对list的访问速度要慢于array、vector和deque
    forward_list(正向链表容器)十分接近list,但是内部采用的是单链表实现,因此节省了一定的内存,但是访问也需要逐个访问

    序列式容器迭代器的通用函数

    由于序列式容器(除了forward_list外)都是支持随机访问迭代器的,所以他们有一些通用的对迭代器的操作方法,这里直接给出:

    begin()返回指向第一个元素的随机访问迭代器
    end()返回指向容器最后一个元素之后一个位置的随机访问迭代器
    rbegin()返回指向最后一个元素的随机访问迭代器
    rend()返回指向第一个元素之前一个位置的随机访问迭代器
    cbegin()和 begin() 功能相同,只不过在其基础上增加了 const 属性,不能用于修改元素
    cend()和 end() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素
    crbegin()和 rbegin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素
    crend()和 rend() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素

    举个栗子:

    std:: array<int, 5> v{1,2,3,4,5};
    for (std::array<int, 5>::iterator it = v.begin(); it != v.end(); it++) {
        std::cout << *it << ' ';
    }
    std::cout << std::endl;//Output 1 2 3 4 5
    for (std::array<int, 5>::reverse_iterator it = v.rbegin(); it != v.rend(); it++) {//注意此处需要使用反向迭代器和++
        std::cout << *it << ' ';
    }
    std::cout << std::endl;//Output 5 4 3 2 1
    

    关于这几个对迭代器的操作方法,可以见下图:

    除此之外对于迭代器的操作,可以使用auto关键字,编译器会自动识别其迭代器的类型。

    序列式容器用法

    array

    array是一种不可以修改其长度,在普通数组的基础上增加了一些全局变量和函数的序列式容器,比起不同数组效率更高更安全。

    定义

    array的定义:

    namespace std{
        template <typename T, size_t N>
        class array;
    }
    

    可以看到array被定义在命名空间std中

    因此创建array可以有以下两种方式:

    #include<array> //使用array必须导入array头文件
    std::array<int, 5> v;
    

    或:

    #include<array>
    using namespace std;
    int main() {
    	array<int, 5> v;
    }
    

    初始化

    array的初始化可以采用默认初始化方式:

    std:: array<int, 5> v{};//默认初始化
    for (std::array<int, 5>::iterator it = v.begin(); it != v.end(); it++) {
    	std::cout << *it << ' ';
    }
    //输出5个0
    

    也可以采用类似数组的初始化方式:

    std:: array<int, 10> v{1,2,5};
    for (std::array<int, 10>::iterator it = v.begin(); it != v.end(); it++) {
        std::cout << *it << ' ';
    }
    //输出1 2 5 0 0 0 0 0 0 0
    

    成员函数

    array因为支持随机访问迭代器,所以上文提到的8个操作array都支持

    除此之外,array还支持其他几个操作

    size()返回array中的元素个数,由于array长度是固定的,所以相当于返回构造array的第二个参数N
    max_size()返回可容纳元素的最大数量,由于array长度是固定的,所以相当于返回构造array的第二个参数N
    empty()返回array是否非空
    at(i)返回array第i个位置(从0开始)的元素的引用,这意味着我们可以直接对他进行修改,并且它会自动检查i是否会导致越界,如果越界会抛出std::out_of_range的异常
    front()返回容器中第一个元素的直接引用,该函数不适用于空的array容器
    back()返回容器中最后一个元素的直接应用,该函数同样不适用于空的array容器
    data()返回一个指向容器首个元素的指针
    operator[]类似于数组元素的下标访问方式,返回数组对应下标的引用,可以直接操作(包括修改)
    fill(T& val)将val赋值给array中的每一个元素,相当于批量赋值,可以用于初始化
    array1.swap(array2)在array1和array2的T与N一致的情况下交换两个array中的元素

    举个栗子:

    std:: array<int, 5> v{1,2,3,4,5};
    v[2] = 7;
    std::cout << v.at(2) << std::endl;//Output 7
    v.at(2) = 5;
    std::cout << v.at(2) << std::endl;//Output 5
    for (std::array<int, 5>::iterator it = v.begin(); it != v.end(); it++) {//Output 1 2 5 4 5
    	std::cout << *it << ' ';
    }
    std::cout << std::endl;
    std::cout << v.front() << std::endl;//Output 1
    std::cout << v.back() << std::endl;//Output 5
    v.fill(10);
    for (std::array<int, 5>::iterator it = v.begin(); it != v.end(); it++) {//Output 10 10 10 10 10
    	std::cout << *it << ' ';
    }
    std::cout << std::endl;
    *(v.data()) = 4;
    for (std::array<int, 5>::iterator it = v.begin(); it != v.end(); it++) {//Output 4 10 10 10 10
    	std::cout << *it << ' ';
    }
    

    array相比数组的提升

    1.array可以实现大小的比较

    大小比较的规则与字符串的大小比较规则一致

    std::array<char, 20> h{ "helloworld" };
    std::array<char, 20> a{ "apple" };	
    if (a < h) {//no
        std::cout << "yes\n";
    }
    else {
        std::cout << "no\n";
    }
    

    2.array可以直接赋值

    std::array<char, 20> h{ "helloworld" };
    std::array<char, 20> a{ "apple" };
    a = h;
    for (auto e : a) {//helloworld
        std::cout << e;
    }
    

    3.at方法可以自动检查边界问题

    vector

    vector是向量容器,一个向量用于存储同一个类型的一组值

    定义

    一个向量的定义需要引入如下代码段:

    #include <vector>
    using namespace std;
    

    或以下列形式创建,(T)是一个类型

    #include <vector>
    std::vector<T> v;
    

    注意,这样定义的 vector 容器,因为容器中没有元素,所以没有为其分配空间。当添加第一个元素(比如使用 push_back() 函数)时,vector 会自动分配内存。

    对于vector,有容量(capacity)和size(大小)的区分。

    容量指的是vector能够容纳的最大元素数,这是一个可以拓展的值,通过调用reserve()来拓展容量,如果新的容量小于等于当前容量,那么没有操作,其不会影响原有元素,也不会生成新元素,但是要注意,一旦使用了reserve()那么原油的所有迭代器都将会失效,因为拓展容量时会修改整个vector的地址。

    大小指的是vector当前实际容纳的元素数,其也可以修改,通过调用resize()来修改值,如果新的size比容量要大,那么会自动扩容。

    初始化

    第一种方式,初始化成员列表:
    vector<int> v1{1,2,3,4,5};
    第二种方式,指定元素个数(默认初始化为0)
    vector<int> v2(5);//5个0
    第三种方式,指定元素个数并全部初始化为1
    vector<int> v3(5,1);//5个1 
    第四种方式,存储已经存在的vector容器值或数组
    vector<int> a(v3); //5个1
    vector<int> b(v1.begin(),v1.begin()+3);//1 2 3
    int arr[3] = {4,5,6};
    vector<int> c(arr,arr+3);//4 5 6
    

    需要注意的是,由于vector是可以直接创建空的vector的,所以这样的初始化是错误的

    vector<int> v;
    for (auto it = v.begin();it != v.end();it++){
    	*it = 1;
        cout << *it << ' '; 
    }
    //不会报错,但是不会做到预想的结果,因为空的vector的begin() == end()
    

    成员函数

    vector因为支持随机访问迭代器,所以上文提到的8个操作vector都支持

    除此之外,vector还支持其他几个操作

    size()返回实际元素个数
    max_size()返回元素个数的最大值。这通常是一个很大的数
    resize()改变实际元素的个数
    capacity()返回当前容量
    reserve()增加容器的容量
    empty()返回vector是否非空
    at(i)返回vector第i个位置(从0开始)的元素的引用,这意味着我们可以直接对他进行修改,并且它会自动检查i是否会导致越界,如果越界会抛出std::out_of_range的异常
    front()返回容器中第一个元素的直接引用,该函数不适用于空的vector容器
    back()返回容器中最后一个元素的直接应用,该函数同样不适用于空的vector容器
    data()返回一个指向容器首个元素的指针
    operator[]类似于数组元素的下标访问方式,返回数组对应下标的引用,可以直接操作(包括修改)
    assign(val)将val赋值给vector中的每一个元素,相当于批量赋值,可以用于初始化
    push_back()在vector的尾部添加一个元素,先创建,然后拷贝移动到vector末尾
    pop_back()移出vector尾部的元素,对于空的vector不适用,移除后size-1,而capacity不变
    insert()在指定的位置插入一个或多个元素,插入后size+1,capacity可能不变
    erase()移出一个元素或一段元素,移除后size减小,capacity不变
    clear()移出所有的元素,容器大小变为 0
    swap()交换两个容器的所有元素/td>
    emplace()在指定的位置直接生成一个元素,大小+1
    emplace_back()在vector尾部生成一个元素,由于其是在尾部直接生成而不是拷贝元素或移动,因此效率比push_back高

    一些例子:

    vector<int> v;
    cout << v.front() << endl;//Error
    cout << v.back() << endl;//Error
    cout << v.size() << endl;//Output 0
    v.pop_back();//Error
    for (auto e : v) {//no Output
        cout << e << ' ';
    }
    cout << v.max_size() << endl;//Output 1073741823
    v.resize(10);
    cout << v.max_size() << endl;//Output 1073741823
    cout << v.size() << endl;//Output 10
    for (auto e : v) {//Output 0 0 0 0 0 0 0 0 0 0
        cout << e << ' ';
    }
    

    其中某些函数存在多个重载,或其调用有其独特的含义,如对参数由特定要求等,这里单独列出:

    1.insert
    iterator insert(iterator pos,const T& elem)	在迭代器 pos 指定的位置之前插入一个新元素elem,并返回表示新插入元素位置的迭代器。
    iterator insert(iterator pos,int n,const T& elem)	在迭代器 pos 指定的位置之前插入 n 个元素 elem,并返回表示第一个新插入元素位置的迭代器。
    iterator insert(iterator pos,first,last) 	在迭代器 pos 指定的位置之前,插入其他容器(不仅限于vector)中位于 [first,last) 区域的所有元素,并返回表示第一个新插入元素位置的迭代器。
    iterator insert(iterator pos,initializer_list<T> initlist)	在迭代器 pos 指定的位置之前,插入初始化列表(用大括号{}括起来的多个元素,中间有逗号隔开)中所有的元素,并返回表示第一个新插入元素位置的迭代器。
                                                                                        
    2.emplace()
    该函数与insert很像,都是在某个位置插入元素,但是要注意这个函数一次只能插入一个,同时该函数的效率比insert单次插入要高                                                                               
    iterator emplace(iterator pos,const T& elem)                                             
                                                                                        
    3.erase()
    iterator erase(iterator pos) 删除某个指定位置的元素,返回指向被删除元素下一个位置元素的迭代器       iterator erase(iterator begin,iterator end)删除[begin,end)范围的元素,返回指向被删除元素下一个位置元素的迭代器   
                    
    void show(vector<int> v) {
    	for (auto c : v) {
    		cout << c << ' ';
    	}
    	cout << endl;
    }
    int main() {
    	vector<int> v{ 1,2,4,5 };
    	v.insert(v.begin() + 2, 3);
    	show(v);//1 2 3 4 5
    	v.insert(v.begin(), 3, 0);
    	show(v);//0 0 0 1 2 3 4 5
    	array<int, 2> arr{ 6,7 };
    	v.insert(v.end(), arr.begin(), arr.end());
    	show(v);//0 0 0 1 2 3 4 5 6 7
    	v.insert(v.end(), { 8,9 });
    	show(v);//0 0 0 1 2 3 4 5 6 7 8 9
    	v.emplace(v.end(), 10);
    	show(v);//0 0 0 1 2 3 4 5 6 7 8 9 10
    	v.erase(v.begin());
    	show(v);//0 0 1 2 3 4 5 6 7 8 9 10
    }                                                                    
    

    一些小tips

    虽然我们创建一个向量vector的时候,理论上这个T可以是任意类型,但是bool类型作为T是会出现问题的因为其牵扯到复杂的历史遗留问题,不做展开。

    deque

    deque是双端队列容器,其在某些方面与vector高度相似,其对头尾的插入为O(1),对中间位置的插入为O(n),但是其与vector有一个很大的不同在于deque 容器中存储元素并不能保证所有元素都存储到连续的内存空间中。

    定义

    类似的,deque的创建也有两种方式:

    1.
    #include<deque>
    using namespace std;
    deque<int> deq;
    2.
    #include<deque>
    std::deque<int> deq;
    

    注意,这样定义的deque容器,因为容器中没有元素,所以没有为其分配空间。当添加第一个元素(比如使用 push_back() 函数)时,deque 会自动分配内存。

    初始化

    与vector类似的5种初始化方式

    第一种方式,初始化成员列表:
    deque<int> v1{1,2,3,4,5};
    第二种方式,指定元素个数(默认初始化为0)
    deque<int> v2(5);//5个0
    第三种方式,指定元素个数并全部初始化为1
    deque<int> v3(5,1);//5个1 
    第四种方式,存储已经存在的deque容器值或数组
    deque<int> a(v3); //5个1
    deque<int> b(v1.begin(),v1.begin()+3);//1 2 3
    int arr[3] = {4,5,6};
    deque<int> c(arr,arr+3);//4 5 6
    

    也跟vector一样在某些方面有限制

    deque<int> v;
    for (auto it = v.begin();it != v.end();it++){
    	*it = 1;
        cout << *it << ' '; 
    }
    //不会报错,但是不会做到预想的结果,因为空的deque的begin() == end()
    

    成员函数

    因为deque支持随机访问迭代器,所以上面对随机访问迭代器的8种操作deque都支持

    除此之外,deque还支持其他几个操作

    size()返回实际元素个数
    max_size()返回元素个数的最大值。这通常是一个很大的数
    resize()改变实际元素的个数
    empty()返回deque是否非空
    shrink _to_fit()将内存减少到等于当前元素实际所使用的大小
    at(i)返回deque第i个位置(从0开始)的元素的引用,这意味着我们可以直接对他进行修改,并且它会自动检查i是否会导致越界,如果越界会抛出std::out_of_range的异常
    front()返回容器中第一个元素的直接引用,该函数不适用于空的deque容器
    back()返回容器中最后一个元素的直接应用,该函数同样不适用于空的deque容器
    operator[]类似于数组元素的下标访问方式,返回数组对应下标的引用,可以直接操作(包括修改)
    assign(val)将val赋值给deque中的每一个元素,相当于批量赋值,可以用于初始化
    push_back()在deque的尾部添加一个元素,先创建,然后拷贝移动到deque末尾
    pop_back()移出deque尾部的元素,对于空的deque不适用,移除后size-1,而capacity不变
    push_front()在deque的头部添加一个元素,先创建,然后拷贝移动到deque头部
    pop_front()移出deque头部的元素,对于空的deque不适用,移除后size-1,而capacity不变
    insert()在指定的位置插入一个或多个元素,插入后size+1,capacity可能不变
    erase()移出一个元素或一段元素,移除后size减小,capacity不变
    clear()移出所有的元素,容器大小变为 0
    swap()交换两个容器的所有元素/td>
    emplace()在指定的位置直接生成一个元素,大小+1
    emplace_back()在deque尾部生成一个元素,由于其是在尾部直接生成而不是拷贝元素或移动,因此效率比push_back高
    emplace_front()在deque头部生成一个元素,由于其是在头部直接生成而不是拷贝元素或移动,因此效率比push_front高

    注意,deque没有data()函数,这是deque的底层实现决定的。

    由于函数的定义与重载与vector十分类似,这里不再演示

    deque的底层原理

    deque的底层原理,是借助这样的一个结构实现的

    map是一个地址数组,存储着各个连续空间的首地址,通过这个map数组,deque 容器申请的这些分段的连续空间就能实现“整体连续”的效果。

    list

    双向链表容器,底层是以双向链表的形式实现的。因此,list 容器中的元素可以分散存储在内存空间里。

    定义

    类似的,list的创建也有两种方式:

    1.
    #include<list>
    using namespace std;
    list<int> L;
    2.
    #include<list>
    std::list<int> L;
    

    注意,这样定义的list容器,因为容器中没有元素,所以没有为其分配空间。当添加第一个元素(比如使用 push_back() 函数)时,list 会自动分配内存。

    初始化

    与vector类似的5种初始化方式

    第一种方式,初始化成员列表:
    list<int> v1{1,2,3,4,5};
    第二种方式,指定元素个数(默认初始化为0)
    list<int> v2(5);//5个0
    第三种方式,指定元素个数并全部初始化为1
    list<int> v3(5,1);//5个1 
    第四种方式,存储已经存在的list容器值或数组
    list<int> a(v3); //5个1
    list<int> b(v1.begin(),v1.begin()+3);//1 2 3
    int arr[3] = {4,5,6};
    list<int> c(arr,arr+3);//4 5 6
    

    也跟vector一样在某些方面有限制

    list<int> v;
    for (auto it = v.begin();it != v.end();it++){
    	*it = 1;
        cout << *it << ' '; 
    }
    //不会报错,但是不会做到预想的结果,因为空的list的begin() == end()
    

    成员函数

    比起vector,array和deque,list的迭代器类型为双向迭代器,这决定了对于list的迭代器不能使用任何的比较运算符,+=、-=之类的一次跨越多步的运算符以及不能通过下标访问元素。但是其支持使用==和!=运算符

    size()返回实际元素个数
    max_size()返回元素个数的最大值。这通常是一个很大的数
    resize()调整容器的大小
    empty()返回list是否非空
    front()返回容器中第一个元素的直接引用,该函数不适用于空的list容器
    back()返回容器中最后一个元素的直接应用,该函数同样不适用于空的list容器
    assign(val)将val赋值给list中的每一个元素,相当于批量赋值,可以用于初始化
    push_back()在list的尾部添加一个元素,先创建,然后拷贝移动到list末尾
    pop_back()移出list尾部的元素,对于空的list不适用,移除后size-1,而capacity不变
    push_front()在list的头部添加一个元素,先创建,然后拷贝移动到list头部
    pop_front()移出list头部的元素,对于空的list不适用,移除后size-1,而capacity不变
    insert()在指定的位置插入一个或多个元素,插入后size+1,capacity可能不变
    erase()移出一个元素或一段元素,移除后size减小,capacity不变
    clear()移出所有的元素,容器大小变为 0
    swap()交换两个容器的所有元素
    emplace()在指定的位置直接生成一个元素,大小+1
    emplace_back()在list尾部生成一个元素,由于其是在尾部直接生成而不是拷贝元素或移动,因此效率比push_back高
    emplace_front()在list头部生成一个元素,由于其是在头部直接生成而不是拷贝元素或移动,因此效率比push_front高
    splice()将一个 list 容器中的元素插入到另一个容器的指定位置
    remove(val)删除容器中所有等于 val 的元素
    remove_if()删除容器中满足条件的元素
    unique()删除容器中相邻的重复元素,只保留一个
    merge()合并两个事先已排好序的 list 容器,并且合并之后的 list 容器依然是有序的,如果原本的两个list无序则报错
    sort()通过更改容器中元素的位置,将它们进行排序
    reverse()反转容器中元素的顺序

    另外,由于list底层的实现机制的原因,对list容器进行插入、删除、结合等操作的时候不会导致原有的迭代器失效,只有删除会导致当前指向的迭代器失效。

    部分list添加的函数举例:

    void show(list<int> v) {
    	for (auto c : v) {
    		cout << c << ' ';
    	}
    	cout << endl;
    }
    int main() {
    	list<int> L{ 0,0,0,1,4,3 };
    	show(L);//0 0 0 1 4 3
    	L.remove(0);
    	show(L);//1 4 3
    	L.sort();
    	show(L);//1 3 4 
    	list<int> L2{ 4,5,6 };
    	L.merge(L2);
    	show(L);//1 3 4 4 5 6
    	L.unique();
    	show(L);//1 3 4 5 6
    	L.reverse();
    	show(L);//6 5 4 3 1
    }
    

    insert、erase等函数的使用方法与上文一致,这里不再重复
    但是对于一些新的方法这里给出使用形式

    1.splice()
    splice() 成员方法的作用对象是其它 list 容器,其功能是将其它 list 容器中的元素添加到当前 list 容器中指定位置处
    void splice (iterator pos, list& l);将 l 容器中存储的所有元素全部移动当前 list 容器中 pos 指明的位置处。
    void splice (iterator pos, list& l, iterator it);将 l 容器中 it 指向的元素移动到当前容器中 pos 指明的位置处
    void splice (iterator pos, list& l, iterator first, iterator last);将 l 容器 [first, last) 范围内所有的元素移动到当前容器 pos 指明的位置处
    注意,无论使用哪种形式,添加完成后l都为空
                                                                               
    2.remove_if()
    remove_if(lambda)该函数接受一个lambda表达式(实际上是一个函数),满足条件的都将被删除。                        
    void show(list<int> v) {
    	for (auto c : v) {
    		cout << c << ' ';
    	}
    	cout << endl;
    }
    int main() {
    	list<int> L{ 0,0,0,1,4,3 };
    	list<int> L2{ 4,5,6 };
    	L.splice(L.begin(), L2);//4 5 6 0 0 0 1 4 3
    	show(L);
    	L.splice(L.end(), L2, L2.begin());//0 0 0 1 4 3 4
    	show(L);
    	L.splice(L.end(), L2, L2.begin(), L2.end());//0 0 0 1 4 3 4 5 6
    	show(L);
        L.remove_if([&](int data) {return data <= 0; });//1 4 3
    	show(L);
    }                                                                     
    

    list的底层原理

    list的底层即双向链表

    forward_list

    forward_list,采用单链表构建的一种stl数据结构

    定义

    类似的,forward_list的创建也有两种方式:

    1.
    #include<forward_list>
    using namespace std;
    forward_list<int> L;
    2.
    #include<forward_list>
    std::forward_list<int> L;
    

    注意,这样定义的forward_list容器,因为容器中没有元素,所以没有为其分配空间。当添加第一个元素(比如使用 push_back() 函数)时,forward_list 会自动分配内存。

    初始化

    与vector类似的5种初始化方式

    第一种方式,初始化成员列表:
    forward_list<int> v1{1,2,3,4,5};
    第二种方式,指定元素个数(默认初始化为0)
    forward_list<int> v2(5);//5个0
    第三种方式,指定元素个数并全部初始化为1
    forward_list<int> v3(5,1);//5个1 
    第四种方式,存储已经存在的forward_list容器值或数组
    forward_list<int> a(v3); //5个1
    forward_list<int> b(v1.begin(),v1.begin()+3);//1 2 3
    int arr[3] = {4,5,6};
    forward_list<int> c(arr,arr+3);//4 5 6
    

    也跟vector一样在某些方面有限制

    forward_list<int> v;
    for (auto it = v.begin();it != v.end();it++){
    	*it = 1;
        cout << *it << ' '; 
    }
    //不会报错,但是不会做到预想的结果,因为空的forward_list的begin() == end()
    

    成员函数

    因为forward_list底层采用了单链表的形式,因此forward_list的迭代器为正向迭代器,因此其对应的前面八个迭代器函数中带r的都不存在

    before_begin()返回指向容器中第一个元素之前的位置的迭代器
    cbefore_begin()返回指向容器中第一个元素之前的位置的迭代器,不能用于修改元素
    max_size()返回元素个数的最大值。这通常是一个很大的数
    resize()调整容器的大小
    empty()返回list是否非空
    front()返回容器中第一个元素的直接引用,该函数不适用于空的list容器
    assign(val)将val赋值给list中的每一个元素,相当于批量赋值,可以用于初始化
    push_front()在list的头部添加一个元素,先创建,然后拷贝移动到list头部
    emplace_front()在list头部生成一个元素,由于其是在头部直接生成而不是拷贝元素或移动,因此效率比push_front高
    pop_front()移出list头部的元素,对于空的list不适用
    insert_after()在指定的位置插入一个元素,返回一个指向新元素的迭代器
    emplace_after()/td> 在指定的位置插入一个元素,效率高于insert_after()
    erase_after()删除容器中某个指定位置或区域内的所有元素
    clear()移出所有的元素,容器大小变为 0
    swap()交换两个容器的所有元素/td>
    splice_after()将某个 forward_list 容器中指定位置或区域内的元素插入到另一个容器的指定位置之后
    remove(val)删除容器中所有等于 val 的元素
    remove_if()删除容器中满足条件的元素
    unique()删除容器中相邻的重复元素,只保留一个
    merge()合并两个事先已排好序的 list 容器,并且合并之后的 list 容器依然是有序的,如果原本的两个list无序则报错
    sort()通过更改容器中元素的位置,将它们进行排序
    reverse()反转容器中元素的顺序

    注意没有size()函数

    forward_list的底层原理

    forward_list 使用的是单链表

    展开全文
  • 序列式容器与关联式容器

    千次阅读 2019-08-01 15:01:42
    0、序列式容器 vector 一、vector6种初始化 1、vector<int> vec1;// 默认初始化,vector为空,size为0,需要动态添加 2、vector<int> vec1(7);//包含7个缺省的值初始化,即7个0. 3、...

    0、序列式容器

    vector

    一、vector6种初始化

    1、vector<int> vec1;// 默认初始化,vector为空,size为0,需要动态添加
    2、vector<int> vec1(7);//包含7个缺省的值初始化,即7个0.
    3、vector<int> vec1(7,3);// 包含7个值为3的int
    4、vector<int> vec2(vec1);
       vector<int> vec2=vec1;// 两种方式等价,vec2初始化为vec1的拷贝
    5、vector<int> vec1={1,2,3,5,6};// 列表初始化
    6、vector<int> vec2(vec1.begin()+2,vec1.end());// 两个迭代器范围

    list

    deque

    头尾两端分别做元素插入与删除。处理数据库事务或模拟一家超市的结账队列,像这两种应用都可以充分利用 deque 容器。

    与vector区别

    1:deque可以在容器的头部和尾部高效地添加或删除对象,这是它相对于 vector 容器的优势。

    2:没有容量观念,动态分段连续空间组合,没必要vector的空间保留。

    基本操作:

    增删

    push_back在尾部添加一个元素  push_front在首部添加一个元素

    pop_back在尾部删除一个元素    pop_front在首部删除一个元素

    emplace (C++11)在迭代器位置插入元素(emplace使用直接构造函数,insert使用复制构造函数)

    emplace_front (C++11)在首部添加一个元素

    emplace_back (C++11)在尾部添加一个元素

    insert迭代器位置插入元素,或者插入连续的序列

    erase擦除迭代器位置的元素,或者擦除连续的序列

    访问元素

    operator[]直接访问指定位置的元素

    at直接访问指定位置的元素,指定位置超出有效范围会报出异常

    front访问首元素

    back访问尾元素

    判断

    size返回目前元素的数量

    max_size返回可以拓展的最大容量

    resize改变目前容器的大小

    empty判断容器是否为空

    迭代器

    begin 将迭代器返回到开头(增长方向:begin -> end)

    end将迭代器返回到结尾

    rbegin返回反向迭代器以反向开始(增长方向:rbegin -> rend)

    rend将反向迭代器返回到反向结束

     

    stack

    先进后出,

    基本操作:

    增删:s.push(int x)将x 接到队列的末端    s.pop()  弹出队列的第一个元素,注意,并不会返回被弹出元素的值

    访问元素:q.top() 获取栈顶元素

    判断:q.empty() 当队列空时,返回true       q.size()访问队列中的元素个数

    queue

    先进先出,queue不提供遍历功能,也没有迭代器。

    基本操作:

    增删:q.push(int x)将x 接到队列的末端    q.pop()  弹出队列的第一个元素,注意,并不会返回被弹出元素的值

    访问元素:q.front() 访问队首元素,即最早被压入队列的元素    q.back()访问最后被压入队列的元素

    判断:q.empty() 当队列空时,返回true       q.size()访问队列中的元素个数

    heap

    heap是priority_queue的幕后英雄

    操作:make_heap  ,  push_heap,   pop_heap , sort_heap

    参数都是:sort_heap  (Iterator first,Iterator second)迭代器

    #include <vector>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    int main(){
    	int a[9] = { 0, 1, 2, 3, 4, 8, 9, 3, 5 };
    	vector<int> vec(a, a + 9);
    
    	make_heap(vec.begin(), vec.end());
    	for (int i = 0; i < vec.size(); i++)
    		cout << vec[i] << " ";  // 958340231
    
    	vec.push_back(7);
    	push_heap(vec.begin(), vec.end());// 前面已经make_heap过,后面新增用push_heap
    	for (int i = 0; i < vec.size(); i++)
    		cout << vec[i] << " ";  // 9783502314
    
    	pop_heap(vec.begin(), vec.end());
    	cout << vec.back() << endl;// 9 有返回但是没有删除
    	vec.pop_back();//删除
    
    	sort_heap(vec.begin(), vec.end());
    	for (int i = 0; i < vec.size(); i++)
    		cout << vec[i] << " ";  // 012345678
    }

    priority_queue

    底层:最大堆,但是依权值高低自动递减排序。

    声明用法:(默认降序)

        //下面两种优先队列的定义是等价的,默认降序
        priority_queue<int> q;
        priority_queue<int,vector<int>,less<int> >;//后面有一个空格
        // 升序
        priority_queue<int,vector<int>,greater<int> >;

    基本操作

    增删元素:push(int x),  pop() 

    访问元素:top() , 

    判断:empty()   size()  

    #include <queue>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    int main(){
    	int a[9] = { 0, 1, 2, 3, 4, 8, 9, 3, 5 };
    	priority_queue<int> q(a, a + 9);
    
    	while (!q.empty()){
    		cout << q.top();// 985433210
    		q.pop();
    	}
    	return 0;
    }

     

    1、关联式容器

    set

    在set中每个元素的值都唯一,而且系统能根据元素的值自动进行排序。应该注意的是set中数元素的值不能直接被改变*iter=9错误

    声明用法:(默认升序)

        //下面两种优先队列的定义是等价的,默认升序
        set<int> q;
        set<int,vector<int>,less<int> >;//后面有一个空格
        // 降序
        set<int,vector<int>,greater<int> >;

    基本操作

    insert()   

    pair<iterator,bool> insert(int x);// 返回一个键值对<新插元素迭代器,成功与否>
    iterator insert(iteration position, int x);// 返回指向插入元素的迭代器
    void insert (Iterator first,Iterator second);// 范围

    erase()

    void erase(Iteration position);// 删除该迭代器指向位置元素
    void erase(Iteration first,Iteration second)// 区间上元素

    find(Iterator first,Iterator second, int x), count(int x), lower_bound(int x),upper_bound(int x),

    #include <set>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    int main(){
    	int a[5] = { 0,1,2,3,4 };
    	set<int> s(a,a+5);
    
    	s.insert(5);// 012345
    	s.erase(1);// 02345
    
    	// find函数返回迭代器
    	set<int>::iterator cc = s.begin();// 初始化迭代器
    	cc=s.find(3);
    	if (cc != s.end())
    		cout << "2 found" << endl;
    
    	// 企图通过迭代器修改set,不允许
    	*cc = 9;//错误
    
    	return 0;
    }

    map

    map和set一样是关联式容器,它们的底层容器都是红黑树,区别就在于map的值不作为键,键和值是分开的。它的特性如下:

    map以RBTree作为底层容器
    所有元素都是键+值存在
    不允许键重复
    所有元素是通过键进行自动排序的
    map的键是不能修改的,但是其键对应的值是可以修改的
    在map中,一个键对应一个值,其中键不允许重复,不允许修改,但是键对应的值是可以修改的,原因可以看上面set中的解释。

    #include <map>    
    #include <string>   
    #include <iostream>   
    using namespace std;  
      
    int main()    
    {   
        map<int, string> mapStudent;   // 构造map 
    
        mapStudent.insert(pair<int, string>(1, "student_one"));// map的insert,用pair  
        mapStudent.insert(pair<int, string>(2, "student_two"));  
        mapStudent.insert(pair<int, string>(3, "student_three"));  
     
        map<int, string>::iterator iter; // 迭代器 
        for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)  
           cout<<iter->first<<' '<<iter->second<<endl;  
    
        // find函数(关键值key),返回迭代器。
        iter=mapStudent.find(2)
    
        // 修改value
        iter->second=9;// 正确,关键值不可以修改。
    }  

    multiset

    multimap

    hashtable

    展开全文
  • 之所以被称为序列容器,是因为元素在容器中的位置同元素的值无关,即容器不是排序的。将元素插入容器时,指定在什么位置,元素就会位于什么位置。 排序容器 包括 set 集合容器、multiset多重集合容器、map映射容器...

    STL 容器种类和功能

    1. 序列容器
      主要包括 vector 向量容器、list 列表容器以及 deque 双端队列容器。之所以被称为序列容器,是因为元素在容器中的位置同元素的值无关,即容器不是排序的。将元素插入容器时,指定在什么位置,元素就会位于什么位置。
    2. 排序容器
      包括 set 集合容器、multiset多重集合容器、map映射容器以及 multimap 多重映射容器。排序容器中的元素默认是由小到大排序好的,即便是插入元素,元素也会插入到适当位置。所以关联容器在查找时具有非常好的性能。
    3. 哈希容器
      C++ 11 新加入 4 种关联式容器,分别是 unordered_set 哈希集合、unordered_multiset 哈希多重集合、unordered_map 哈希映射以及 unordered_multimap 哈希多重映射。和排序容器不同,哈希容器中的元素是未排序的,元素的位置由哈希函数确定。

    迭代器

    迭代器的分类

    1. 前向迭代器
      假设 p 是一个前向迭代器,则 p 支持 ++p,p++,*p 操作,还可以被复制或赋值,可以用 == 和 != 运算符进行比较。此外,两个正向迭代器可以互相赋值。
    2. 双向迭代器
      双向迭代器具有正向迭代器的全部功能,除此之外,假设 p 是一个双向迭代器,则还可以进行 --p 或者 p-- 操作(即一次向后移动一个位置)。
    3. 随机访问迭代器
      随机访问迭代器具有双向迭代器的全部功能。除此之外,假设 p 是一个随机访问迭代器,i 是一个整型变量或常量,则 p 还支持以下操作:
      p+=i:使得 p 往后移动 i 个元素。
      p-=i:使得 p 往前移动 i 个元素。
      p+i:返回 p 后面第 i 个元素的迭代器。
      p-i:返回 p 前面第 i 个元素的迭代器。
      p[i]:返回 p 后面第 i 个元素的引用。
      此外,两个随机访问迭代器 p1、p2 还可以用 <、>、<=、>= 运算符进行比较。
      在这里插入图片描述

    迭代器的定义

    1. 正向迭代器

      容器类名::iterator 迭代器名;

    2. 常量正向迭代器

      容器类名::const_iterator 迭代器名;

    3. 反向迭代器

      容器类名::reverse_iterator 迭代器名;

    4. 常量反向迭代器

      容器类名::const_reverse_iterator 迭代器名;
      示例:

    #include<bits/stdc++.h> 
    using namespace std;
    int main()
    {
    	//v被初始化成有10个元素
        vector<int> v{1,2,3,4,5,6,7,8,9,10}; 
        cout << "第一种遍历方法:随机访问迭代器支持" << endl;
        //像普通数组一样使用vector容器
        for (int i = 0; i < v.size(); ++i)
            cout << v[i] <<" "; 
        
        cout << endl << "第二种遍历方法:三种迭代器均支持" << endl;
        vector<int>::iterator i;
        //用 != 比较两个迭代器
        for (i = v.begin(); i != v.end(); ++i)
            cout << *i << " ";
        
        cout << endl << "第三种遍历方法:随机访问迭代器支持" << endl;
        //用 < 比较两个迭代器
        for (i = v.begin(); i < v.end(); ++i) 
            cout << *i << " ";
       
        cout << endl << "第四种遍历方法:随机访问迭代器支持" << endl;
        i = v.begin();
        //间隔一个输出   // 随机访问迭代器支持 "+= 整数"  的操作
        while (i < v.end()) { 
            cout << *i << " ";
            i += 2; 
        }
    }
    

    输出:
    在这里插入图片描述

    序列式容器

    • array<T,N>(数组容器):n个固定元素,随机访问
      表示可以存储 N 个 T 类型的元素,是 C++
      本身提供的一种容器。此类容器一旦建立,其长度就是固定不变的,这意味着不能增加或删除元素,只能改变某个元素的值;
    • vector(向量容器):尾部删除插入,随机访问
      用来存放 T类型的元素,是一个长度可变的序列容器,即在存储空间不足时,会自动申请更多的内存。使用此容器,在尾部增加或删除元素的效率最高(时间复杂度为O(1) 常数阶),在其它位置插入或删除元素效率较差(时间复杂度为 O(n) 线性阶,其中 n 为容器中元素的个数);
    • deque(双端队列容器):头部尾部删除插入,随机访问
      和 vector非常相似,区别在于使用该容器不仅尾部插入和删除元素高效,在头部插入或删除元素也同样高效,时间复杂度都是 O(1)常数阶,但是在容器中某一位置处插入或删除元素,时间复杂度为 O(n) 线性阶;
    • list(链表容器):任意位置删除插入,两个方向顺序访问
      是一个长度可变的、由 T类型元素组成的序列,它以双向链表的形式组织元素,在这个序列的任何地方都可以高效地增加或删除元素(时间复杂度都为常数阶O(1)),但访问容器中任意元素的速度要比前三种容器慢,这是因为 list 必须从第一个元素或最后一个元素开始访问,需要沿着链表移动,直到到达想要的元素。
    • forward_list(正向链表容器):任何位置删除插入,正向顺序访问
      和 list容器非常类似,只不过它以单链表的形式组织元素,它内部的元素只能从第一个元素开始访问,是一类比链表容器快、更节省内存的容器。

    vector容器包含的成员函数

    • begin() 返回指向容器中第一个元素的迭代器。
    • end() 返回指向容器最后一个元素所在位置后一个位置的迭代器,通常和 begin() 结合使用。
    • rbegin() 返回指向最后一个元素的迭代器。
    • rend() 返回指向第一个元素所在位置前一个位置的迭代器。
    • cbegin() 和 begin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
    • cend() 和 end() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
    • crbegin() 和 rbegin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
    • crend() 和 rend() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
    • size() 返回实际元素个数。
    • max_size() 返回元素个数的最大值。这通 常是一个很大的值,一般是 232-1,所以我们很少会用到这个函数。
    • resize() 改变实际元素的个数。
    • capacity() 返回当前容量。
    • empty() 判断容器中是否有元素,若无元素,则返回 true;反之,返回 false。
    • reserve() 增加容器的容量。
    • shrink _to_fit() 将内存减少到等于当前元素实际所使用的大小。
    • operator[ ] 重载了 [ ] 运算符,可以向访问数组中元素那样,通过下标即可访问甚至修改 vector 容器中的元素。
    • at() 使用经过边界检查的索引访问元素。
    • front() 返回第一个元素的引用。
    • back() 返回最后一个元素的引用。
    • data() 返回指向容器中第一个元素的指针。
    • assign() 用新元素替换原有内容。
    • push_back() 在序列的尾部添加一个元素。
    • pop_back() 移出序列尾部的元素。
    • insert() 在指定的位置插入一个或多个元素。
      insert示例代码:
    #include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        std::vector<int> demo{1,2};
        //第一种格式用法
        demo.insert(demo.begin() + 1, 3);//{1,3,2}
    
        //第二种格式用法
        demo.insert(demo.end(), 2, 5);//{1,3,2,5,5}
    
        //第三种格式用法
        std::array<int,3>test{ 7,8,9 };
        demo.insert(demo.end(), test.begin(), test.end());//{1,3,2,5,5,7,8,9}
    
        //第四种格式用法
        demo.insert(demo.end(), { 10,11 });//{1,3,2,5,5,7,8,9,10,11}
    
        return 0;
    }
    
    • erase() 移出一个元素或一段元素。
    • remove() 删除容器中所有和指定元素值相等的元素,并返回指向最后一个元素下一个位置的迭代器。值得一提的是,调用该函数不会改变容器的大小和容量。
    • clear() 移出所有的元素,容器大小变为 0。
    • swap() 交换两个容器的所有元素。
    • emplace() 在指定的位置直接生成一个元素。
    • emplace_back() 在序列尾部生成一个元素。

    示例:

    #include<bits/stdc++.h>
    using namespace std;
    int main(){
    	//	创建int类型vector容器 
    	vector<int>v;
    	//	获得vector容器容量 
    	cout<<v.size()<<endl;
    	//	向vector容器尾部插入元素 
    	v.push_back(1); 
    	v.push_back(2); 
    	cout<<v.size()<<endl;
    	//增加容器的容量,如果 vector 的容量在执行此语句之前,已经大于或等于 1 个元素
    	v.reserve(1);
    	cout<<v.size()<<endl;
    	v.reserve(10);
    	cout<<v.size()<<endl;
    	//创建指定容量和元素的vector
    	vector<int>va(10,-1);//第一个容量,第二个为值,默认为0 
    	//返回元素个数的最大值。这通常是一个很大的值,一般是 232-1,所以我们很少会用到这个函数。
    	cout<<va.max_size()<<endl; 
    	//改变实际元素的个数。
    	v.resize(0);
    	cout<<v.size()<<endl;
    	//返回当前容量。
    	cout<<va.capacity()<<endl;
    	//判断容器中是否有元素,若无元素,则返回 true;反之,返回 false。
    	cout<<va.empty()<<endl;
    	//将内存减少到等于当前元素实际所使用的大小。
    	va.shrink_to_fit();
    	cout<<va.size()<<endl;
    	//返回第一个元素的引用。
    	cout<<va.front()<<endl;
    	//返回最后一个元素的引用。
    	cout<<va.back()<<endl;
    	//返回指向容器中第一个元素的指针。
    	cout<<va.data()<<endl;
    	//移出序列尾部的元素。
    	va.pop_back();
    	//在指定的位置插入一个或多个元素。
    	va.insert(va.begin()+5,1);
    	cout<<va[5]<<endl;
    	//用新元素替换原有内容。
    	va.assign({1,1,1,1,1,1});
    	cout<<va[1]<<endl;
    	//移出一个元素或一段元素。
    	va.erase(va.begin()+1,va.begin()+3);
    	cout<<va.size()<<endl;
    	//va.clear()   移出所有的元素,容器大小变为 0。
    	//交换两个容器的所有元素。
    	swap(v,va);
    	cout<<va.size()<<endl;
    	return 0;
    } 
    

    在这里插入图片描述

    deque包含的成员函数
    deque包含的成员函数和vector基本一致,常用的增加了:

    • push_front() 在序列的头部添加一个元素。
    • pop_front() 移除容器头部的元素。

    list容器可用的成员函数

    • empty() 判断容器中是否有元素,若无元素,则返回 true;反之,返回 false。
    • size() 返回当前容器实际包含的元素个数。
    • max_size() 返回容器所能包含元素个数的最大值。这通常是一个很大的值,一般是 232-1,所以我们很少会用到这个函数。
    • front() 返回第一个元素的引用。
    • back() 返回最后一个元素的引用。
    • assign() 用新元素替换容器中原有内容。
    • emplace_front() 在容器头部生成一个元素。该函数和 push_front() 的功能相同,但效率更高。
    • push_front() 在容器头部插入一个元素。
    • pop_front() 删除容器头部的一个元素。
    • emplace_back() 在容器尾部直接生成一个元素。该函数和 push_back() 的功能相同,但效率更高。
    • push_back() 在容器尾部插入一个元素。
    • pop_back() 删除容器尾部的一个元素。
    • emplace() 在容器中的指定位置插入元素。该函数和 insert() 功能相同,但效率更高。
    • insert() 在容器中的指定位置插入元素。
    • erase() 删除容器中一个或某区域内的元素。
    • swap() 交换两个容器中的元素,必须保证这两个容器中存储的元素类型是相同的。
    • resize() 调整容器的大小。
    • clear() 删除容器存储的所有元素。
    • splice() 将一个 list 容器中的元素插入到另一个容器的指定位置。
    #include<bits/stdc++.h>
    using namespace std;
    int main(){
    	list<double>li1{3.1,2.2,2.9},li2{9.9,10.9};
    	//排序 
    	li1.sort();
    	for (auto it:li1) {
            std::cout << it << " ";
        }
        cout<<endl;
        //指向 li1 容器中的元素 2
        list<double>::iterator it = ++li1.begin();
        //调用第一种语法格式
        li1.splice(it, li2); // li1: 3.1,9.9,10.9,2.2,2.9
                        
        for (auto it:li1) {
            std::cout << it << " ";
        }
        cout<<endl;
        //调用第二种语法格式,将 [li1.begin(),li1.end())范围内的元素移动到 li1.begin() 位置处  
    	li2.splice(li2.begin(), li1, li1.begin(), li1.end());
    	for (auto it:li2) {
            std::cout << it << " ";
        }
    	return 0;
    } 
    

    在这里插入图片描述

    • remove(val) 删除容器中所有等于 val 的元素。
    #include<bits/stdc++.h>
    using namespace std;
    int main(){
    	list<int>li{1,3,5,2,4,3,5,3,3};
    	li.remove(3);
    	for (auto it:li) {
            std::cout << it << " ";
        }
    	return 0;
    } 
    

    在这里插入图片描述

    • remove_if() 删除容器中满足条件的元素。
    #include<bits/stdc++.h>
    using namespace std;
    int main(){
    	list<int>li{1,3,5,2,4,3,5,3,3};
    	li.remove_if([](int value) {return (value <= 3); }); 
    	for (auto it:li) {
            std::cout << it << " ";
        }
    	return 0;
    } 
    

    在这里插入图片描述

    • unique() 删除容器中相邻的重复元素,只保留一个。
    #include <iostream>
    #include <list>
    using namespace std;
    //二元谓词函数
    bool demo(double first, double second)
    {
        return (int(first) == int(second));
    }
    
    int main()
    {
        list<double> mylist{ 1,1.2,1.2,3,4,4.5,4.6 };
        //删除相邻重复的元素,仅保留一份
        mylist.unique();//{1, 1.2, 3, 4, 4.5, 4.6}
    
        for (auto it = mylist.begin(); it != mylist.end(); ++it)
            cout << *it << ' ';
        cout << endl;
        //demo 为二元谓词函数,是我们自定义的去重规则
        mylist.unique(demo);
    
        for (auto it = mylist.begin(); it != mylist.end(); ++it)
            std::cout << *it << ' ';
        return 0;
    }
    

    在这里插入图片描述

    • merge() 合并两个事先已排好序的 list 容器,并且合并之后的 list 容器依然是有序的。
    #include<bits/stdc++.h>
    using namespace std;
    int main(){
    	list<int>li{1,3,5,2,4,3,5,3,3},l2{9,8,1,5};
    	li.merge(l2); 
    	for (auto it:li) {
            std::cout << it << " ";
        }
    	return 0;
    } 
    

    在这里插入图片描述

    • sort() 通过更改容器中元素的位置,将它们进行排序。
    • reverse() 反转容器中元素的顺序。
    展开全文
  • 序列式容器概述

    2022-03-13 16:51:46
    序列式容器概述 一.容器概述及分类 容器就是存放东西的地方,而编程中有一些按特定方式排列的数据我们一般叫数据结构,这些数据结构可以配合算法帮助我们解决相关的问题,有一些使用广泛的数据结构如数组,队列,...
  • C++容器概述和序列式容器基本操作

    千次阅读 2018-02-02 18:40:31
    容器是一些特定类型对象的集合,容器类分为序列式容器和关联容器两种。容器基本操作 容器类的一些基本操作如下图:定义和初始化 每个容器都定义了一个默认构造函数。除array之外,其他容器的默认构造函数都会创建...
  • c++ STL中的五种序列式容器 序列式容器 序列容器,即以线性排列(类似普通数组的存储方式)来存储某一指定类型(例如 int、double 等)的数据,需要特殊说明的是,该类容器并不会自动对存储的元素按照值的大小...
  • 序列式容器 1 容器的概观与分类 2 vector 3 list 4 deque 5 stack 6 queue 7 heap 8 priority_queue 9 slist 4 序列式容器4.1 容器的概观与分类 序列式容器array、vector、heap、priority-queue、list、slist、deque...
  • STL中的容器可以分为序列式容器和关联式容器。序列式容器指其中的元素都可序,但未必有序。在STL中提供了vector, list, deque, stack, queue, priority_queue等等序列式容器。其中stack和queue是由deque改头换面而成...
  • C++ STL 序列式容器

    2019-08-07 00:26:29
    C++ STL 序列式容器 什么是序列式容器 序列容器就是以线性序列方法来存储元素的容器,它对元素的顺序和存放顺序相关,具体的容器主要有5种。分别是: 1、array<T,N> 数组容器,特点是长度固定,可以随机存取;...
  • vector,deque,list定义于namespace std中,这三者是STL的序列式容器,也就是元素的位置和你置入元素的方式顺序有关系,三者在存储方式上有很大不同,处于程序运行效率,不同的存储方式,也就提醒我们在不同的应用...
  • STL序列式容器之vector

    2016-07-10 23:14:38
    STL容器分为两类:分别是序列式容器和关联式容器。 序列式容器: vector, heap, priority_queue, list, slist, deque, stack, queue. 需要说明的是,heap内含一个vector,priority_queue内含一个heap,stack内含...
  • 序列式容器简介

    2019-01-09 22:00:18
    所谓序列式容器,表示其中的元素都是可以排序的,但未必是有序的。 C++本身提供了一个序列式容器数组array,STL另外有vector,list,deque,stack,queue,priority-queue等等序列式容器。stack和queue由于只是将deque...
  • 序列式容器详解序列式容器序列式容器共有函数:迭代器成员函数常用其他成员函数<1> array初始化array 特有常用函数<2> vector初始化vector特有常用函数<3>deque初始化 序列式容器 所谓STL序列式...
  • 上一节我们学习的stack是后入先出,这一节学的队列queue遵循先入先出的规则。 同stack一样,queue的压入和弹出元素操作为push和pop操作。 学习queue可以和stack进行对照,两者基本的框架和思路都是一样的。...
  • STL之序列式容器详解

    千次阅读 2018-05-30 19:15:55
    所谓序列式容器,其中的元素都可序,但未必有序,C++语言本身提供了一个序列式容器array,STL另外再提供vector、list、deque、stack、queue、priority-queue等序列容器。其中stack和queue由于只是将deque改头换面而...
  • 一、什么是序列式容器 以线性排列(类似普通数组的存储方式)来存储某一指定类型(例如 int、double 等)的数据 需要特殊说明的是: 该类容器并不会自动对存储的元素按照值的大小进行排序; 序列容器只是一类容器的...
  • STL序列式容器 - heap

    2016-04-07 14:02:10
    STL 源码剖析之四:序列式容器---heap STL- heap主要有以下几种操作组成: make_heap,建堆 sort_heap,堆排序 pop_heap,取出堆顶元素 push_heap,调整堆 heap并不归属于STL容器组件,它是个幕后英雄,...
  • 序列容器以线性序列的方式存储元素。它没有对元素进行排序,元素的顺序和存储它们的顺序相同。以下有5种标准的序列容器,每种容器都具有不同的特性: array<T,N>(数组容器)是一个长度固定的序列,有 N 个 T ...
  • 序列式容器(Sequence Containers):所谓序列式容器,其中的元素都可序(ordered),但未必有序(sorted)。C++语言本身提供了一个序列式容器array,STL另外再提供了vector,list,deque,stack,queue,priority-queue等等...
  • array 容器是在 C++ 普通数组的基础上,添加了一些成员函数和全局函数。在使用上,它比普通数组更安全,且效率并没有因此变差。array 容器的大小是固定的,无法动态的扩展或收缩,这也就意味着,在使用该容器的过程...

空空如也

空空如也

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

序列式容器

友情链接: untitled.zip