网站死循环,怎么做dnf辅助网站,湖南长沙公司有哪些,外贸网站哪个比较好目录
序列式容器
Vector
vector概述
vector的迭代器
vector的数据结构
vector的构造和内存管理
vector的元素操作
List
List概述
List的设计结构
List的迭代器
List的数据结构
List的内存构造
List的元素操作 C标准模板库#xff08;STL#xff09;是一组高效的…目录
序列式容器
Vector
vector概述
vector的迭代器
vector的数据结构
vector的构造和内存管理
vector的元素操作
List
List概述
List的设计结构
List的迭代器
List的数据结构
List的内存构造
List的元素操作 C标准模板库STL是一组高效的数据结构和算法的集合广泛应用于C程序设计中。STL由六大核心组件组成分别是
容器Containers各种数据结构如vectorlistdeque等等。迭代器Iterators扮演容器域算法之间的胶合剂是所谓的”泛型指针“算法Algorithms各种常用算法例如sortsearchcopyerase等等。函数对象Function Objects又名为仿函数行为类似函数可作为算法的某种策略。适配器Adapters一种用来修饰容器或者仿函数或迭代器接口的东西例如stack和queue。分配器Allocators负责空间配置域管理从实现角度来看他是一个管理空间的模板类。 STL六大组件的交互关系容器通过分配器获取数据存储空间算法则通过迭代器去存取容器的内容这也是为什么说迭代器是类似于一种胶合剂的角色仿函数则可以协助算法完成不同的策略变化适配器可以修饰或者套接仿函数。 在 C 中STLStandard Template Library标准模板库提供了一系列容器来帮助程序员组织和管理数据。常用的数据结构有aray(数组)、list(链表)、tee(树)stack(堆栈)、queue(队列)、hashtable(散列表)、set(集合)、map(映射表)…等等。当提到STL时许多人的第一印象便是容器这也证明了容器的可靠性以及受欢迎程度。 STL 容器大致可以分为两类序列式容器Sequence Containers和关联式容器Associative Containers。如其各自的名字一般序列式就是按照顺序排列的容器。而关联式容器就是通过键值和键值对进行查找的。
常见的序列式容器包括
vector向量动态数组支持随机访问内部连续存储。list链表双向链表不支持随机访问插入和删除操作非常快。deque双端队列支持两端快速插入和删除的容器支持随机访问。forward_list单向链表C11 引入的新容器单向链表不支持随机访问。
常见的关联式容器包括
set集合存储唯一的键值不允许重复通常按照键的字典序排序。multiset多重集合类似 set但允许键值重复。map映射存储键值对键唯一通常按照键的字典序排序。multimap多重映射类似 map但允许键值重复。
序列式容器
Vector
vector概述 vector的数据结构跟array是非常相似的只不过他们有一点不同那就是array在定义时会被限制住大小是静态的容量。而vector则是动态的容量可以根据插入数据的数量去自动扩容容量。我们不必再去担心初始化数组的时候去定义一个大块头使用vector时这个顾虑将烟消云散。 vector的实现技术关键在于对其大小的控制以及重新分配时数据迁移的效率一旦vector的空间满载如果客户端每新增一个元素vector随之去增加一个元素这种效率肯定是很慢的。所以vector是采用的未雨绸缪机制。
vector的迭代器 vector维护的是一个连续线性空间所以无论是什么类型的元素普通指针都可以作为vector的迭代器而满足所有的必要条件。因为vector迭代器的操作指针都可以完成无非就是加减乘除加加减减等操作。所以vector迭代器的定义正是普通指针。 vector的数据结构 vector的数据结构也是非常简单线性连续空间。它以两个迭代器start和finish分别指向所分配空间的目前已使用范围的头和尾其中end_of_storage则是用来指向分配空间的尾。 为了提高数据迁移时的效率vector引入未雨绸缪的机制。这个机制就是vector实际配置的大小要比客户端需求的大小更大以备将来的扩充降低分配空间的次数。这个不难理解。 通过startfinishend_of_storage三个迭代器便可轻易的提供首位标示大小容量空容器判断等。
下方是vector的整体示意图 vector的构造和内存管理 我们围绕这个小测试程序说起。
// filename : vector-test.cpp
#include vector
#include iostream
#include algorithmusing namespace std;int main() {int i;vectorint iv(2, 9);cout size iv.size() endl; // size2cout capacity iv.capacity() endl; // capacity2iv.push_back(1);cout size iv.size() endl; // size3cout capacity iv.capacity() endl; // capacity4iv.push_back(2);cout size iv.size() endl; // size4cout capacity iv.capacity() endl; // capacity4iv.push_back(3); cout size iv.size() endl; // size5cout capacity iv.capacity() endl; // capacity8iv.push_back(4);cout size iv.size() endl; // size6cout capacity iv.capacity() endl; // capacity8for (i 0; i iv.size(); i)cout iv[i] ; // 9 9 1 2 3 4cout endl;iv.push_back(5);cout size iv.size() endl; // size7cout capacity iv.capacity() endl; // capacity8for (i 0; i iv.size(); i)cout iv[i] ; // 9 9 1 2 3 4 5cout endl;iv.pop_back();iv.pop_back();cout size iv.size() endl; // size5cout capacity iv.capacity() endl; // capacity8cout endl;iv.pop_back();cout size iv.size() endl; // size4cout capacity iv.capacity() endl; // capacity8vectorint::iterator ite find(iv.begin(), iv.end(), 1);if (ite ! iv.end())iv.erase(ite);cout size iv.size() endl; // size3cout capacity iv.capacity() endl; // capacity8for (i 0; i iv.size(); i)cout iv[i] ; // 9 9 2cout endl;ite find(iv.begin(), iv.end(), 2);if (ite ! iv.end())iv.insert(ite, 3, 7);cout size iv.size() endl; // size6cout capacity iv.capacity() endl; // capacity8for (int i 0; i iv.size(); i)cout iv[i] ; // 9 9 7 7 7 2cout endl;iv.clear();cout size iv.size() endl; // size0cout capacity iv.capacity() endl; // capacity8return 0;
} 从这段小的测试例子来看我们不难发现vector的分配空间的机制正如我们所了解的一样它在扩容时会进行更大量级的扩容又是双倍扩容。vector缺省使用alloc作为空间配置器并据此定义了一个data_allocator为的是方便以元素大小为配置单位。 当我们使用push_back将新元素插入尾部时该函数首先会去检测是否还有备用空间如果有就不扩容在备用空间上进行构造并调整finish如果没有就回去调用insert_aux扩容空间重新配置移动数据释放空间。 template class T, class Alloc
void vectorT, Alloc::insert_aux(iterator position, const T x) {if (finish ! end_of_storage) { // 还有备用空间// 在备用空间起始处构造一个元素并以vector最后一个元素值为其初值construct(*finish, *finish-1);finish;// 复制待插入的元素值T x_copy x;// 将 [position, finish-1) 区间的元素向后移动一位copy_backward(position, finish-1, finish);*position x_copy;} else { // 已无备用空间const size_type old_size size(); // 记录旧的大小const size_type len (old_size ! 0 ? 2 * old_size : 1); // 新大小如果原大小为0则配置1否则配置原大小的两倍// 分配新的内存空间iterator new_start data_allocator::allocate(len);iterator new_finish new_start;try {// 将原 vector 的内容拷贝到新 vectornew_finish uninitialized_copy(start, position, new_start);// 为新元素设定初值 xconstruct(*new_finish, x);new_finish;// 将原 vector 的备用空间中的内容也忠实复制过来new_finish uninitialized_copy(position, finish, new_finish);} catch (...) {// 如果出现异常销毁新分配的内存并释放destroy(new_start, new_finish);data_allocator::deallocate(new_start, len);throw;}// 析构并释放原 vectordestroy(begin(), end());deallocate();// 调整迭代器指向新 vectorstart new_start;finish new_finish;end_of_storage new_start len;}
} 这里还需提一嘴所谓的动态增加大小并非是像链表一般直接在后方增加新的扩容空间因为vector的本质还是数组所以它增加大小的方式和数组是相同的大家不要误解。因此一旦引起空间重新配置那么原来vector的迭代器都将失效切记。
vector的元素操作 这里我不再多说大家可以参考我之前学习vector操作时的一篇文章。
C基础知识八STL标准库Vectors和list_c stl标准库-CSDN博客https://blog.csdn.net/LKHzzzzz/article/details/136316825 List
List概述 相对于vectorlist则显得更为复杂一下。但是list本身的优势也是vector没有的。例如插入一个元素就会配置一个元素空间这就做到了对空间运用的绝对精准同时这也是许多大型项目中经常用到的一种数据结构例有Linux内核其中对list的运用更是出神入化不得不感叹大神的智慧。但是vector和list各有各的优势还需要取决于在什么场景下用那个数据结构。
List的设计结构 list的本身和list的节点是不同的结构需要分开进行设计以下是一个双向链表的节点机构。 List的迭代器 List的迭代器不能再像vector一般用一个普通指针作为迭代器因为list的节点不是连续存在的所以list迭代器必须要有能力指向list的节点并可以进行--等操作。这里我们可以看出来list是一个双向列表那么我们的迭代器也就必须具备前移和后退的能力。 注list的迭代器在析构这个list之前都是有效的与vector并不相同 以下是list的迭代器结构
template typename T, typename Ref, typename Ptr
struct list_iterator {typedef list_iteratorT, T, T* Self; // 自定义类型别名typedef bidirectional_iterator_tag iterator_category; // 迭代器类别typedef T value_type; // 值类型typedef Ptr pointer; // 指针类型typedef Ref reference; // 引用类型typedef std::listT::node* link_type; // 节点类型typedef std::size_t size_type; // 大小类型typedef std::ptrdiff_t difference_type; // 差值类型private:link_type node; // 迭代器内部的指针指向 list 的节点public:// 构造函数list_iterator(link_type x) : node(x) {}list_iterator() : node(nullptr) {} // 默认构造函数list_iterator(const Self x) : node(x.node) {} // 拷贝构造函数// 比较运算符bool operator(const Self x) const { return node x.node; }bool operator!(const Self x) const { return node ! x.node; }// 解引用运算符reference operator*() const { return (*node).data; }// 成员访问运算符pointer operator-() const { return (*this-operator*()); }// 前缀递增运算符Self operator() {node link_type((*node).next);return *this;}// 后缀递增运算符Self operator(int) {Self tmp *this;(*this);return tmp;}// 前缀递减运算符Self operator--() {node link_type((*node).prev);return *this;}// 后缀递减运算符Self operator--(int) {Self tmp *this;--(*this);return tmp;}
};
List的数据结构 List不仅仅是一个双向链表而且还是一个环状双向链表。所以它只需要一个指针便可以完整表现整个链表。 List的内存构造
让我们先从一段小的测试例子看起
#include list
#include iostream
#include algorithmusing namespace std;int main() {int i;listint ilist;cout size ilist.size() endl; // size0ilist.push_back(0);ilist.push_back(1);ilist.push_back(2);ilist.push_back(3);ilist.push_back(4);cout size ilist.size() endl; // size5listint::iterator ite;for (ite ilist.begin(); ite ! ilist.end(); ite) {cout *ite ;}cout endl; // 输出 0 1 2 3 4cout endl;ite find(ilist.begin(), ilist.end(), 3);if (ite ! ilist.end()) {ilist.insert(ite, 99);}cout size ilist.size() endl; // size6cout *ite endl; // 输出 99for (ite ilist.begin(); ite ! ilist.end(); ite) {cout *ite ;}cout endl; // 输出 0 1 2 99 3 4cout endl;ite find(ilist.begin(), ilist.end(), 1);if (ite ! ilist.end()) {cout *(ilist.erase(ite)) endl; // 输出 2}for (ite ilist.begin(); ite ! ilist.end(); ite) {cout *ite ;}cout endl; // 输出 0 2 99 3 4cout endl;return 0;
} 当我们以push_back插入元素的时候他的底层调用的其实是Insert函数
void push_back(const T x){insert(end()x); insert是一个重载函数有多种形式但是在list中用的就是最简单一步操作也就是单纯的去插入一个元素首先构造一个元素空间然后在尾部进行一系列的操作把新元素插入进去。
list_nodeT *insert(list_nodeT *position, const T x)
{list_nodeT *tmp create_node(x); // 产生一个节点内容为 x// 调整双向指针使 tmp 插入进去tmp-next position;tmp-prev position-prev;// 更新前后节点的指针(static_castlist_nodeT *(position-prev))-next tmp;position-prev tmp;return tmp;
} 插入之后的list状态也就如下图一般。由于list不像vector一般会在扩容时重新分配空间然后转移过去然后析构因此list的迭代器是一直有效的。 List的元素操作 这里大家可以去看一下我之前写的一篇基本操作文章关于List的这里就不多说了。
C基础知识八STL标准库Vectors和list_c stl标准库-CSDN博客https://blog.csdn.net/LKHzzzzz/article/details/136316825
