嘉兴网站建设999 999,网站首页自动下拉广告,iis怎么加载网站,医院哪个科室负责网站建设文章目录1、序列容器1.1、容器共性1.2、vectorvector 结构* vector 扩容原理* vector 迭代器失效1.3、dequedeque 结构deque 迭代器deque 模拟连续空间1.4、listlist 特殊操作list 结构list 迭代器2、关联式容器2.1、容器共性2.2、容器特性3、无序关联式容器3.1、容器共性3.2、…
文章目录1、序列容器1.1、容器共性1.2、vectorvector 结构* vector 扩容原理* vector 迭代器失效1.3、dequedeque 结构deque 迭代器deque 模拟连续空间1.4、listlist 特殊操作list 结构list 迭代器2、关联式容器2.1、容器共性2.2、容器特性3、无序关联式容器3.1、容器共性3.2、容器特性模板类的集合内部封装组织数据的方法也就是数据结构
作用存放数据
分类
序列式容器 线性关联式容器key-value 集合红黑树实现无序关联容器hash 实现
1、序列容器
序列式容器
array固定大小的数组。支持随机访问迭代器。vector动态数组。支持随机访问迭代器。deque双端队列。支持随机访问迭代器。list双向链表。只支持双向访问迭代器。forward_list单链表。只支持前向访问迭代器
序列式容器使用总结当下列操作频繁发生时
在容器中间位置添加删除元素list在容器头部位置添加删除元素deque / list在容器尾部位置添加删除元素vector / deque / list访问容器任意位置上的元素vector
1.1、容器共性
初始化
// 1、默认构造函数空容器
容器();
// 2、构造拥有 count 个有值 value 的元素的容器。
容器(size_type count,const T value T(),const Allocator alloc Allocator());
// 3、构造拥有范围 [first, last) 内容的容器。
容器(InputIt first, InputIt last, const Allocator alloc Allocator());赋值操作
// 1、重载等号操作符
operator
// 2、assign
void assign(InputIt first, InputIt last); // 以范围 [first, last) 中元素的副本替换内容。
void assign(size_type count, const T value); // 将 count 个 value 的副本替换内容。元素访问
at // 访问指定元素同时越界检查
operator[] // 访问指定元素
front // 访问第一个元素
back // 访问最后一个元素容量
// 检查容器是否无元素
bool empty() const;
// 容器中元素数量
size_type size() const;修改器
// 1. 删除容器中所有元素
void clear();// 2. 插入元素
// 在 pos 前插入 value
iterator insert(const_iterator pos, T value);
// 在 pos 前插入 value 的 count 个副本
iterator insert(const_iterator pos, size_type count, const T value);
// 原地构造元素并将参数args转发给构造函数
iterator emplace(const_iterator pos, Args... args);// 3. 容器末尾添加元素
void push_back(const T value);
// 容器末尾就地构造元素
void emplace_back(Args... args);// 4. 移除末尾元素
void pop_back();// 5. 删除元素
// 移除位于 pos 的元素。
iterator erase(iterator pos);
// 移除范围 [first, last) 中的元素。
iterator erase(iterator first, iterator last); // 6. 改变容器中可存储元素的个数
void resize(size_type count);
void resize(size_type count, T value T());// 7. 交换容器内容
void swap(deque other);1.2、vector
动态数组支持随机访问迭代器逻辑机构和物理结构一致连续线性空间空间不足时自动扩容
vector 扩容
申请新空间两倍扩容移动数据释放原空间
vector 结构
vector 使用三个指针维护动态数组 start, finish, end_of_storage 源码如下
template class _Tp, class _Alloc
class _Vector_base {
protected:_Tp* _M_start; // 指向使用空间的第一个元素 _Tp* _M_finish; // 指向使用空间的最后一个元素的下一个位置_Tp* _M_end_of_storage; // 指向可用空间的最后一个位置的下一个位置
};通过三个指针可以实现一些基本接口
iterator begin() { return _M_start; }
iterator end() { return _M_finish; }size_type size() const { return size_type(end() - begin()); }
size_type capacity() const { return size_type(_M_end_of_storage - begin()); }
bool empty() const { return begin() end(); }reference operator[](size_type __n) { return *(begin() __n); }reference front() { return *begin(); }
reference back() { return *(end() - 1); }* vector 扩容原理
vector 扩容
申请新空间两倍扩容。拷贝旧空间的元素到新空间新空间前半段存放旧数据后半段存放新插入的数据。释放原空间。
注意初始化时数组空间大小为 0扩容后新空间大小为 1。此后都是两倍扩容操作。
添加元素时先检测空间是否够用
size ! capacity在待插入位置构造新元素size capacity则进行 vector 扩容
void push_back() {// 检测是否有可用空间// 空间足够if (_M_finish ! _M_end_of_storage) {construct(_M_finish);_M_finish;}// 空间不够申请新的空间else_M_insert_aux(end());
}空间足够在待插入位置构造新元素
template class _T1, class _T2
inline void _Construct(_T1* __p, const _T2 __value) {new ((void*) __p) _T1(__value); // 定位new表达式在 _p 位置上构造一个对象
}template class _T1, class _T2
inline void construct(_T1* __p, const _T2 __value) {_Construct(__p, __value);
}空间不够扩容操作
template class _Tp, class _Alloc
void vector_Tp, _Alloc::_M_insert_aux(iterator __position, const _Tp __x)
{// 检测是否有可用空间该函数会被其他函数调用所以需要再次检查if (_M_finish ! _M_end_of_storage) {construct(_M_finish, *(_M_finish - 1));_M_finish;_Tp __x_copy __x;copy_backward(__position, _M_finish - 2, _M_finish - 1);*__position __x_copy;}else {const size_type __old_size size();// 1、申请新空间若旧空间大小为 0初始化则新空间大小为 1否则新空间为旧空间大小的 2 倍const size_type __len __old_size ! 0 ? 2 * __old_size : 1;iterator __new_start _M_allocate(__len);iterator __new_finish __new_start;// 2、将旧空间的元素复制到新空间// push_back 操作前半段用来存放旧数据后半段用来存放新数据__STL_TRY {// 将旧数据拷贝到新空间__new_finish uninitialized_copy(_M_start, __position, __new_start);// 为新元素设定初值construct(__new_finish, __x);// 调整水位__new_finish;// 拷贝插入点后的旧数据insert操作也可能导致扩容__new_finish uninitialized_copy(__position, _M_finish, __new_finish);}// 3、释放旧空间__STL_UNWIND((destroy(__new_start,__new_finish), _M_deallocate(__new_start,__len)));destroy(begin(), end());_M_deallocate(_M_start, _M_end_of_storage - _M_start);_M_start __new_start;_M_finish __new_finish;_M_end_of_storage __new_start __len;}
}* vector 迭代器失效
vector 支持随机访问迭代器普通指针天生具备。
typedef _Tp value_type;
typedef value_type* iterator;插入元素
尾部插入 size capacity尾迭代器失效size capacity所有迭代器失效动态数组扩容重新分配空间 中间插入 size capacity插入位置后的所有迭代器失效size capacity所有迭代器失效动态数组扩容重新分配空间
例在遍历容器元素的过程中添加元素的操作很危险。一旦发生扩容操作申请新的存储空间而迭代器仍指向原空间导致越界。
删除元素
尾部删除尾迭代器失效中间删除删除位置后的所有迭代器失效元素前移
例删除 vector 中值为 val 的所有元素。下面是容易导致错误的做法
// 错误写法删除后元素前移当前删除位置后的所有迭代器失效
for (auto it numbers.begin(); it ! numbers.end(); it) {if (val *it) {numbers.erase(it);}
}错误的原因在于
删除连续相同元素删除后元素前移跳过第二个要删除的元素删除最后一个元素删除后元素前移迭代器指向 end() 的下一个位置发生越界
正确的写法
for (auto it vec.begin(); it ! vec.end();) { if (val *it) { // 删除元素后不能执行 操作it vec.erase(it); } else {//未删除元素执行操作it; }
}1.3、deque
双端队列支持随机访问迭代器逻辑结构连续空间双端开口首尾插入移除元素 O(1)物理离散物理结构由多个片段构成片段内部连续片段间不连续片段的控制由中控器完成。
修改器接口
// 容器头部插入元素
void push_front( const T value );
// 容器头部就地构造元素
void emplace_front( Args... args );
// 移除容器头部元素
void pop_front();deque 结构
物理结构由多个片段构成片段内部连续片段之间不连续片段的控制由中控器完成。
deque 组成
中控器map 数组其中的每个元素node 节点是一个指针指向一块较大的连续空间缓冲区。缓冲区buffer 缓冲区实际存放数据的区域 源码如下
template class _Tp, class _Alloc __STL_DEFAULT_ALLOCATOR(_Tp)
class deque : protected _Deque_base_Tp, _Alloc {protected: typedef pointer* _Map_pointer; // 二级指针static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); }protected:using _Base::_M_map; // 连续空间每个元素是一个指针指向一个 bufferusing _Base::_M_map_size; // 容纳的指针数量using _Base::_M_start; // 哨兵指向 buffer 起始位置using _Base::_M_finish; // 哨兵指向 buffer 结束位置缓冲区 buffer 大小默认 512
// 返回每个缓冲区可容纳元素数量
inline size_t __deque_buf_size(size_t __size) {return __size 512 ? size_t(512 / __size) : size_t(1);
}deque 迭代器
deque 逻辑连续体现在 operator 和 operator–运算。deque 迭代器需要判断缓冲区位置其次当迭代器处于缓冲区边缘为了能够正确跳跃至上一个或下一个缓冲区需要中控器的支持。
dueque 迭代器组成
cur指向 buffer 的当前元素fast哨兵指向 buffer 起始位置last哨兵指向 buffer 结束位置node指向中控器 源码如下
template class _Tp, class _Ref, class _Ptr
struct _Deque_iterator {// 支持迭代器typedef random_access_iterator_tag iterator_category;typedef _Tp value_type;typedef _Ptr pointer;typedef _Ref reference;typedef size_t size_type;typedef ptrdiff_t difference_type;typedef _Tp** _Map_pointer;typedef _Deque_iterator _Self;typedef _Tp** _Map_pointer; // 二级指针指向 buffer_Tp* _M_cur; // 指向 buffer 的当前元素_Tp* _M_first; // 哨兵指向 buffer 起始位置_Tp* _M_last; // 哨兵指向 buffer 结束位置_Map_pointer _M_node; // 中控器二级指针...
};deque 插入元素首先判断插入元素在 deque 的位置 iterator insert(iterator position, const value_type __x) {// 1、若插入位置是头部if (position._M_cur _M_start._M_cur) {push_front(__x);return _M_start;}// 2、若插入位置是尾部else if (position._M_cur _M_finish._M_cur) {push_back(__x);iterator __tmp _M_finish;--__tmp;return __tmp;}// 3、若插入位置在中间else {return _M_insert_aux(position, __x);}}在 deque 中间位置插入需要移动元素为了减少移动元素次数这里有一个巧妙的设计判断插入点前和插入点后的元素数量移动元素数量少的一端。
template class _Tp, class _Alloc
typename deque_Tp, _Alloc::iterator
deque_Tp,_Alloc::_M_insert_aux(iterator __pos, const value_type __x)
{// 插入点前元素个数difference_type __index __pos - _M_start;value_type __x_copy __x;// 比较插入点前的元素数量与插入点后的元素数量// 选择元素较少的一端移动元素// 1、若插入点前元素个数较少if (size_type(__index) this-size() / 2) {// 头端插入与第一个元素值相同的元素push_front(front());iterator __front1 _M_start;__front1;iterator __front2 __front1;__front2;__pos _M_start __index;iterator __pos1 __pos;__pos1;// 元素前移copy(__front2, __pos1, __front1);}// 2、若插入点后元素个数较少else {// 尾端插入与最后一个元素值相同的元素push_back(back());iterator __back1 _M_finish;--__back1;iterator __back2 __back1;--__back2;__pos _M_start __index;copy_backward(__pos, __back2, __back1);}// 插入元素*__pos __x_copy;return __pos;
}deque 模拟连续空间
deque 迭代器模拟连续空间
reference operator[](size_type __n) { return _M_start[difference_type(__n)]; }reference front() { return *_M_start; }reference back() {iterator __tmp _M_finish;--__tmp;return *__tmp;
}size_type size() const { return _M_finish - _M_start; }bool empty() const { return _M_finish _M_start; }**operator ***
reference operator*() const { return *_M_cur; }set_node
实现 node 节点 (buffer) 跳转
void _M_set_node(_Map_pointer __new_node) {_M_node __new_node;_M_first *__new_node;_M_last _M_first difference_type(_S_buffer_size());
}difference_type operator-
两个迭代器的距离 两个迭代器间的 buffers 总长度 起始 buffer 长度 末尾当前buffer 长度
两个迭代器间的 buffers 长度bufferSize * 首尾 buffer 间的 buffers 数量-1 是排除起始边界 buffer起始 buffer 的元素数量__x._M_last - __x._M_cur末尾 buffer 的元素数量_M_cur - _M_first
difference_type operator-(const _Self __x) const {// 两个迭代器间的 buffers 总长度 起始 buffer 长度 末尾当前buffer 长度return difference_type(_S_buffer_size()) * (_M_node - __x._M_node - 1) (_M_cur - _M_first) (__x._M_last - __x._M_cur);
}operator
// 前置
_Self operator() {_M_cur;// 判断是否到了 buffer 边界终点if (_M_cur _M_last) {// 跳转至下一个node节点(buffer)的起点_M_set_node(_M_node 1);_M_cur _M_first;}return *this;
}// 后置
_Self operator(int) {_Self __tmp *this;// 前置实现后置*this;return __tmp;
}operator–
// 前置--
_Self operator--() {// 判断是否到了 buffer 边界起点if (_M_cur _M_first) {// 跳转至前一个node节点(buffer)的终点_M_set_node(_M_node - 1);_M_cur _M_last;}--_M_cur;return *this;
}// 后置--
_Self operator--(int) {_Self __tmp *this;// 前置--实现后置----*this;return __tmp;
}operator
_Self operator(difference_type __n) {difference_type __offset __n (_M_cur - _M_first);// 目标位置在同一 buffer 内if (__offset 0 __offset difference_type(_S_buffer_size()))_M_cur __n;// 目标位置不在同一 buffer 内else {difference_type __node_offset __offset 0 ? __offset / difference_type(_S_buffer_size()): -difference_type((-__offset - 1) / _S_buffer_size()) - 1;// 切换到目标 node 节点(buffer)_M_set_node(_M_node __node_offset);// 切换至正确元素_M_cur _M_first (__offset - __node_offset * difference_type(_S_buffer_size()));}return *this;}operator
_Self operator(difference_type __n) const {_Self __tmp *this;// 内部调用 实现return __tmp __n;
}operator-
内部调用 偏移量 -n
// 内部调用 -n
_Self operator-(difference_type __n) { return *this -__n; }operator-
内部调用 -
_Self operator-(difference_type __n) const {_Self __tmp *this;return __tmp - __n;
}1.4、list
list 双向链表支持双向访问迭代器物理结构循环双向链表逻辑结构双向链表
list 特殊操作
// 1、从一个链表转移元素到另一个链表
// 移动一个链表到另一个链表的某个指定位置
void splice(const_iterator pos, list other);
void splice(const_iterator pos, list other)
// 移动一个链表中的某个元素到另一个链表的某个指定位置
void splice(const_iterator pos, list other, const_iterator it)
void splice(const_iterator pos, list other, const_iterator it);
// 移动一对迭代器范围元素到另一个链表的某个指定位置
void splice(const_iterator pos, list other, const_iterator first, const_iterator last)
void splice(const_iterator pos, list other,const_iterator first, const_iterator last)// 2、对元素进行排序
void sort();
template class Compare void sort(Compare comp);
template typename T
struct Compare {bool operator()(const T a, const T b) const {return a b;}
}; // 3、合并两个已排序的链表
void merge(list other);// 4、将该链表的所有元素的顺序反转
void reverse();// 5、移除满足特定标准的元素
void remove(const T value);
void remove_if(UnaryPredicate p)// 6、删除连续的重复元素
void unique();list 结构
list 通过 node 指针可以实现遍历循环链表尾端留有空白节点符合左闭右开成为 last 迭代器。 list node
prev指向前一个节点next指向下一个节点data存储数据 struct _List_node_base {_List_node_base* _M_next;_List_node_base* _M_prev;
};template class _Tp
struct _List_node : public _List_node_base {_Tp _M_data;
};list 迭代器
templateclass _Tp, class _Ref, class _Ptr
struct _List_iterator : public _List_iterator_base {// 1、typedeftypedef _List_iterator_Tp,_Tp,_Tp* iterator;typedef _List_iterator_Tp,const _Tp,const _Tp* const_iterator;typedef _List_iterator_Tp,_Ref,_Ptr _Self;typedef _Tp value_type;typedef _Ptr pointer;typedef _Ref reference;typedef _List_node_Tp _Node;// 2、运算符重载...
}; 运算符重载
reference operator*() const { return ((_Node*) _M_node)-_M_data; }pointer operator-() const { return (operator*()); }void _M_incr() { _M_node _M_node-_M_next; }
void _M_decr() { _M_node _M_node-_M_prev; }_Self operator() { this-_M_incr();return *this;
}
_Self operator(int) { _Self __tmp *this; // 先调用重载在调用重载*因此这里调用的是拷贝构造this-_M_incr();return __tmp;
}
_Self operator--() { this-_M_decr();return *this;
}
_Self operator--(int) { _Self __tmp *this;this-_M_decr();return __tmp;
}2、关联式容器
2.1、容器共性
容器共性
底层实现红黑树查找元素时间复杂度O(logN)默认情况下按照关键字 key 升序排列不能修改关键字 key 的值支持双向访问迭代器
面试红黑树的特征
节点是红色或黑色根节点必须是黑色叶子节点都是黑色红色节点的孩子节点必须是黑色的。黑色节点的孩子节点可以是黑色的。从根节点到叶子节点的所有路径的黑色节点的个数相同
扩展从根节点到叶子节点的路径上不存在连续的红色节点
最短路径节点都是黑色的最长路径红黑相间2 * 黑色节点数 - 1红色节点数 黑色节点数 - 1
2.2、容器特性
容器分类set / mapkey 唯一multiset / multimapkey 不唯一。
set
存放 key 的有序集合插入操作insert返回std::pairiterator, bool查找操作count / find删除操作erase
map
存放键值对pairconst key, value。可以使用std::pair或std::make_pair存放元素。支持下标访问运算符注意查询时对应的 key 若不存在会直接创建该 key 的记录
3、无序关联式容器
3.1、容器共性
底层实现哈希表桶 单链表存放的元素是无序的针对自定义类型必须自定义 std::hash和 std::equal_to
面试hash table 哈希冲突不同的 key散列到相同的地址即 H(key1) H(key2)哈希冲突解决方法链地址法STL、开放定址法、再散列法装载因子 实际装载数据的长度 n / 哈希表长 m当负载因子过大时rehash
3.2、容器特性 unordered_set unordered_map unordered_multiset unordered_multimap
例自定义 point 类型无法使用无序关联式容器。
定义std::hash
自定义函数对象扩展std::hash的模板特化版本函数调用运算符设计成 const 版本
// 1、自定义哈希函数
// 1.1、扩展 std::hash 的模板特化版本
namespace std {
template
// 1.2、自定义函数对象
struct hashPoint {// 1.3、函数调用运算符设计成 const 版本size_t operator()(const Point rhs) const {// 自定义哈希函数return (rhs.getX() 1) ^ (rhs.getY() 1);}
};定义 std::equal_to重载函数调用运算符或重载等号运算符或使用模板特化
bool operator() (const T lhs, const T rhs) const {return lhs rhs;
}bool operator (const T lhs, const T rhs) {return lhs rhs;
}namespace std {
template
struct equal_toPoint {bool operator()(const Point lhs, const Point rhs) const {return (lhs.getX() rhs.getX()) (lhs.getY() rhs.}
};
}//end of namespace std
