C++ 标准模板库 STL 顺序容器详解

C++ 标准模板库 STL 顺序容器

容器 数据结构 顺序性 重复性 支持迭代器
vector 动态数组 无序 可重复 随机访问迭代器
deque 双向队列 无序 可重复 随机访问迭代器
list 双向链表 无序 可重复 双向迭代器

动态数组 vector

vector #include <vector> 动态数组:其元素在内存中是连续存放的,随机存取任何元素都可以在常数时间内完成,在该容器的尾部增删元素也几乎能够在常数时间内完成具有较好的性能。

​ 一个 vector 常用函数使用实例如下:

#include <iostream>
#include <vector>
using namespace std;
template<class T>
void printVector(T s, T e){
    for(;s != e; ++s){
        cout << *s << ' ';
    }
    cout << endl;
}

int main(){
    int a[5] = {1,2,3,4,5};
    vector<int> v(a,a+5);
    cout << "1)" << v.end() - v.begin() << endl;
    cout << "2)";
    printVector(v.begin(), v.end());
    v.insert(v.begin()+3, 100); // insert()函数插入元素
    cout << "3)";
    printVector(v.begin(), v.end());

    vector<int> v2(5,0);
    v2.insert(v2.begin()+2,v.begin(),v.end()); // insert() 函数数据块插入
    cout << "4)";
    printVector(v2.begin(), v2.end());
    v.erase(v.begin()+3); // erase() 函数删除元素
    cout << "5)";
    printVector(v.begin(), v.end());
    v.erase(v.begin()+2,v.begin()+4); // erase() 函数删除数据块
    cout << "6)";
    printVector(v.begin(), v.end());

    return 0;
}

构造函数

函数 函数描述
vector 构造函数创建一个 vector,可以设定大小 nSize
vector(const vector&) 拷贝构造函数,可以对区间内另一个数组的元素进行拷贝
operator= 将新内容分配给容器,替换其当前内容,并相应地修改其大小
assign 将新内容分配给 vector,替换其当前内容,并相应地修改其 size

容量管理函数

函数 函数描述
size 返回容器中元素的数量
max_size 返回容器可容纳的最大元素数
resize 调整容器的大小,使其包含 n(参数)个元素
capacity 返回当前为 vector 分配的存储空间(容量)的大小
empty 返回 vector 是否为空
reserve 请求 vector 容量至少足以包含 n(参数)个元素
shrink_to_fit 要求容器减小其 capacity(容量)以适应其 size(元素数量)

增删函数

函数 函数描述
push_back 在容器的最后一个元素之后添加一个新元素
pop_back 删除容器中的最后一个元素,有效地将容器 size 减少一个
insert 通过在指定位置的元素之前插入新元素来扩展该容器,通过插入元素的数量有效地增加容器大小
erase 从 vector 中删除单个元素(position)或一系列元素([first,last)),这有效地减少了被去除的元素的数量,从而破坏了容器的大小
clear 从 vector 中删除所有的元素(被销毁),留下 size 为 0 的容器
emplace 通过在 position(参数)位置处插入新元素 args(参数)来扩展容器
emplace_back 在 vector 的末尾插入一个新的元素,紧跟在当前的最后一个元素之后

索引函数

函数 函数描述
operator[] 返回容器中第 n(参数)个位置的元素的引用
at 返回容器中第 n(参数)个位置的元素的引用
front 返回对容器中第一个元素的引用
back 返回对容器中最后一个元素的引用
data 返回指向容器中第一个元素的指针

迭代器函数

函数 函数描述
begin 返回指向容器中第一个元素的迭代器
end 返回指向容器中最后一个元素之后的理论元素的迭代器
rbegin 返回指向容器中最后一个元素的反向迭代器
rend 返回一个反向迭代器,指向中第一个元素之前的理论元素
cbegin 返回指向容器中第一个元素的常量迭代器(const_iterator)
cend 返回指向容器中最后一个元素之后的理论元素的常量迭代器(const_iterator)
crbegin 返回指向容器中最后一个元素的常量反向迭代器(const_reverse_iterator)
crend 返回指向容器中第一个元素之前的理论元素的常量反向迭代器(const_reverse_iterator)

用 vector 实现二维数组

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

int main(){
    vector<vector<int>> arr(3); // arr中有 3 个元素,每个元素都是 vector<int> 容器
    for(int i=0; i<arr.size(); ++i){
        for(int j=0; j<3; ++j){
            arr[i].push_back(j);
        }
    }
    for(int i=0; i<arr.size(); ++i){
        for(int j=0; j<3; ++j){
            cout << arr[i][j] << ' ';
        }
        cout << endl;
    }
    return 0;
}

双向队列 deque

deque #include <deque> 双向队列:其元素在内存中是连续存放的,随机存取任何元素都可以在常数时间内完成,在该容器的两端增删元素也几乎能够在常数时间内完成具有较好的性能。

​ 所有适用于 vector 的操作都适用于 deque,除此之外,deque 还有 push_front / pop_front 在最前端插入或删除元素的操作,复杂的都是 O ( 1 ) O(1) O(1) 。

函数 函数描述
deque 构造函数
push_back 在容器的末尾添加一个新元素
push_front 在容器的开头插入一个新元素
pop_back 删除容器中的最后一个元素,同时将容器大小减少一个
pop_front 删除容器中的第一个元素,同时将容器大小减少一个
emplace_front 在容器的开头插入一个新的元素
emplace_back 在容器的末尾插入一个新的元素

双向链表 list

list #include <list> 双向链表:其元素在内存中是不连续存放的,不支持随机存取,在该容器的任何位置增删元素几乎都能够在常数时间内完成具有较好的性能。

list 除了具有所有顺序容器都有的成员函数之外,还支持以下8个成员函数:

函数 函数描述
push_front 在容器的开头插入一个新元素
pop_front 删除容器中的第一个元素
sort 元素排序,值得注意的是 list 不支持 STL 算法中的 sort
remove 删除和指定值相等的所有元素
unique 删除所有和前一个元素相同的元素,使得元素不重复,使用之前需要sort
merge 合并两个链表,并清空被合并的那个链表
reverse 颠倒链表内容
splice 在指定位置前面插入另一链表中的一个或多个元素,并在该链表中删除这些元素

​ 一个 list 的成员函数使用实例如下:

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

class A{
    private:
        int n;
    public:
        A(int n_){n = n_;}
        friend bool operator<(const A & a1, const A & a2);
        friend bool operator==(const A & a1, const A & a2);
        friend ostream& operator<<(ostream & o, const A & a2);
};

bool operator<(const A & a1, const A & a2){
    return a1.n < a2.n;
}

bool operator==(const A & a1, const A & a2){
    return a1.n == a2.n;
}

ostream& operator<<(ostream & o, const A & a2){
    o << a2.n;
    return o;
}

template <class T>
void printList(T start, T end){
    for(;start != end; ++start){
        cout << *start << ',';
    }
    cout << endl;
}

int main(){
    list<A> lst1, lst2;
    lst1.push_back(1); lst1.push_back(3);
    lst1.push_back(2); lst1.push_back(4);
    lst1.push_back(2);
    lst2.push_back(10); lst2.push_back(50);
    lst2.push_back(30); lst2.push_back(30);
    lst2.push_back(40); lst2.push_back(40);
    lst2.push_back(30); lst2.push_back(20);
    cout << "1) ";
    printList(lst1.begin(),lst1.end());
    cout << "2) ";
    printList(lst2.begin(),lst2.end());
    lst2.sort(); // 调用 sort 成员函数进行 lst2 排序
    cout << "3) ";
    printList(lst2.begin(),lst2.end());
    lst2.unique(); // 删除 lst2 中所有和前一个元素相等的元素
    cout << "4) ";
    printList(lst2.begin(),lst2.end());
    lst2.pop_front(); // 将 lst2 的第一个元素删除
    cout << "5) ";
    printList(lst2.begin(),lst2.end());
    lst1.remove(2); // 删除 lst1 中所有值为 2 的元素
    cout << "6) ";
    printList(lst1.begin(),lst1.end());
    lst2.merge(lst1); // 将 lst1 中的元素合并到 lst2 并将 lst1 清空
    cout << "7) ";
    printList(lst2.begin(),lst2.end());
    lst2.reverse(); // 颠倒 lst2
    cout << "8) ";
    printList(lst2.begin(),lst2.end());

    lst1.push_back(100); lst1.push_back(200);
    lst1.push_back(300); lst1.push_back(400);
    cout<<"9) ";
    printList(lst1.begin(),lst1.end());
    // 找到列表中的指定元素
    list<A>::iterator p1,p2,p3;
    p1 = find(lst2.begin(),lst2.end(),4);
    p2 = find(lst1.begin(),lst1.end(),200);
    p3 = find(lst1.begin(),lst1.end(),400);
    lst2.splice(p1,lst1,p2,p3); // 将 lst1 中 [p2,p3) 区间内的元素插入到 lst2 中 p1 位置之前,并将这些元素从 lst1 中删除
    cout<<"10) ";
    printList(lst1.begin(),lst1.end());
    cout<<"11) ";
    printList(lst2.begin(),lst2.end());

    return 0;
}

到此这篇关于C++ 标准模板库 STL 顺序容器详解的文章就介绍到这了,更多相关C++ 标准模板库 STL 内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C++标准模板库vector的常用操作

    一:介绍 vector是C++标准模板库,是一个容器,底层是数组,为连续内存. 命名空间为std,所属头文件为<vector>   注意:不是<vector.h> vector存储数据时,会分配一个存储空间,如果继续存储,该分配的空间已满,就会分配一块更大的内存,把原来的数据复制过来,继续存储,这些性能也会一定程度上会有损耗 二:常用操作 容量: a.vector大小:vector.size() b.vector所占内存实际大小:vector.capacity() 修改: a.尾部

  • C++(STL库)之顺序容器vector的使用

    一.特点 ①总的来说:可变大小数组.支持快速随机访问.在尾部之外的位置插入或删除元素可能很慢 ②元素保存在连续的内存空间中,因此通过下标取值非常快 ③在容器中间位置添加或删除元素非常耗时 ④一旦内从重分配,和原vector相关的指针,引用,迭代器都失效.内存重分配耗时很长 二.头文件.using声明 头文件:#include <vector> using声明:using std::vector; 三.初始化 vector<T>  v1; ==>v1是一个空的vector ve

  • C++标准模板库函数sort的那些事儿

    STL里面有个sort函数,可以直接对数组排序,复杂度为n*log2(n).sort()定义在在头文件<algorithm>中.sort函数是标准模板库的函数,已知开始和结束的地址即可进行排序,可以用于比较任何容器(必须满足随机迭代器),任何元素,任何条件,执行速度一般比qsort要快.另外,sort()是类属函数,可以用于比较任何容器,任何元素,任何条件. 具体事例如下:char ch[20]="sdasdacsdasdas";cout<<ch<<

  • C++标准模板库map的常用操作

    一:介绍 map是STL的关联式容器,以key-value的形式存储,以红黑树(平衡二叉查找树)作为底层数据结构,对数据有自动排序的功能. 命名空间为std,所属头文件<map> 注意:不是<map.h> 二:常用操作 容量: a.map中实际数据的数据:map.size() b.map中最大数据的数量:map.max_size() c.判断容器是否为空:map.empty() 修改: a.插入数据:map.insert() b.清空map元素:map.clear() c.删除指定

  • C++标准模板库STL的介绍

    介绍 STL(standard template library)标准模板库,是一种高效的C++程序库. STL分为三类:container(容器),iterator(迭代器)和algorithm(算法). 容器(container) 容器是用来管理某一类对象的集合,包括序列式容器和关联式容器. 序列式容器:vector,list,deque 关联式容器:map,set 遵循规则: 1.所有容器中存放的都是值而非引用.因此容器中的每个元素必须能够被拷贝,如想存放的不是副本,容器元素只能是指针.

  • C++ 标准模板库 STL 顺序容器详解

    C++ 标准模板库 STL 顺序容器 容器 数据结构 顺序性 重复性 支持迭代器 vector 动态数组 无序 可重复 随机访问迭代器 deque 双向队列 无序 可重复 随机访问迭代器 list 双向链表 无序 可重复 双向迭代器 动态数组 vector ​ vector #include <vector> 动态数组:其元素在内存中是连续存放的,随机存取任何元素都可以在常数时间内完成,在该容器的尾部增删元素也几乎能够在常数时间内完成具有较好的性能. ​ 一个 vector 常用函数使用实例如

  • 对python3标准库httpclient的使用详解

    如下所示: import http.client, urllib.parse import http.client, urllib.parse import random USER_AGENTS = [ "Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; SV1; AcooBrowser; .NET CLR 1.1.4322; .NET CLR 2.0.50727)", "Mozilla/4.0 (compatible; M

  • Golang 标准库 tips之waitgroup详解

    WaitGroup 用于线程同步,很多场景下为了提高并发需要开多个协程执行,但是又需要等待多个协程的结果都返回的情况下才进行后续逻辑处理,这种情况下可以通过 WaitGroup 提供的方法阻塞主线程的执行,直到所有的 goroutine 执行完成. 本文目录结构: WaitGroup 不能被值拷贝 Add 需要在 Wait 之前调用 使用 channel 实现 WaitGroup 的功能 Add 和 Done 数量问题 WaitGroup 和 channel 控制并发数 WaitGroup 和

  • python 标准库原理与用法详解之os.path篇

    os中的path 查看源码会看到,在os.py中有这样几行 if 'posix' in _names: name = 'posix' linesep = '\n' from posix import * #省略若干代码 elif 'nt' in _names: from nt import * try: from nt import _exit __all__.append('_exit') except ImportError: pass import ntpath as path #...

  • C++ STL容器详解之红黑树部分模拟实现

    目录 一.红黑树的概念 二.红黑树的性质 三.红黑树节点的定义 四.红黑树结构  五. 红黑树的插入操作 六.代码 总结 一.红黑树的概念 红黑树(Red Black Tree),是在计算机科学中用到的一种数据结构,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black. 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的. 二.红黑树的性质 1. 每个结点不是红色就是黑色: 2. 根节点是黑色的:

  • Python标准库之time库的使用教程详解

    目录 1.时间戳 2.结构化时间对象 3.格式化时间字符串 4.三种格式之间的转换 time模块中的三种时间表示方式: 时间戳 结构化时间对象 格式化时间字符串 1.时间戳 时间戳1970.1.1到指定时间到间隔,单位是秒 import time print(time.time()) 输出: 1649834054.98593 计算一个小时之前的时间戳 #计算一个小时之前的时间戳 print(time.time() - 3600) 输出: 1649830637.5699048 2.结构化时间对象

  • Python标准库time使用方式详解

    目录 1.time库 1.1.获取格林威治西部的夏令时地区的偏移秒数 1.2.时间函数 1.3.格式化时间.日期 1.4.单调时钟 1.time库 时间戳(timestamp)的方式:通常来说,时间戳表示的是从1970年1月1日00:00:00开始按秒计算的偏移量 结构化时间(struct_time)方式:struct_time元组共有9个元素 格式化的时间字符串(format_string),时间格式的字符串 1.1.获取格林威治西部的夏令时地区的偏移秒数 如果该地区在格林威治东部会返回负值(

随机推荐