数据结构与算法分析（二）--- STL简介 + 线性表容器（C++11）

文章目录

一、什么是STL

每种数据结构都要提供相应的一组操作方法（也即 增、删、改、查、排序 等算法）。对于相对底层的面向过程的C语言来说，要想使用一些复杂的数据结构，标准库并没有提供相应的接口，需要自己实现相应的一组操作方法，当然也可以使用第三方库比如libcstl。

对于面向对象的语言比如C++，在标准库中就提供了常用的数据结构及其算法，这就是C++有名的STL（Standard Template Library），也是C++标准库的核心，其它的编程语言一般也都提供有类似的STL标准模板库。

C++标准库的应用范围比C语言第三方库比如libcstl的应用范围广得多，所以本系列文章介绍数据结构实现及其操作算法的STL库时，以C++11的STL为准。介绍STL库的目的也是在我们了解数据结构及其操作的基础上，不用重复造轮子，直接使用标准库既可以提高工作效率（标准库比我们自己实现的算法更健壮高效），又可以方便参与到与别人共同开发的协作网络中（跟别人使用同一套库，程序兼容性与可移植性比较好）。

先简单介绍下C++的STL，STL是由一些可适应不同需求的集合类（即数据结构类）和一些能够在这些数据集合上运作的算法构成，STL内的所有组件都由模板构成，所以其元素可以是任意类型。STL组件主要包括以下部分：

  • 容器（container）：用来管理某类对象的集合，容器可以是array、linked list、tree、hash map、set等；
  • 迭代器（iterator）：用来在一个对象集合内遍历元素，这个对象集合或许是个容器，或许是容器的一部分。迭代器和寻常的指针类似，调用operator ++ 就累进，调用operator * 就访问被指向的元素值，你可以把迭代器视作一种智能指针，能够把”前进至下一元素“的意图转换为合适的操作；
  • 算法（algorithm）：用来处理集合内的元素，它们可以出于不同的目的而插入、删除、修改、查找、排序、使用元素，通过迭代器的协助，我们只需撰写一次算法，就可以将它应用于任意容器，因为所有容器的迭代器都提供一致的接口。

STL的基本观念是将数据与操作分离，数据由容器类管理，操作则由可定制的算法负责，迭代器在两者之间充当粘合剂，使任何算法都可以和任何容器交互运作。STL组件之间的关系如下图所示：
STL各组件之间的关系
先给出C++ STL 支持的容器及成员函数一览表如下：
C++ 容器库成员函数表

二、顺序表的STL容器

2.1 STL容器：Array（C++11）

先看看C++11 STL容器最基本的类型array，它包覆了一个寻常的static C-style array并提供一个STL容器接口（同样支持前面介绍的C-style Array的操作）。Array有固定大小，因此你无法借由增加或移除元素而改变其大小，只允许你修改或查询元素值。

C++11 STL Array的类模板定义如下（第一个参数T为元素类型，第二个参数N为元素个数）：

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

  • 1
  • 2
  • 3
  • 4
  • 5

既然是面向对象的class array<>，先看看该类的构造函数：
数组构造函数
class array<>的比较、访问等非更易型操作：
array的查询比较操作
class array<>的赋值、交换等更易型操作：
array赋值修改操作
class array<>的迭代器支持的相关操作：
array迭代器相关操作
下面给出一个操作array的示例程序供参考：

// datastruct\array_demo.cpp

#include 
#include 
#include 

template <typename T>
void printElements(const T& coll)
{
    for(auto iter = coll.begin(); iter != coll.end(); ++iter)
    {
        const auto& elem = *iter;
        std::cout << elem << '\t';
    }
    std::cout << std::endl;
}

int main(void)
{
    // create array with 10 ints
    std::array<int, 10> a = {31, 22, 19, 47};
    printElements(a);
    
    // modify last two elements
    a.back() = 99;  
    a[a.size() - 2] = 42;
    printElements(a);
    
    // sort the array elements
    std::sort(a.begin(), a.end());
    printElements(a);

    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34

上面array的示例代码运行结果如下（需要注意编译器是否支持C++11，比如g++在4.7以上版本才支持，添加-std=c++11即可）：
array_demo运行结果

2.2 STL容器：Vector（C++11）

Class Array<>在初始化时就固定了大小（也即存储元素的数量），后面几乎不可调整大小，缺乏弹性，因此不支持插入或删除元素的操作，只支持修改、查询或排序元素的操作。这对于一般的场景倒也够用，但有很多场景需要数据结构能支持动态调整大小的功能（毕竟需求随着时间会变化），于是动态变长数组（Dynamic array）应运而生。

动态变长数组如何实现呢？虽然支持动态调整大小，其物理存储结构依然是顺序结构的数组（如果是链式结构实现就不叫数组了），要实现数组可变长度，最简单的方法就是在初始化数组时，多申请一部分空间，为以后的变长预留位置。C++11 STL容器中的变长数组也是这么实现的，由于变长数组可以向一个方向增长，所以取名Vector，也算比较形象贴切。变长数组Vector与静态数组Array的示意图对比如下：
vector与array对比
变长数组Vector通过多申请空间，为变长预留位置的方案虽然可以在一定程度上满足我们的需求，但当预留空间用完之后，就蜕化为静态数组Array了，如果要继续插入元素，就会再找一块儿更大的连续地址空间（为原地址空间的两倍大小），将原地址空间的数据搬移到新的地址空间，继续支持变长特性，这个操作称为变长数组的扩容。由于扩容后，原数据元素搬移导致地址变更，对这些元素的地址引用操作比如引用、指针、迭代器等都将失去作用，且扩容操作比较耗时。要想缓解扩容导致的问题，可以在创建变长数组时，根据我们的需求预留足够的空间，但预留太多空间会导致空间浪费，这个取舍需要平衡。

C++11 STL Vector的类模板定义如下（第一个参数T为元素类型，第二个参数Allocator定义内存模型，可省略直接使用默认值）：

// 

namespace std{
	template <typename T,
			  typename Allocator = allocator<T>>
	class vector;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

class vector<>的构造函数与析构函数如下：
vector构造与析构函数
class vector<>的比较、访问等非更易型操作：
vector比较访问操作
跟前面array容器相比，这里多了元素容量调整的接口函数，也是对前面介绍的变长数组实现方案中预留空间的操作，可以查询当前vector容量，也可以扩大或者缩小预留空间。需要注意的是，对容量的调整（比如reserve或shrink_to_fit）会导致所有指向元素的引用、指针、迭代器等失效。

class vector<>的赋值、交换等更易型操作：
vector赋值交换操作
class vector<>的迭代器支持的操作跟前面介绍的array类似，这里就不再赘述了。

class vector<>因为增加了变长特性，就可以支持插入与删除操作了，由于vector顺序存储结构的限制，在尾部插入或删除元素的效率比较高（常数时间复杂度），在中间插入删除的效率较低（线性时间复杂度）。Vector支持的插入或删除操作如下：
vector插入与删除操作
因为容器内某元素的引用、指针、迭代器等都指向该元素的地址，任何改变该元素地址的行为都会导致指向该元素的引用、指针、迭代器失效。前面介绍了vector容量的变更会导致其失效，这里在vector容器中间插入或移除元素，会导致该插入或移除点后面的所有元素地址发生改变，也即会使该插入或移除点之后的所有元素的引用、指针、迭代器失效（在vector容器末尾插入或移除元素不受影响）。

布尔类型比较特殊，C语言的默认基本类型并不支持bool类型，如果想使用bool类型需要包含头文件< stdbool.h >。C++标准库针对bool类型的vector<>专门设计了一个特殊版本，目的是获取一个优化的vector，使其耗用空间远小于vector的一般实现版本。一般版本会为每个bool元素分配至少 1 byte空间，而vector< bool >特化版本的内部只使用 1 bit 存放一个元素，空间节省8倍。不过有一点需要注意，C++的最小定址值仍是以byte为单位的，所以必须对其迭代器进行特殊处理，即便如此vector< bool >特化版本也无法满足其它vector的所有规定，其所有元素操作都必须转化为bit操作。

下面给出一个操作vector的示例程序供参考：

// datastruct\vector_demo.cpp

#include 
#include 
#include 
#include 

template <typename T>
void printElements(const T& coll)
{
    for(auto iter = coll.begin(); iter != coll.end(); ++iter)
    {
        const auto& elem = *iter;
        std::cout << elem << " ";
    }
    std::cout << std::endl;
}

int main(void)
{
    // create empty vector for strings
    std::vector<std::string> sentence;
    
    // reserve memory for five elements to avoid reallocation
    sentence.reserve(5);
    
    // append some elements
    sentence.push_back("Hello,");
    sentence.insert(sentence.end(), {"how", "are", "you", "?"});
    
    // print elements and some attribute value
    printElements(sentence);
    std::cout << "max_size: " << sentence.max_size() << std::endl;
    std::cout << "size:     " << sentence.size() << std::endl;
    std::cout << "capacity: " << sentence.capacity() << std::endl;
    std::cout << "address:  " << &sentence.at(0) << std::endl;
    
    //swap elements
    std::swap(sentence[1], sentence[3]);
    
    // insert elements before elements "?"
    sentence.insert(std::find(sentence.begin(), sentence.end(), "?"), "always");
    
    // assign "!" to the last elements
    sentence.back() = "!";
    
    // print elements and some attribute value
    printElements(sentence);
    std::cout << "size:     " << sentence.size() << std::endl;
    std::cout << "capacity: " << sentence.capacity() << std::endl;
    std::cout << "address: " << &sentence.at(0) << std::endl;
    
    // delete last two elements
    sentence.pop_back();
    sentence.pop_back();
    
    // shrink capacity
    sentence.shrink_to_fit();
    
    // print elements and some attribute value
    printElements(sentence);
    std::cout << "size:     " << sentence.size() << std::endl;
    std::cout << "capacity: " << sentence.capacity() << std::endl;
    std::cout << "address:  " << &sentence.at(0) << std::endl;

    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67

上面vector的示例代码运行结果如下（需要注意编译器是否支持C++11，比如g++在4.7以上版本才支持，添加-std=c++11即可）：
vector_demo运行结果
从上面的运行结果也可以看出，当vector的容量不足时，再插入元素，会将原容量扩充一倍。当vector容量变化时，容器内元素的地址也会发生变化，所以指向容器内元素的引用、指针、迭代器都会失效。

2.3 STL容器：Deque（C++11）

了解了变长数组容器Vector，我们会好奇，既然STL提供了单向变长，只能在尾部方便插入、移除元素的方法，有没有提供双向变长，在首尾两端都支持插入、移除元素方法的容器呢？如果有，会如何实现呢？

Vector容器当容量不足，扩展容量时需要将原先所有的元素复制到新的内存地址空间，这点在容器内元素数量很多时，就很影响效率。假如找不到更大的连续内存地址空间，Vector容器扩容将会失败。这些缺点能否避免，同时又保留顺序表高效随机访问的优点呢？

C++11 STL还真提供了一个可以双向变长，在首尾两端都能高效插入、移除元素的容器：Deque（Double-ended queue），类似于Vector容器，也是采用dynamic array来管理元素，并提供随机访问操作的，有着和Vector几乎一模一样的接口，和Vector不同的是，Deque能在首尾两端进行快速插入或删除元素。Deque元素间的逻辑结构如下：
Deque逻辑结构
Vector容器是通过预留更多的空间实现单向变长功能的，Deque容器会采用何种方法实现双向变长功能呢？很容易想到，如果把两个Vector起点拼接到一起，两个Vector分别能向其中一端变长扩展，组合起来不就可以实现双向变长扩展了吗？

Deque容器也就是这么设计的，但如果只是将两个Vector简单拼接，当两个Vector扩容时，对内存连续地址空间的需求更高，复制元素的成本也更高，所以能否避免扩容时元素的复制呢？

要想避免扩容时元素的复制，就需要再增加新的地址空间后，能把原地址空间与新地址空间（可称为“区块”）连接起来，每当一端扩容时，再找一个新的独立区块连接到原区块后面就可以了，所以Deque容器是由一组独立区块（individual blocks，一般一个区块大小为512字节）构成的，第一个区块朝某方向扩展，最后一个区块朝另一个方向扩展。Deque的内部结构如下图示：
Deque容器内部结构
Deque容器内部的独立区块并不都是连续的（扩容时可能原区块后面空间不够，需要在其它地方另找一个区块），这些不连续的区块如何管理呢？如果区块间的管理不到位，就没法实现顺序表的随机访问功能。

为了管理分段空间deque容器引入了Map数组（可看作多个独立区块的中央控制器），Map是一块连续地址空间，其中每个元素是指向各个独立区块的指针，这些独立区块是deque存储数据的主体，deque容器每创建一个独立区块，都将该区块的首地址存入Map数组的相应数据项中。Map数组管理deque容器一组独立区块的结构关系图示如下：
deque内部实现原理图
由上图可以看出，deque容器要想实现对分段连续地址空间的随机访问，迭代器的设计就比Vector复杂得多。在Map和deque块的结构之下，deque使用了两个迭代器M_start和M_finish，对首个deque块和末deque块进行控制访问。迭代器iterator共有4个变量域，包括M_first、M_last、M_cur和M_node。M_node存放当前deque块的Map数据项地址，M_first和M_last分别存放该deque块的首尾元素的地址（M_last实际存放的是deque块的末尾字节的地址），M_cur则存放当前访问的deque双端队列的元素地址。

由于deque容器的迭代器比vector容器的迭代器复杂很多，所以通过deque容器的元素访问和迭代器操作会比vector慢一些。所以C++ Standard建议：如非必要（比如需要经常在首尾两端插入或移除元素，或及时释放不再使用的元素等），优先选择使用Vector容器。

C++11 STL Deque的类模板定义如下（第一个参数T为元素类型，第二个参数Allocator定义内存模型，可省略直接使用默认值）：

// 

namespace std{
	template <typename T,
			  typename Allocator = allocator<T>>
	class deque;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

class deque<>的构造函数与析构函数如下：
deque构造与析构函数
class deque<>的比较、访问、迭代器等非更易型操作：
deque非更易型操作
Deque容器由于通过Map管理多个独立区块，在扩容时新增区块，当某区块地址空间不再使用时也会释放该区块。跟Vector容器类似，当扩展或缩减容量时，涉及到的独立区块内的元素地址会发生变化，指向这些元素的指针、引用、迭代器将会失效；除了首尾两端，在中间插入或删除元素时，该作用点后面的所有元素地址也会发生变化，指向这些元素的指针、引用、迭代器也会失效。

class deque<>的赋值、交换、插入、移除等更易型操作：
deque更易型操作
下面给出一个操作deque的示例程序供参考：

// datastruct\deque_demo.cpp

#include 
#include 
#include 
#include 

template <typename T>
void printElements(const T& coll)
{
    for(auto iter = coll.begin(); iter != coll.end(); ++iter)
    {
        const auto& elem = *iter;
        std::cout << elem << "\n";
    }
    std::cout << std::endl;
}

int main(void)
{
    // create empty deque of strings
    std::deque<std::string> coll;

    // insert several elements
    coll.assign(3, std::string("string"));
    coll.push_back("last string");
    coll.push_front("first string");
    printElements(coll);

    // remove first and last element
    coll.pop_front();
    coll.pop_back();

    // insert "another" into every element but the first
    for(int i = 1; i < coll.size(); ++i)
        coll[i] = "another " + coll.at(i);
    printElements(coll);

    //change size to four elements    
    coll.resize(4, "resized string"); 
    
    // sort the elements
    std::sort(coll.begin(), coll.end());
    printElements(coll);

    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47

上面deque的示例代码运行结果如下（需要注意编译器是否支持C++11，比如g++在4.7以上版本才支持，添加-std=c++11即可）：
deque示例程序执行结果

三、链式表的STL容器

3.1 STL容器：List（C++11）

C++11 STL为链表提供的默认容器是class list<>，list容器使用doubly linked list双向链表管理其中的元素。由此可见，双向链表的应用场景比单向链表更多。先看下list容器中元素的逻辑组织关系：
list元素逻辑结构
C++11 STL List的类模板定义如下（第一个参数T为元素类型，第二个参数Allocator定义内存模型，可省略直接使用默认值）：

// 

namespace std{
	template <typename T,
			  typename Allocator = allocator<T>>
	class list;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

List容器的内部结构完全迥异于array、vector，List对象自身提供了两个指针，用来指向第一个和最后一个元素（便于快速找到链表首结点与尾结点，从链表首位插入、删除结点比较高效），每个元素都有两个指针分别指向其前一个元素与后一个元素。如果想要插入新元素、移除指定元素，只需要操作对应大的指针即可，如下图所示：
list插入新元素
list容器由于使用了指针存储元素间的指向关系，相比array和vector等顺序表容器，可以更高效的插入与删除元素。由于不要求元素间连续存储，自然也不需要类似vector的容量调整、空间重分配的操作。同样的，list容器放弃了元素间的邻接关系，自然就不支持下标访问与随机访问了，对链表元素的排序就很不方便（可以在链表插入新元素时，按顺序插入到指定位置，使其插入新元素前后都保持有序状态）。

class list<>的构造函数与析构函数如下：
list构造与析构函数
class list<>的比较、访问等非更易型操作（相比顺序表不支持下标访问了）：
list非更易型操作
class list<>的赋值、交换等更易型操作：
list更易型操作
class list<>的迭代器支持的操作跟前面介绍的array类似，这里就不再赘述了。

class list<>容器的插入与删除操作比顺序表要强大丰富些，不仅支持链表首尾的插入与移除，还支持条件移除（移除所有某条件为真的元素）：
list插入移除操作
class list<>容器得益于元素间指向关系调整比较高效的优势，其支持的更易型操作也比顺序表强大丰富得多，支持链表的拼接、合并、反序、移除重复元素等。由于链表不支持随机访问，不适用于算法库中的排序函数，为此list容器为自己量身定做了用于内部元素排序的成员函数，如果我们想要对链表元素排序，只能使用其成员函数list::sort：
list容器特殊的更易型操作
class list<>容器的splice链表拼接操作，实际上也是改变两个链表拼接位置附近元素的指针指向关系，如下图所示：
list拼接操作示意图
下面给出一个操作list的示例程序供参考：

// datastruct\list_demo.cpp

#include 
#include 
#include 

template <typename T>
void printElements(const T& coll)
{
    for(auto iter = coll.begin(); iter != coll.end(); ++iter)
    {
        if(iter != coll.begin())
            std::cout << " <--> ";
        const auto& elem = *iter;
        std::cout << elem;
    }
    std::cout << std::endl;
}

void printLists(const std::list<int>& list1, const std::list<int>& list2)
{
    std::cout << "list1: ";
    printElements(list1);
    std::cout << "list2: ";
    printElements(list2);
    std::cout << std::endl;
}

int main(void)
{
    // create two empty lists
    std::list<int> list1, list2;

    // fill both lists with elements
    for(int i = 0; i < 6; ++i)
    {
        list1.push_back(i);
        list2.push_front(i);
    }
    printLists(list1, list2);

    // insert all elements of list1 before the first element with value 3 of list2
    list2.splice(std::find(list2.begin(), list2.end(), 3), list1);
    printLists(list1, list2);

    // move first element of list2 to the end
    list2.splice(list2.end(), list2, list2.begin());
    printLists(list1, list2);

    // sort second list, assign to list1 and remove duplicates
    list2.sort();
    list1 = list2;
    list2.unique();
    printLists(list1, list2);

    // merge both sorted lists into the first list
    list1.merge(list2);
    printLists(list1, list2);

    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61

上面list的示例代码运行结果如下（需要注意编译器是否支持C++11，比如g++在4.7以上版本才支持，添加-std=c++11即可）：
list示例程序运行结果

3.2 STL容器：Forward List（C++11）

C++11 STL既然提供了双向链表容器list，有没有提供单向链表容器呢？之前觉得单向链表的使用不如双向链表那么方便，所以并没有为单向链表单独提高一个容器，从C++11开始才为单向链表专门提供了一个容器forward list，其内部是以singly linked list管理元素的。forward list容器内元素的逻辑结构如下图示（forward list前向链表，即往前面靠近首结点的地方插入移除元素比较高效，省去了不少遍历时间）：
forward list逻辑结构
C++11 STL Forward List的类模板定义如下（第一个参数T为元素类型，第二个参数Allocator定义内存模型，可省略直接使用默认值）：

// 

namespace std{
	template <typename T,
			  typename Allocator = allocator<T>>
	class forward_list;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

Forward List可以看作一个行为受限的List，只能单向前进，不能走回头路。凡是List不支持的功能，Forward List也不支持。那么，既然已经有了List，为了又提供了一个更鸡肋的Forward List呢？

C++ standard这样描述forward list：

我们希望forward list和你自己手写的C-style singly linked
list相较之下没有任何空间或时间上的额外开销，任何性质如果与这个目标相抵触，我们就放弃该性质。

由此可见，forward list相比list的优势就是内存占用更少，运行效率更高。凡事有收益就有代价，forward list相较list有着诸多约束，比如只能前向遍历，没有提供指向最后一个元素的指针，自然也不提供在链表末尾插入或删除元素的操作。

class forward_list<>的构造函数与析构函数如下：
forward_list构造与析构函数
class forward_list<>的比较、访问等非更易型操作（相比双向链表不支持末尾结点和元素数量访问了）：
forward_list非更易型操作
class forward_list<>的赋值、交换等更易型操作：
forward_list更易型操作
class forward_list<>只能前向遍历元素，不支持反向迭代器，因此其支持的迭代器操作同样受限。C++11 STL为forward_list提供了两个特殊迭代器before_begin()和before_cbegin()，可以获得第一个元素的前一位置，forward_list支持的迭代器如下：
forward_list迭代器操作
class forward_list<>容器的插入与删除操作跟list类似，但不支持末尾插入或删除元素的操作：
forward_list插入或删除操作
C++ STL为forward_list单独提供迭代器before_begin()可以获得第一个元素的前一个位置，实际上也就是前篇我们介绍单向链表中的链表头位置，获取这个位置更方便在链表最前端（第一个元素前）插入或删除元素。

在中间插入或删除元素时，需要获得查找到插入或删除目标元素的前一个位置，就可以使用两个迭代器，分别从begin()与before_begin()开始往后遍历查找，待begin()查找到目标元素位置后，其前驱结点的位置即为before_begin()。这两个过程的操作图示如下：
forward_list插入或删除结点图示
class forward_list<>容器跟list容器类似，也提供链表的拼接、合并、反序、移除重复元素等。同样的，forward_list也不适用于算法库中的排序函数，容器自身提供了用于内部元素排序的成员函数forward_list::sort，这些操作方法如下：
forward_list特殊的更易型操作
class forward_list<>容器的splice_after链表拼接操作与list容器提供的splice操作类似，但为何命名为splice_after呢？由于forward_list只能前向遍历的特点，传给splice_after的是“splice所作用元素位置”的前一个元素位置，所以splice_after拼接操作是作用到传入位置的后一个位置的。splice_after拼接操作图示如下：
forward_list拼接操作图示
下面给出一个操作forward_list的示例程序供参考：

// datastruct\forward_list_demo.cpp

#include 
#include 
#include 
#include 

template <typename T>
void printElements(const T& coll)
{
    for(auto iter = coll.begin(); iter != coll.end(); ++iter)
    {
        if(iter != coll.begin())
            std::cout << " --> ";
        const auto& elem = *iter;
        std::cout << elem;
    }
    std::cout << std::endl;
}

void printLists(const std::string& str, const std::forward_list<int>& list1, 
                                        const std::forward_list<int>& list2)
{
    std::cout << str << std::endl;
    std::cout << "list1: ";
    printElements(list1);
    std::cout << "list2: ";
    printElements(list2);
    std::cout << std::endl;
}

int main(void)
{
    // create two forward lists
    std::forward_list<int> list1 = {1, 2, 3, 4};
    std::forward_list<int> list2 = {77, 88, 99};
    printLists("Initial:", list1, list2);

    // insert new element at the beginning of list2
    list2.insert_after(list2.before_begin(), 99);
    list2.push_front(10);
    list2.insert_after(list2.before_begin(), {10, 11, 12, 13});
    printLists("Insert new element:", list1, list2);

    // insert all elements of list2 at the beginning of list1
    list1.insert_after(list1.before_begin(), list2.begin(), list2.end());
    printLists("List2 into list1:", list1, list2);

    // delete second element, and elements after element with value 99
    list2.erase_after(list2.begin());
    list2.erase_after(std::find(list2.begin(), list2.end(), 99), list2.end());
    printLists("Delete some elements:", list1, list2);

    // sort list1, assign it to list2, and remove duplicates
    list1.sort();
    list2 = list1;
    list2.unique();
    printLists("Sorted and unique:", list1, list2);

    // merge both sorted lists into list1
    list1.merge(list2);
    list1.unique();
    printLists("Merged:", list1, list2);

    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66

上面forward_list的示例代码运行结果如下（需要注意编译器是否支持C++11，比如g++在4.7以上版本才支持，添加-std=c++11即可）：
forward_list示例程序运行结果

本章数据结构实现源码下载地址：https://github.com/StreamAI/ADT-and-Algorithm-in-C/tree/master/datastruct

更多文章：

注：本文转载自blog.csdn.net的流云IoT的文章"https://blog.csdn.net/m0_37621078/article/details/103585026"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！