0
  • 聊天消息
  • 系统消息
  • 评论与回复
登录后你可以
  • 下载海量资料
  • 学习在线课程
  • 观看威廉希尔官方网站 视频
  • 写文章/发帖/加入社区
会员中心
创作中心

完善资料让更多小伙伴认识你,还能领取20积分哦,立即完善>

3天内不再提示

STL的概述

汽车电子威廉希尔官方网站 来源:wenzi嵌入式软件 作者: wenzid 2023-01-20 17:08 次阅读

STL 概述

C++ STL 是一套功能强大的 C++ 模板类,提供了通用的模板类和函数,这些模板类和函数可以实现多种流行和常用的算法,关于 STL 呢,下面通过一个系统框图来对其进行一个总结:

图片

image-20210812170610134

可以看到,其主要包含 6 大方面,分别是:

  • 容器:一个容器就是一些特定类型对象的集合。STL容器分为两大类:序列式容器和关联式容器
  • 序列式容器:为程序员提供了控制元素存储和访问顺序的能力。这种顺序不依赖于元素的值,而是与元素加入容器时的位置相对应。
  • 关联式容器:关联容器中的元素是按照关键字来保存和访问的。关联式容器支持高效的关键字查找和访问,STL有两个主要的关联式容器:map 和 set。
  • 算法:STL 通过函数模板提供了很多作用于容器的通用算法,例如查找、插入、删除、排序等,这些算法均需要引入头文件,所有的 STL算法都作用在由迭代器所标识出来的区间上,可以分为两类:
  • 质变算法:运算过程中会更改区间内 迭代器所指向的内容,如分割,删除
  • 非质变算法:运算过程中不会改变区间内迭代器所指向的内容,如匹配,计数等算法
  • 迭代器:迭代器提供对一个容器中的对象的访问方法,并且定义了容器中的对象的范围。迭代器就如同一个指针。事实上,C++的指针也是一种迭代器。
  • 仿函数:仿函数在 C++ 标准中采用的名称是函数对象。仿函数主要用于 STL 中的算法中,虽然函数指针也可以做为算法的参数,但是函数指针不能满足 STL 对于抽象的要求
  • 配接器:配接器又被称之为是适配器,通俗来讲,适配器就是以序列式容器为底层数据结构,进一步封装了的为适应场景应用的容器。STL中提供了三种适配器,分别为: stackqueue ,priority_queue
  • 配置器:以 STL 运用的角度而言,空间配置器是最不需要介绍的,它总是藏在一切组件的背后,默默工作。整个 STL 的操作对象都存放在容器之中,而容器需要配置空间以放置资料,这就是空间配置器的作用。

在对 STL 标准库做了一个总体的概述之后,进一步详细地对每个部分进行叙述。

容器

在一份资料中看到,容器是这样被形容的:

容器,置物之所也

对于容器来说,又分为序列式容器和关联式容器,这里先从序列式容器开始说起

序列式容器

序列式容器:其中的元素都可序,但是未必有序。C++语言本身提供了一种序列式容器arraySTL另外提供了 vectorlistdequestackqueuepriority-queue等序列容器。其中stackqueue只是由deque改头换面而成,威廉希尔官方网站 上称为一种配接器。

下面将对几种序列式容器进行阐述:

vector

vector 是一个拥有扩展功能的数组,我们可以创建任何类型的 vector

比如说,我们可以通过如下的方式创建一个二一维数组:

vector A1 {1,2,3,4,5};

对于一维数组的初始化,也可以采用如下的方式进行:

vector A1(10);     /* 带参数构造,10个数据都是 0 */
vector A2(10,1);   /* 带参数构造,10个数据全是 1 */

除了上述这种给出数据的初始化方式以外,也可以通过同类型来进行初始化,比如下面这样:

vector  A3(12,1);
vector  A4(A3);          /* 通过 A3 来初始化 A4 */

也可以通过创建一个存储 vector元素的 vector的形式来创建一个二维数组:

vector> Matrix {{1,2,3},{4,5,6},{7,8,9}};

也可以通过如下的方式来初始化二维数组:

vectorint>> Matrix(N,vector<int>(M,-1));

上述代码的意思就是说,创建了一个 N*M 的矩阵,并且用 -1 填充所有位置上的值。

在创建了一个vector之后,又该如何访问内部的数据成员呢?有如下几种方式:

vector<int> A1 = {1,2,3,4,5};
vector<int>::iterator k1 = A1.begin();
cout << *k1 << endl;
cout << *(k1 + 1) << endl;

vector<int>::iterator k2 = A1.end();    /* 返回最后一个元素的下一个地址 */
cout << *(k2 - 1) << endl;

cout << A1.at(0) << endl;

上述代码经过运行之后,输出的结果如下所示:

1
2
5
1

紧接着,就是关于元素的插入,删除,插入删除可以使用下面方法:

A1.pop_back();               /* 删除最后一个元素 */
A1.push_back();              /* 在末尾添加一个元素 */

当然,也可以在特定位置插入元素,如下所示:

vector A1 = {1,2,3,4,5};
vector::iterator k = A1.begin();
A1.insert(k + 1, 9);

插入元素之后,A1里的元素变为:

1,9,2,3,4,5

在叙述 vector的开头,就说了vector是一个具有扩展功能的数组,也就是说 vector的容量是可以扩充的,如下就有一个例子:

最后,来叙述一些 vector的遍历方式:

for (int i = 0; i < A.size(); i++)
{
    cout << A1[i] << endl
}

上述这种方式是和C语言中普通数组的遍历方式一样的,在C++ 中除了这种遍历方式,还有其余的方式,比如:

for (vector<int>::iterator k = A1.begin(); k != A1.end(); k++)
{
    cout << *k << endl;
}

除此之外,还有一种稍微简便一点的方式,用 auto 来推导迭代:

for (auto iter = A1.begin(); iter != A1.end(); iter++)
{
    cout << *iter << endl;
}

除此之外,还有更为简洁的,如下所示:

for (auto i : A1)
{
    cout << i << endl;
}

list

对比于 vector的连续线性空间,list显得复杂许多,他的好处是每次插入或者删除一个元素,就配置或者释放一个元素空间。因此list对于空间的运用有着绝对的精准,一点也不浪费。而且对于任何位置的元素插入或者元素移除,list永远是常数时间。下图展示了 list双向链表容器是如何存储元素的:

图片

image-20210815154103144

在使用 list 的时候,需要包含下面两行代码:

#include 
using namespace std;

根据不同的使用场景,有如下几种方式创建 list 容器:

list<int> values;        /* 空的 list 容器 */
list<int> values(10);    /* 创建一个包含 n 个元素的 list 容器 */
list<int> values(10,5);  /* 创建了一个包含 10 个元素且值都为 5 的容器 */
list<int> values2(values);

可以看到上述的初始化的方法和vector一样,都是有这么几种方式,同样的,和vector一样,list也提供了push_back,pop_back方法,而且由于是双链表的原因,也可以从头部插入或者删除数据:push_front,pop_front

#include 
#include 
#include 

using namespace std;

int main(int argc, char **argv)
{
    list<int> mylist;

    mylist.push_back(33);
    mylist.push_back(22);
    mylist.push_front(11);

    for (auto n: mylist)
    {
        cout << n << endl;
    }

    mylist.front() -= mylist.back();
    mylist.insert(mylist.begin(),0);

    cout << "^^^^^^^^^^^^^^^^^^^^^^^^^" << endl;
    for (auto n : mylist)
    {
        cout << n << endl;
    }
    cout << "========================" << endl;
    mylist.erase(--mylist.end());

    for (auto n : mylist)
    {
        cout << n << endl;
    }
}

上述代码最终的输出结果如下所示:

11
33
22
^^^^^^^^^^^^^^^^^^^^^^^^^
0
-11
33
22
========================
0
-11
33

对比结果,和代码就可以清除地知道具体地作用,在这里需要注意地就是:mylist.begin()mylist.end()返回的分别是:返回容器中第一个元素的双向迭代器,返回指向容器中最后一个元素所在位置的下一个位置的双向迭代器。

上述所叙述的基本是 list相对比与 vector相同的部分,那么两者不同的部分呢,由于 list 数据结构的特殊,也提供了一些 vector 没有的操作,比如说:

  • splice: 将某个连续范围的元素从一个 list 迁移到另一个(或者同一个)list 的某个节点
  • remove: 删除list中指定值的元素,和 erase 不同,这里是根据值而不是位置去删除。
  • merge: 合并两个有序链表并使之有序。
  • sort: 针对 list 的特定排序算法,默认的算法库中的sort需要随机访问迭代器,list并不能提供

先从 splice说起,对于splice来说,其主要有如下三种原型:

void splice(iterator position, list  &x);
void splice(iterator position, list  &x, iterator it);
void splice(iterator position, list  &x, iterator first, iterator last);

下面分别就这三种原型进行叙述:

#include 
#include 
#include 

using namespace std;

int main(int argc, char** argv)
{
    list<int> mylist1, mylist2;
    list<int>::iterator it;

    for (int i = 0; i <= 4; i++)
        mylist1.push_back(i);

    for (int i = 0; i <= 3; i++)
        mylist2.push_back(i*10);

    it = mylist1.begin();
    it++;

    mylist1.splice(it,mylist2);

    for (auto n : mylist1)
        cout << n << endl;
}

代码输出结果为:

1
10
20
30
2
3
4

这里需要注意的是:此处的 it由于是指向的mylist1,经过splice后,此迭代器依然存在于 mylist1中,所以没有失效。

#include 
#include 
#include 

using namespace std;

int main(int argc, char** argv)
{
    list<int> mylist1, mylist2;
    list<int>::iterator it;

    for (int i = 0; i <= 4; i++)
        mylist1.push_back(i);

    for (int i = 0; i <= 3; i++)
        mylist2.push_back(i*10);

    it = mylist1.begin();
    it++;

    mylist1.splice(it,mylist2);

    for (auto n : mylist1)
        cout << n << endl;
    cout << "^^^^^^^^^^^^^^^^^^^^^" << endl;

    mylist2.splice(mylist2.begin(), mylist1, it);

    /* mylist1: 1, 10, 20, 30, 3, 4
    *  mylist2: 2
    *  it 现在就无效了
    */

    cout << "====================" << endl;

    it = mylist1.begin(); /* 现在 it 指向的是 1 */
    advance(it, 3);       /* 现在 it 就指向的是 30 */

    mylist1.splice(mylist.begin(), mylist1, it, mylist.end());
    /* 经过上述这么操作之后 */
    /* mylist1 就变成了:30 3 4 1 10 20 */
}

上述注释对 splice三种原型进行了常数,结合注释也能够清楚地知道具体地功能。

除了splice以外,还有remove函数以及 merge 和sort也是区别于vector的,所涉及的代码如下所示:

#include 
#include 
#include 

using namespace std;

int main(int argc, char** argv)
{
    list  mylist;
    mylist.push_back('A');
    mylist.push_back('B');
    mylist.push_back('C');
    mylist.remove("B");

    mylist.sort();

    for (auto n : mylist)
           cout << n << endl;  

    return 0;
}

最终输出的结果为:

int main(int argc, char** argv)
{
    list  mylist;
    mylist.push_back("one");
    mylist.push_back("two");
    mylist.push_back("three");
    mylist.remove("two");

    mylist.sort();

    for (auto n : mylist)
           cout << n << endl;  

    return 0;
}

关于 merge,使用起来也很简单,它的作用是将两个有序序列进行合并,注意,必须是有序序列,并且,两种序列的排序方式是一致的,也就是说,要么都是升序,要么都是降序。下面是关于 merge的使用例子:

#include
#include

int main(){
    // declaring the lists
    // initially sorted, use sort() if unsorted
    std::list<int> list1 = { 10, 20, 30 };
    std::list<int> list2 = { 40, 50, 60 };

    // merge operation
    list2.merge(list1);

    std::cout << "List:  ";

    for (auto it = list2.begin(); it != list2.end(); ++it)
        std::cout << *it << " ";

    return 0;
}

代码输出的结果是:10,20,30,40,50,60

deque

vector 是单向开口的连续线性空间,deque 则是一种双向开口的连续线性空间。所谓双向开口,意思是可以在头尾两端分别做元素的插入和删除工作,deque 和 vector 的差异在于:

  • deque 允许常数时间内对起头端进行元素的插入或移除操作
  • deque 没有所谓的容量(capacity)概念,因为它是动态地以分段连续空间组合而成,随时可以增加一段新的空间并链接起来。

关于deque要指出的一点是,它的迭代并不是普通的指针,其复杂度要大的多,因此除非必要,应该尽可能使用 vector 而非 deque。对 deque 进行排序操作,为了提高效率,可以先将 deque 完整复制到一个 vector 中,将 vector 排序后(利用 STL sort),再复制回 deque。

下面是关于 deque的一个例子:

std::deque<int> mydeque;

// set some initial values:
for (int i=1; i<6; i++) mydeque.push_back(i);   // 1 2 3 4 5
std::deque<int>::iterator it = mydeque.begin();
++it;
it = mydeque.insert (it,10);
mydeque.erase(--mydeque.end());
for(auto n: mydeque) std::cout << n << " ";     // 1 10 2 3 4

适配器

在本文的最开头给出了适配器的概念,再来回顾一下,就是:适配器就是以序列式容器为底层数据结构,进一步封装了的为适应场景应用的容器。STL中提供了三种适配器,分别为: stackqueue ,priority_queue

stack

Stack (堆栈) 是一个容器类的改编,为程序员提供了堆栈的全部功能,也就是说实现了一个先进后出 (FILO)的数据结构,其示意图如下所示:

图片

image-20210815225740108

它主要支持如下操作:

  • empty: 判断 栈是否为空
  • size: 取得栈的大小
  • top: 取得栈顶的元素
  • push:入栈操作
  • pop: 出栈操作

stack 的所有元素都必须满足先进后出的机制,只有stack顶的元素,才有机会被外界取用,以此stack不提供迭代器,关于它的简单的使用例子如下所示:

#include
#include

using namespace std;

int main(int argc, char **argv)
{
    stack<int> mystack;

    for (int i = 0; i < 4; i++)
        mystack.push(i);

    cout << "pop out element..." << endl;

    while (!mystack.empty())
    {
        cout << mystack.top();
    }

    cout << "\\n" << endl;
    return 0;
}
输出:
// Popping out elements... 4 3 2 1 0
queue

queue 是一种先进先出(FIFO)的数据结构,允许从最底部加入元素,同时取得最顶部元素。STL以 deque 作为缺省情况下的 queue 底部结构,下面queue的示意图:

图片

image-20210815230959996

代码如下所示:

std::queue<int> myqueue;
for (int i=0; i<5; ++i) myqueue.push(i);
std::cout << "Popping out elements...";
while (!myqueue.empty())
{
   std::cout << ' ' << myqueue.front();
   myqueue.pop();
}
std::cout << '\\n';
// Popping out elements... 0 1 2 3 4
return 0;
priority queue

优先队列(priority queue)允许用户以任何次序将任何元素推入容器内,但取出时一定是从优先权最高的元素开始取。优先队列具有权值观念,其内的元素并非依照被推入的次序排列,而是自动依照元素的权值排列,权值最高者排在最前面。

优先队列完全以底部容器为根据,加上 heap 处理规则,具有修改某物接口,形成另一种风貌的性质,因此是配接器。优先队列中的所有元素,进出都有一定的规则,只有queue顶部的元素(权值最高者),才有机会被外界取用。因此并不提供遍历功能,也不提供迭代器。

优先队列的构造函数和其他序列式容器的略有不同,因为需要指定底层容器的类型和优先级比较的仿函数。C++11 中一共有5大种构造函数,下面列出其中一种:

template <class InputIterator>
priority_queue (InputIterator first, InputIterator last,
                const Compare& comp, const Container& ctnr);

下面是具体的构造示例:

int myints[]= {10,60,50,20};

std::priority_queue<int> first;
std::priority_queue<int> second (myints,myints+4);
std::priority_queue<int, std::vector<int>, std::greater<int>> third (myints,myints+4);

小结

本次就是关于C++中的序列式容器做了一个总结,当然 C++ 中的容器不止这些,还有其余内容,这次就写到这里啦,下次继续。

声明:本文内容及配图由入驻作者撰写或者入驻合作网站授权转载。文章观点仅代表作者本人,不代表电子发烧友网立场。文章及其配图仅供工程师学习之用,如有内容侵权或者其他违规问题,请联系本站处理。 举报投诉
  • 函数
    +关注

    关注

    3

    文章

    4329

    浏览量

    62576
  • C++
    C++
    +关注

    关注

    22

    文章

    2108

    浏览量

    73624
  • STL
    STL
    +关注

    关注

    0

    文章

    86

    浏览量

    18319
收藏 人收藏

    评论

    相关推荐

    c++之STL算法(三)

    c++之STL算法(三)
    的头像 发表于 07-18 15:00 1279次阅读
    c++之<b class='flag-5'>STL</b>算法(三)

    STL130N6F7 MOS管现货

    STL130N6F7 MOS管产品介绍STL130N6F7询价热线STL130N6F7现货STL130N6F7代理 王先生 深圳市首质诚科技有限公司.
    发表于 11-12 10:21

    X-CUBE-STL与ARM的STL的区别是什么?

    大家好,我正在做一些关于 STL 的研究。STM 的 X-CUBE-STL 产品与 ARM STL 库有何不同?你为什么要用一个而不是另一个?
    发表于 12-02 07:18

    effective stl中文版下载pdf

    导读你已经熟悉了STL。你知道怎么建立容器,迭代它们的内容,添加删除元素和应用常见算法,比如find和sort。但你并不满足,你不能摆脱STL所提供的超过它们能带来的好处
    发表于 08-25 17:47 0次下载

    C++ STL的概念及举例

      本篇文章是作者本人使用STL 后的一些看法, 对於想要靠此文章学习STL, 是不可能的. 建议叁后面介绍的一些书入门.   STL的概念   在STL 中, 大至上分三个主要的
    发表于 08-30 11:39 1410次阅读

    STEP7 STL语句表编程使用手册

    本手册是用STL语句表编程语言编制用户程序的用户指南。 本手册也包括描述STL语言元素的语法和功能的参考章节
    发表于 03-10 16:05 197次下载
    STEP7 <b class='flag-5'>STL</b>语句表编程使用手册

    STL算法在GIS中的应用

    使用STL 算法实现GIS 算法可以保证它的简洁和高效该文结合C++代码实例抽象出了地理算子的概念应用在GIS 算法当中通过定制适配器来消除地理算子和STL 算法之间的不匹配同时拓展了ST
    发表于 06-28 16:55 33次下载

    数据结构与STL

    学习数据结构与STL的一些资料,新手可以慢慢看。
    发表于 12-22 14:41 0次下载

    基于STL曲面网格重建算法

    STL(stereo lithography)作为3D扫描数据和快速原型制造事实上的标准,广泛应用于娱乐、制造业和Internet等领域.随着3D模型越来越复杂,数据量越来越庞大,从STL文件难以
    发表于 12-25 11:52 1次下载
    基于<b class='flag-5'>STL</b>曲面网格重建算法

    S7-STL中文编程手册

    S7-STL中文编程手册免费下载。
    发表于 04-23 11:48 28次下载

    stl-thumb STL缩略图生成器

    ./oschina_soft/stl-thumb.zip
    发表于 05-30 09:46 57次下载
    <b class='flag-5'>stl</b>-thumb <b class='flag-5'>STL</b>缩略图生成器

    C++之STL库中的容器

    前面跟大家介绍过STL库,STL主要是由6大部分组成,其中第一个提到的就是容器,容器在介绍STL中小哥有简单的跟大家介绍过,今天稍微再详细介绍一下
    的头像 发表于 02-21 10:55 1204次阅读
    C++之<b class='flag-5'>STL</b>库中的容器

    博途使用STL中的MOVE指令

    现在,在 S7-1500 CPU 上可使用 STL 中的 MOVE 指令进行编程。
    的头像 发表于 06-06 11:10 6577次阅读
    博途使用<b class='flag-5'>STL</b>中的MOVE指令

    使用STL函数控制传送带

    要创建 STL 函数块“STL-Conveyor”,请按以下步骤操作
    的头像 发表于 10-12 16:00 613次阅读
    使用<b class='flag-5'>STL</b>函数控制传送带

    STL内容介绍

    1 什么是STLSTL(Standard Template Library),即标准模板库,是一个具有工业强度的,高效的C++程序库。它被容纳于C++标准程序库(C++ Standard
    的头像 发表于 11-13 11:32 840次阅读
    <b class='flag-5'>STL</b>内容介绍