STL常用容器2

数据结构

发布日期: 2021-03-04

文章字数: 399

阅读时长: 1 分

阅读次数:

STL常用容器2

STL是低阶码农的归宿。—《不知名弹幕》

推荐赫斌老师的数据结构。 —《某不知名弹幕》

STL中List和vector是两个最常被使用的容器

vector容器

前端封闭，不可以从前端插入数
front()//首个元素
back()//最后一个元素
push_back()//尾插
pop_back()//删除尾部数据
v.begin()//第一个元素的位置
v.rbegin()//最后一个元素的位置
v.end()//最后一个元素的下一个位置
v.rend()//第一个元素的前一个位置
insert()//插入

vector可以视作数组，但是和数组有区别

数组的空间大小在程序运行前就已经分配完成，是静态空间

而vector可以动态拓展，动态拓展不是指在原有的内存空间续借空间，而是指将数据拷贝到更大的内存空间，删除原内存空间数据

vector容器支持可随机访问的迭代器，类似于数组的访问

迭代器：vector<T>::iterator

vector构造函数

函数原型：

vector<T> v;//采用模板实现类实现，默认构造函数
vector(v.begin(),v.end());//将v[v.begin(),v.end())区间中的数据拷贝到本身，无需模板指定数据类型
- 这个区间，前闭后开，即前面的数据可以取到，但是后面的数据无法取到，end指向的值是无意义的
vector(const vector &vec);//拷贝构造函数

void printv(vector& v)  //const vector& v
{
    for (vector::iterator it = v.begin(); it != v.end(); it++)
        cout << (*it);
    cout << endl;
}
void test01()
{
    vector v1;
    for (int i = 0; i < 10; i++)
    {
        v1.push_back(i);
    }
    printv(v1);
    //vector v2=(v1.begin(), v1.end());
    vector v2(v1.begin(), v1.end());
    printv(v2);
    vector v3(10, 100);  //前一个参数为数量，后一个参数为单个数据
    printv(v3);
    vector v4 = v3;
    printv(v4);
}
=>
    0123456789
    0123456789
    100100100100100100100100100100
    100100100100100100100100100100

vector赋值操作

函数原型：

vector& operator=(const vector &vec);//重载等号操作符
assign(beg,end);//将[beg,end）区间中的数据拷贝赋值给本身
assign(n,elem);//将n个elem拷贝赋值给本身

void test02()
{
    //vector赋值
    vector v1;
    for (int i = 0; i < 10; i++)
    {
        v1.push_back(i);
    }
    vector v2;
    v2 = v1;        //no.1
    printv(v2);
    vector v3;
    v3.assign(v1.begin(), v1.end());   //no.2
    printv(v3);
    vector v4;
    v4.assign(2, 829);    //no.3
    printv(v4);
}
=>
    0123456789
    0123456789
    829829

vector容量和大小

函数原型：

empty();//判断容器是否为空，为空返回1
capacity();//容器的容量
size();//返回容器中元素的个数
resize(int num);//重新指定容器的大小，如果容器变长，则以默认值填冲新位置，如果变短，末尾超出容器长度的元素被删除
resize(int num,elem);//同上，多出的用elem填充

void test03()
{
    //vector容器的容量和大小
    vector v;
    for (int i = 0; i < 10; i++)
    {
        v.push_back(i);
    }
    if (v.empty())
    {
        cout << "v为空";
    }
    else
    {
        cout << v.capacity() << endl;//容量
        cout << v.size() << endl;//元素个数
    }
    v.resize(15, 10);
    printv(v);
    v.resize(5);
    printv(v);
}
=>
    13
    10
    01234567891010101010
    01234

vector插入和删除

函数原型：

push_back(ele);//尾部插入元素ele
pop_back();//尾部删除元素
insert(const_iterator pos,ele);//迭代器指向位置pos插入元素ele
insert(const_iterator pos,int count,ele);//迭代器指向位置插入n个ele元素
erase(const_iterator pos);//删除迭代器指向的元素
erase(const_iterator start,const_iterator end);//删除迭代器从start到end之间的元素
clear();//删除容器中的所有元素

void test04()
{
    //vector的插入和删除
    vector v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);
    printv(v);
    v.pop_back();
    printv(v);
    //v.insert(2, 30);
    v.insert(v.begin(), 0);
    v.insert(v.end(), 3, 50);
    printv(v);
    v.erase(v.begin());
    printv(v);
    v.clear();
    printv(v);
}
=>
    10203040
    102030
    0102030505050
    102030505050

vector数据存取

函数原型：

at(int idx);//返回索引idx所指的数据
operator[];//返回索引idx所指的数据
front();//返回容器中第一个数据元素
back();//返回容器中最后一个数据元素

void test05()
{
    //vector的存取
    vector v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);
    cout<
    20301040

vector互换容器

vector预留空间

deque容器

基本概念

双端数组，可以对头部进行插入删除操作

deque容器的迭代器也是支持随机访问的

deque容器的迭代器：deque<int>::const_iterator

迭代器访问：

void printd(deque& d)
{
    //for(deque::const_iterator it=)
    for (deque::const_iterator it = d.begin(); it != d.end(); it++)
        cout << (*it);
}

deque构造函数

deque<T>;//默认构造形式
deque(beg,end);//构造函数将[beg,end)区间中的元素拷贝到容器中
deque(n,elem);//构造函数将n个elem拷贝给本身
deque(const deque&deq);//构造拷贝函数

void test01()
{
    deque d1;
    d1.push_back(10);
    d1.push_front(20);
    deque d2(d1.begin(), d1.end());
    deque d3(3, 30);
    deque d4 = d3;

    printd(d1); cout << endl;
    printd(d2); cout << endl;
    printd(d3); cout << endl;
    printd(d4);
}
=>
    2010
    2010
    303030
    303030

deque容器和vector容器的构造方式几乎一致

deque赋值操作

函数原型：

deque& operator=(const deque& deq);
deque.assign(beg,end);
deque.assign(n,elem);

deque大小操作

函数原型:

deque.empty();
deque.size();
deque.resize(int num);
deque.resize(int num,elem);

deque没有容量的概念

deque插入和删除

函数原型：

两端插入操作：

push_back();//尾插
pop_back();//尾删
push_front();//头插
pop_front();//头删

指定位置操作：

insert(pos,elem);//在pos位置插入elem的拷贝，返回该数据的位置
insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值
insert(pos,begin,end);//在pos位置插入区间[beg,end)中的数据，无返回值
clear();//清空容器中的数据
erase(pos);//删除pos位置的数据，返回下一个数据的位置
erase(begin,end);//删除[begin,end)区间中的数据,返回下一个数据的位置

插入和删除提供的位置不是元素序号或者下标，而是迭代器位置

deque数据存取

函数原型：

at(int idx);//返回索引idx所指的数据
operator[];//返回索引idx所指的数据
front();//返回容器第一个数据
back();//返回容器最后一个数据

deque排序

利用算法对deque容器进行排序，类似于vector容器中常用的算法for_each(begin,end,func);

deque容器排序算法：

sort(iterator begin,iterator end);//对beg和end区间内元素进行排序

#include
void test02()
{
    deque d;
    d.push_back(10);
    d.push_front(20);
    d.push_front(30);
    d.push_back(40);
    printd(d); cout << endl;
    sort(d.begin(), d.end());
    printd(d);
}
//sort从小到大排序
=>
    30201040
    10203040

stack容器

基本概念

stack是体现栈的容器，先进后出，只能访问栈顶元素

即只有顶端元素才可以被外界使用，因此栈不允许有遍历行为

栈中进入数据push

栈中弹出数据pop

常用接口

构造函数：

stack<T> stk;//默认构造函数
stack(const stack &stk);//拷贝构造函数

赋值操作：

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

数据存取：

push(elem);//从栈顶添加元素
pop();//从栈顶移除第一个元素
top();//返回栈顶元素

大小操作：

empty();//判空，栈空为1
size();//返回栈的大小

void test01()
{
    stack s;
    s.push(10);
    s.push(20);
    s.push(30);
    s.pop();
    cout << s.top() << endl;
    stack s2;
    s2 = s;
    cout << s.top();
}

queue容器

基本概念

即表示队列的数据结构，先进先出，有两个出口

允许从一端新增元素，从一端移除元素

只允许访问对头和队尾，因此不支持遍历整个队列

常用接口

构造函数：

queue<T>que;//queue采用模板类实现，queue对象的默认构造函数
queue(const queue &que);//拷贝构造函数

赋值操作：

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

数据存取：

队尾进，队头出

push(elem);//在队尾添加数据
pop();//在队头移除数据
back();//返回队尾元素
front();//返回队头元素

大小操作：

empty();//判空
size();//返回栈的大小

void test01()
{
    queue q;
    q.push(10);        //10 
    q.push(20);        //20 10
    q.push(30);        //30 20 10
    q.push(40);        //40 30 20 10
    if (!q.empty())
    {
        q.pop();    //40 30 20
    }
    cout << q.back() << endl;
    cout << q.front() << endl;
    queue q2;
    q2 = q;
    cout << q2.size();
}
=> 
    40
    20
    3

List容器

基本概念

list即表示链表的数据结构

是一种物理存储上非连续的存储结构，数据元素的逻辑关系通过指针链接来实现

链表由一系列结点组成

结点包括储存元素的数据域和存储指向下一个结点的指针(下一个结点的地址)

数据中，结点由结构体创建

STL中的链表是一个双向循环链表

List的存储空间并不是连续的物理存储空间，因此List的迭代器只支持前移和后移，是双向迭代器

List有一个重要的性质，插入操作和删除操作都不会造成原有list迭代器的失效，这在vector是不成立的

list构造函数

函数原型：

list lst;//list采用模板类实现，对象的默认构造形式
list(beg,end);//将[beg,end)区间内的元素拷贝到容器中
list(n,elem);//构造函数将n个elem拷贝到容器中
list(const list &lst);//拷贝构造函数

void test01()
{
    list lst1;
    lst1.push_back(20);
    lst1.push_back(30);
    lst1.push_front(10);
    printl(lst1);
    list lst2(lst1.begin(), lst1.end());
    printl(lst2);
    list lst3(2, 829);
    printl(lst3);
    listlst4;
    lst4 = lst3;
    printl(lst3);
}
=>
    102030
    102030
    829829
    829829

list赋值和交换

函数原型：

assign(beg,end);
assign(n,elem);
list& operator=(const list &lst);
swap(lst);//将lst与本身的元素互换

//交换
void test02()
{
    list lst1;
    lst1.push_back(20);
    lst1.push_back(30);
    lst1.push_front(10);
    list lst2(2, 829);
    cout << "交换前：" << endl;
    printl(lst1); 
    printl(lst2); 

    lst1.swap(lst2);

    cout << "交换后：" << endl;
    printl(lst1);
    printl(lst2); 
}
=>
    交换前：
    102030
    829829
    交换后：
    829829
    102030

list大小操作

函数原型：

size();//返回容器中元素个数
empty();//判断容器是否为空
resize(num);
resize(num,elem);

list插入和删除

函数原型：

push_back(elem);//在容器尾部添加一个元素
pop_back();//删除容器尾部的一个元素
push_front(elem);//在容器开头添加一个元素
pop_front();//删除容器开头的一个元素
insert(pos,elem);//在pos位置**插入elem元素的拷贝**，返回新数据的位置
insert(pos,beg,end);//在pos位置插入区间[beg,end)内的数据，无返回值
clear();//清除容器中所有元素
erase(pos);//删除pos位置的元素，返回下一个元素的位置
erase(beg,end);//删除[beg,end)区间中的元素，返回下一个元素的位置
**remove(elem);//移除容器中和elem值匹配的元素**

list数据存取

list不支持at访问和[]访问

因为list的迭代器是双向迭代器，不支持随机访问

函数原型：

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

//list容器的迭代器是双向迭代器，不支持随机访问
list::iterator it =L1.begin();
//it=it+1;//错误，不可以跳跃访问，即使是+1

list反转和排序

将容器中的元素反转，将容器中的数据排序

函数原型：

reverse();//反转链表
sort();//链表排序

bool myCompare(int val1,int val2)
{
    return val1 > val2;
}
void test03()
{
    list lst1;
    lst1.push_back(20);
    lst1.push_back(30);
    lst1.push_front(10);
    //sort(lst1.begin(),lst1.end());
    //无法使用这种随机迭代器访问的方式访问list
    lst1.sort();
    printl(lst1);
    lst1.sort(myCompare);
    printl(lst1);
}
//默认排序方式是从小到大
//对于自定义数据类型，必须要指定排序规则

=>
    102030
    302010

bool compare(Person& p1, Person& p2)
{
    if (p1.m_age == p2.m_age)
        return p1.m_height > p2.m_height;
    else
        return p1.m_age < p2.m_age;
}
//高级排序只是在排序规则上再进行一次逻辑规则制定

1doctorc1

https://1doctorc1.github.io/2021/03/04/stl-chang-yong-rong-qi-2/

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 1doctorc1 !

数据结构

STL常用容器3

2021-03-04 1doctorc1

STL与容器

2021-03-04 1doctorc1

数据结构

STL常用容器2

vector容器

vector构造函数

vector赋值操作

vector容量和大小

vector插入和删除

vector数据存取

vector互换容器

vector预留空间

deque容器

基本概念

deque构造函数

deque赋值操作

deque大小操作

deque插入和删除

deque数据存取

deque排序

stack容器

基本概念

常用接口

queue容器

基本概念

常用接口

List容器

基本概念

list构造函数

list赋值和交换

list大小操作

list插入和删除

list数据存取

list反转和排序

你的赏识是我前进的动力