程序员肖邦的博客 享受编程和技术所带来的快乐

C++的STL基础知识

2015-06-12
肖邦
C++
 

C++ 的 STL 基础知识总结。

一、STL容器概述

STL(Standard Template Library) 标准模版库是通用模版和算法的集合。使用模版的目的就是:能够让程序员编写与类型无关的代码。

1、数组与链表的优缺点

  • 数组
    • 优点:访问元素的速度非常快
    • 缺点:在数组中放置数据之前必须预知数组的长度;插入删除元素不方便;
  • 链表
    • 优点:设置长度方面极为灵活;插入删除元素简单;
    • 缺点:必须关注内存的分配和释放;不能随机访问;

2、结合了数组和链表的优点

C++ 标准模版库 STL 所提供的容器类,结合了数组和链表的优点,使用户从诸如内存管理之类的细枝末节中彻底解脱。

3、十大主要容器

  • 向量 - vector:支持对元素的下标访问,在尾部添加和删除元素,效率很高。
  • 列表 - list:在任何位置插入和删除元素,都很方便,不支持对元素的下标访问。
  • 双端队列 - deque:支持对元素的下标访问,支持在两端添加和删除元素。
  • 堆栈 - stack:只支持在一端存储和提取元素。
  • 队列 - queue:支持从前端提取而从后端压入元素。
  • 优先队列 - priority_queue:类似于队列,但所提取的是具有最高优先级的元素。
  • 映射 - map:以 key 的升序存储 key-value 对的序列,每个 key 只能出现一次;根据 key 提取 value 的效率最高;排序根据 key 类型的 < 操作符对其进行比较。
  • 集合 - set:映射的低级形式,不需要为每个 key 指定一个 value。
  • 多重映射 - multimap:映射的通用形式,一个 key 可以拥有超过一个的 key-value 对。
  • 多重集合 - multiset:多重映射的低级形式,不需要为每个 key 指定一个 value。

4、容器的分类

  • 线形容器:向量、列表和双端队列。元素按照线性顺序排列,这类容器必须支持某种形式的 next 操作,以便从一个元素转移到下一个元素。
  • 适配器容器:堆栈、队列和优先队列。适配器容器是对线性容器的一些通用接口加以限制的产物。
  • 关联容器:映射、集合、多重映射和多重集合。根据一个与元素相关联的 key 存储或提取该元素,它们的存储顺序取决于对 key 进行排序后的顺序,并且通常以一棵二叉树的形式存储。

5、容器的共同特征

  • 所有的容器类都支持赋值操作符,这样一个容器类型的变量可以作为一个整体被赋值给另一个相同类型的容器变量。

  • 两个容器变量相等 == 的条件:两个容器变量的容器类型相同,两个容器变量所包含的元素数相同,两个容器变量之间对应位置的元素满足该元素类型的相等 == 性测试。

  • 一个容器变量小于 < 另一个容器变量的条件:两个容器变量的容器类型相同;一个容器变量所包含的每个元素都小于 < 另一个容器变量中对应位置处的元素。

  • 对于容器,其它的比较操作符(><=>=!=)都有类似于==<的重载定义。

  • 当一个类类型的对象被插入到一个容器中时,这个容器实际存储的是这个对象的一份拷贝而非这个对象本身。为此,该容器将使用元素数据类型所定义的拷贝构造函数或者拷贝赋值操作符,对这个被插入的对象进行复制。

二、向量 vector

1、基本特点

  • 连续内存与下标访问。通过下标在一个向量中对其元素进行随机访问的效率可以和数组相媲美。这是因为和数组一样,向量中的元素被存储于一个连续的内存块中。
  • 动态内存分配。向量把它所有的元素存储在一个连续的内存块中,这并不会妨碍新元素被无限制地插入到容器中。如果当前的内存区域无法满足一个向量中所有元素连续存储的需要,那么这个向量就会自动转移到一个新的内存位置。原先位置上的所有元素都将被复制到这个新分配的内存块中,而原先的内存空间则被释放。
  • 通过预分配空间减小额外开销。向量在它增长时能够在内存中转移,这势必会导致诸如内存分配、内存释放、元素复制等额外的开销。但是,如果我们在创建向量时能够合理地为它预分配一些空间,那么将在很大程度上缓解这种和向量相关的计算性开销。
  • 随机访问与插入删除。向量具有数组的随机访问特性,能够在它的尾部进行高效地插入或删除操作,并且具备链表的灵活性,允许我们在它的任何位置进行偶尔地插入或删除(虽然这种操作的效率不高)。

2、定义变量

vector <int> vn;
vector <string> vs;

3、迭代器 iterator

在 STL 中,迭代器和容器之间的关系相当于指针和一个普通数组的关系。而迭代器和指针之间的一个重要区别是不存在值为 NULL 的迭代器。也就是说,我们不能用 NULL 或 0 对迭代器进行初始化。

vector <int>::iterator it;

// 整型向量迭代器 it 指向该向量的第一个元素
vector <int> vn;
vector <int>::iterator it = vn.begin();

// 迭代器指向该向量最后一个元素后面的位置。
it = vn.end()

// 通过 begin() 和 end() 可以在一个循环中遍历向量中的所有元素
for (vector<int>::iterator it = vn.begin(); it != vn.end(); it++)
    cout << *it << endl;

向量迭代器具有一下子两个额外特性:

  • 通过*操作符,它们可以使用和数组指针完全相同的语法进行解引用。
  • 它们可以和数组指针一样通过++--操作符进行自增和自减操作。

4、尾部添加和删除元素

vn.push_back('a');    // 向量的尾部添加一个元素
vn.pop_back('b');     // 向量的尾部删除一个元素

5、随机访问

  • 通过对迭代器进行解引用来设置一个向量元素的值
    vector <int> vn;
    vn.push_back(34);
    vn.push_back(23);
    vector <int>::iterator it = vn.begin();
    *(it + 1) = 52;
    
  • 通过下标对向量元素进行类似数组的随机访问
    for (int i = 0; i < vn.size(); i++)
          cout << vn[i] << endl;
    
  • 可以通过下标操作符修改向量元素的值。
    vn[1] = 63;
    

6、向量元素的预分配与初始化

我们也可以声明一个预先确定长度的向量。

vector <int> vn(100);

// 向量构造函数的第二个参数用于指定元素的初始值
vector <int> vn(100, 2);

在这类声明中,对于基本类型向量,其每个元素都被初始化为适当类型的零。而对于类类型向量,其每个元素将根据在元素类中定义的无参构造函数进行初始化。

7、常见函数

  • front() 返回向量中第一个元素
  • back() 返回向量中最后一个元素
  • size() 返回向量的大小,即元素的个数
  • resize() 可以改变向量的大小,并把一些被初始化为适当类型的零(基本类型向量),或按无参构造函数进行初始化(类类型向量)的元素添加到向量中。
  • clear() 可以清空向量中的所有元素,使向量的大小变成0,但它的容量却仍保持不变。我们也可以通过对这个向量调用 resize(0) 来实现相同的效果。
  • capacity() 返回向量的容量,即最多容纳多少个元素。
  • reserve() 可以为向量保留一些未被初始化的内存,从而扩充该向量的容量。但它并不改变该向量的大小。

向量的大小和容量具有如下特性:

  • 向量的大小可以增加也可以减少,引起向量大小变化的成员函数除resize()外还有push_back()pop_back(),以及后面即将提及的插入和删除函数;
  • 向量的容量只能增加不能减少,只能通过reserve()成员函数改变向量的容量;
  • 向量大小的增加可能会导致其容量的增加,但向量容量的变化并不会影响其大小;
  • 通过resize()成员函数增加向量的大小,新增部分被初始化为适当类型的零;
  • 通过reserve()成员函数增加向量的容量,新增部分不被初始化;
  • 位于向量的容量范围内但不在其大小范围内的元素,也可以通过下标或迭代器进行访问,但其值是未定义的;
  • resize()reserve()成员函数所引起的,向量大小和容量的变化都发生在该向量的尾部。

8、向量的链表操作

  • 只有在向量尾部所进行的链表操作才是高效的,甚至可以达到常数时间级效率(O(1))。其他位置所需要的操作时间很可能和元素数量成正比(O(N))
  • insert()erase()成员函数
    • 这两个成员函数都有一个迭代器参数,它们分别指向新元素将要插入的位置和将被删除的旧元素的位置。
    • insert()成员函数将导致向量的大小增加1erase()成员函数将导致向量的大小减少1
  • find()成员函数,根据给定的参数找到向量中特定元素第一次出现的位置,并返回标识该位置的迭代器。
  • 若链表操作使向量的结构发生变化,则先前对迭代器所做的任何初始化都将失效,必须重新初始化。

9、类对象的向量

  • 如果一个类类型的对象需要被存储在向量中,那么这个类至少应该支持无参构造函数,以确保为这个向量所分配的内存能够被正确地初始化。
  • 该类可能还需要提供拷贝构造函数和拷贝赋值运算符的重载定义。
  • 如有必要该类还需要提供对==<两个操作符的重载定义,这样被存储在向量中的对象就可以相互比较,以供各种STL算法使用。STL能够根据这两个操作符推断出其它比较操作符的含义。
  • 在向量中保存的永远只是对象的拷贝,而非对象本身。
  • 改变长度——无参构造,改变容量——只分配内存不做初始化。
  • 通过sort()函数排序
    • 两参数版本的sort()函数通过针对元素类的被重载的<操作符对向量进行排序。
    • 三参数版本的sort()函数允许通过其第三个参数指定一个函数对象,该函数对象提供了对()操作符的重载定义,进而确定了向量中元素间的比较方法,最终实现了对该向量的排序。
  • 析构与拷贝赋值:删除向量中的一个元素,该元素类型的析构函数将会被调用,以执行实际的删除工作。同时,这个元素后面的所有元素都需要在内存中依次向前移动一位,以保证该向量中的所有元素仍然被存储于连续的内存块中。如果元素类型中定义了拷贝赋值操作符,那么系统就会调用该操作符以完成这个任务。

11、通过数组初始化向量

使用向量的两参数版本构造函数。这两个参数都是指针,第一个指向初始化数组的起始位置,第二个则指向该数组尾部的下一个位置。

三、双端队列 deque

  • 双端队列具有向量的所有功能。
  • 在双端队列的头部与在其尾部进行进行插入和删除的效率一样高。
  • 和向量相比,双端队列的内存开销要大一些,对元素下标访问的效率也要略低一些。
  • 双端队列所提供的push_front()pop_front()成员函数可以与push_back()pop_back()函数相类似的方式在容器的头部插入和删除元素,其效率也是相当的。 双端队列deque

四、列表 list

  • 列表是按照链表的形式进行存储的。
  • 在列表的任何位置插入和删除元素的效率都很高。
  • 无法以下标方式对列表中的元素做随机访问。
  • 列表常用成员函数:
    • push_front():在头部插入一个新元素。
    • pop_front():删除第一个元素。
    • push_back():在尾部插入一个新元素。
    • pop_back():删除最后一个元素。
    • begin():获取第一个元素的迭代器。
    • end():获取最后一个元素下一个位置的迭代器。
    • size():计算列表中元素的数量。
    • remove():删除所有匹配元素。
    • sort():对容器中的元素进行排序。该函数是列表自己的成员函数,利用元素类型对<操作符的重载定义,对其进行比较。此外,也可以通过该函数的第二个参数,提供小于比较标准。
    • unique():列表中连续重复出现的元素只保留第一个。利用元素类型对“==”操作符的重载定义,对各元素进行比较。此外,也可以通过该函数的第二个参数,提供等于比较标准。
    • splice():把列表中的一部分元素划到另一个列表中。将参数列表(第二个参数)指定位置(第三个参数)的元素剪切到调用列表的指定位置(第一个参数)。剪切完成以后,参数列表将丢失被剪切的元素。
    • merge():合并两个列表。假定它的调用列表和参数列表都是经过排序的。该函数把参数列表中的元素合并到调用列表中,并且使调用列表仍然保持有序状态。合并完成以后,参数列表将被清空。 列表list

五、堆栈 stack

  • 堆栈可以作为任何支持push_back()pop_back()back()以及empty()size()等操作的容器的包装类。这意味着,如果我们自行编写了一个容器并且提供了上面这些函数,那么堆栈就可以对它进行适配。
  • 指定底层容器的语法:
    stack<string, vector<string> > ss;
    

    表示所创建堆栈对象的底层容器是一个字符串向量。注意vector<string>和后面的>之间的空格必须有,否则编译器会把>>理解为一个右移操作符,从而造成编译错误。

  • 如果没有指定底层容器,如:
    stack<string> ss;
    

    那么该堆栈在缺省情况下将使用一个双端队列作为其底层容器。

  • 堆栈的push()pop()top()成员函数分别依赖于底层容器的push_back()pop_back()back()成员函数。

六、队列 queue

  • 队列可以作为任何支持push_back()pop_front()back()front()以及empty()size()等操作的容器的包装类,或者说对支持这些函数的底层容器进行适配。
  • 指定底层容器的语法:
    queue<string, list<string> > qs;
    

    表示所创建队列的底层容器是一个字符串列表。

  • 如果没有指定底层容器,
    queue<string> qs;
    

    那么该队列在缺省情况下将使用一个双端队列作为其底层容器。

  • 队列的push()pop()成员函数分别依赖于底层容器的push_back()pop_front()成员函数。其它函数则直接调用底层容器的同名函数。

七、优先队列 priority_queue

  • 每当向(从)优先队列压入(弹出)一个元素后,队列中具有最高优先级的元素就被自动排列到队列的最前面。
  • 优先队列中元素的优先级通常取决于程序员通过函数对象所提供的比较标准。
  • 如果程序员并没有显式地为优先队列中的元素提供比较标准,但元素类却提供了对“<”操作符的重载定义,那么系统就会通过该操作符确定元素的优先级。
  • 再不然,系统会使用声明于C++标准库头文件functional中的less函数对象,完成对队列中元素优先级的判定。

八、映射 map

  • 映射是一个key-value对的序列,其中每个key都是唯一的。
  • 一个映射中所有的key-value对,以key的升序排列,按二叉树的形式存储,因此我们可以在这种容器中进行快速的提取操作。当一个新的元素被插入到映射中时,这种顺序依然能够得到保持。
  • 生成和维护一个以key排序的序列,要求这个映射能够使用针对key类型的<操作符,作为元素间的比较标准。
  • 程序员也可以自己指定函数对象,作为元素间的比较标准。例如,对于具有 C 风格字符串类型 key 的 map 容器,其比较函数对象如下:
    class c_string_less
    {
    public:
        bool operator () (const char *lpsz1, const char *lpsz2) const
        {
            return strcmp (lpsz1, lpsz2) < 0;
        }
    };
    // 该映射对象以如下方式创建:
    map<char*, int, c_string_less> mcs;
    

    通过提供一个适当的比较函数,可以把一个映射中并不完全相等的 key 判断为相等。例如map<string, int>采用string作为key的类型。而string类中的<操作符是大小写敏感的。如果我们所需要的key排序恰恰是基于某种大小写不敏感的比较标准,那么我们就可以为该映射的构造函数提供一个大小写不敏感的比较函数对象,以替代string类中的<操作符,参与对映射中元素的排序。

九、集合 set

集合中的每个元素只能出现一次,即集合中不允许出现重复的元素

十、泛型算法

  • 除了容器之外,STL还向我们提供了一些算法。它们可以在容器类中使用,以完成查找、排序、计数、合并、填充、比较、变换、删除以及划分等任务。
  • STL算法通常只需要以迭代器作为参数,并不需要知道所操作容器的细节,因此,STL算法又被称为泛型算法。
  • 对于泛型算法,一个算法能否被应用于一个给定的容器,完全取决于该容器是否支持这个算法所需要的迭代器类型。
  • STL中,共有60种不同的算法,其中23种是非修改算法(如find()函数),其余37种是修改算法(如sort()函数)。
  • 关于STL所提供的排序算法,特别是针对类类型对象的排序,我们基本上可以采用两种方法:
    • 为容器中的元素类提供<操作符的重载定义。缺省情况下,泛型算法sort()使用这个操作符的重载定义对元素进行排序。
    • 定义一个比较函数对象,并把它作为参数提供给排序算法。通过对()操作符的重载定义,该函数对象可以告诉sort()算法如何对两个类类型的对象进行比较。

十一、更多迭代器

我们可以按照下面的方式把一个标识符声明为一个迭代器:

容器模板名<类型实参1, 类型实参2, ...>::迭代器类型名 迭代器变量名;

其中,迭代器类型名可选用下列名字之一:

iterator
reverse_iterator
const_iterator
const_reverse_iterator

例如:

vector<Shape*>::iterator it;
list<string>::const_iterator cit;
list<int>::reverse_iterator rit;
map<string, int>::const_reverse_iterator crit;

那些带有reverse字样的迭代器的++--操作符,与那些不带reverse字样的相应迭代器相比,具有相反的意思。而那些带有const字样的迭代器则不允许我们通过它们对其所指向的元素进行修改。


上一篇 C++的异常

Comments

Content