flask网站开发源码,云南哪里有给做网站的,软件开发好做吗,营销助手app官方下载STL和泛型编程 一.STL六大部件前开后闭区间 二.容器(1)顺序容器1.array源码剖析 2.vector源码剖析vector的迭代器 3.list源码剖析迭代器的设计规则关于重载操作符关于重载-和*操作符 4.forward_list源码剖析 5.deque源码剖析底层数据结构操作实现deque的设计de… STL和泛型编程 一.STL六大部件前开后闭区间 二.容器(1)顺序容器1.array源码剖析 2.vector源码剖析vector的迭代器 3.list源码剖析迭代器的设计规则关于重载操作符关于重载-和*操作符 4.forward_list源码剖析 5.deque源码剖析底层数据结构操作实现deque的设计deque的迭代器deque的插入deque模拟连续空间 (2)容器适配器1.stack2.queuequeue和stack源码剖析 (3)关联式容器1.mutiset2.multimap (4)哈希结构1.unordered_multiset2.unordered_multimap (5)元素不可以重复1.set2.map3.unordered_set4.unordered_map 三.OOP VS GP四.分配器五. 红黑树源码剖析测试以红黑树为底层的容器set、multiset源码剖析 map、multimap源码剖析map独有的[] 六. 哈希表源码剖析测试unordered容器 七. 算法迭代器的分类验证容器的迭代器种类迭代器分类对算法的影响 算法源代码剖析1.accumulate2.for_each3.replace,replace_if,replace_copy4.count,count_if5.find,find_if6.sort7.binary_search 八. 仿函数(函数对象)STL仿函数编写条件 九. 适配器1.binder2nd2.not13.bind 八. 仿函数(函数对象)STL仿函数编写条件 九. 适配器1.binder2nd2.not13.bind 以STL为目标探讨泛型编程。 一.STL六大部件 算法通过迭代器来处理容器中的数据。
容器使用分配器来管理它们的内存。分配器将内存分配和释放的实现细节封装起来使得容器可以在运行时根据需要动态地分配内存。
适配器允许在现有的容器或迭代器之上实现不同的行为或提供新的接口从而更加方便地操作数据。
仿函数通常用于算法、容器和其他组件中以提供各种功能和灵活性。它们可以作为算法的参数传递也可以用于自定义容器的排序、查找和比较操作等。使用仿函数可以在编译时将函数调用行为封装到对象中从而提供更灵活和通用的功能。算法通常通过仿函数来完成比较、排序和其他操作这使得算法可以适用于各种数据类型和需求。 前开后闭区间
所有容器满足前开后闭区间 二.容器 array无法扩充。 vector尾可以扩充。 deque头尾都可以扩充。
set和map一般是红黑树实现unordered_set和unordered_map一般是hash表实现(分离链接法)。
(1)顺序容器
1.array 源码剖析 2.vector 源码剖析 几乎所有vector的实现都是当vector需要扩充的时候进行两倍成长。会造成大量的拷贝构造和析构。 vector的迭代器 3.list 源码剖析 list本身就是一个指针(link_type),link_type是一个指针(list_node*)指向了一个_list_node结构体。
list是非连续空间因此iterator不能是指针只有vector和array的iterator是指针其余都是结构体。 迭代器的设计规则
迭代器必须定义五种类型以便于能回答算法的问题。 1.迭代器的类型。关于前向、双向、随机等。
2.两个迭代器间的距离。
3.迭代器指向的元素的类型。 iterator_traitsIterator::value_type迭代器指向的元素的类型。iterator_traitsIterator::difference_type两个迭代器之间的差值类型。这通常用于表示两个迭代器之间的距离。iterator_traitsIterator::iterator_category迭代器的类型分类如 std::input_iterator_tag、std::forward_iterator_tag、std::bidirectional_iterator_tag 或 std::random_access_iterator_tag。这用于区分迭代器的不同能力。iterator_traitsIterator::pointer 和 iterator_traitsIterator::reference这两个类型通常分别定义为 value_type* 和 value_type但某些迭代器类型可能会提供特殊的指针或引用类型。 为了应付迭代器有指针的形式需要一个中间层traits。traits中使用了模板的偏特化区分当参数是指针或类。 关于重载操作符 重载后置
先调用拷贝构造函数将当前的对象复制给tmp然后对当前对象进行前置操作最后返回tmp
关于返回值
因为标准库中后置不可以连做两次因此这里值传递返回。前置可以连做两次返回引用。
关于重载-和*操作符 list的指针类型修改为指向自己的相比于指向void更精确。
4.forward_list
只提供push_front插入且不提供size()。 源码剖析 5.deque 源码剖析 在C标准库中deque双端队列的实现是优化了从序列两端插入和删除操作的容器。与vector相比它不保证所有元素都在连续的内存地址中但仍然能够提供对任何元素的直接随机访问访问。这是通过一个复杂的内部数据结构实现的旨在兼顾两端操作的高效性和随机访问的能力。
底层数据结构
deque的实现通常采用一种“分块数组”或称为“段数组”的策略。具体来说
多个固定大小的数组块deque由多个数组块组成每个块能够存储固定数量的元素。这些数组块的大小通常是实现定义的可以根据元素的类型和容器的大小动态调整以优化性能。映射器Mapdeque内部使用一个中心数据结构通常是一个数组或动态数组来维护对这些块的引用指针或索引。这个中心结构被称为映射器它按序记录了所有块的位置使得可以快速定位到任何一个元素所在的块。
操作实现
随机访问通过映射器deque可以计算出任何元素的位置即首先定位到正确的块然后在该块内进行索引。这使得随机访问的时间复杂度为O(1)与vector相同。在两端插入和删除由于deque的设计它可以在头部或尾部添加或移除元素而无需移动其他元素。如果在一端的块已满且需要添加更多元素时deque将分配一个新的块并更新映射器。这种操作通常比vector的动态扩容涉及复制现有元素到新的内存地址更高效。动态扩容当deque增长到超出当前映射器容量时它需要一个更大的映射器来存储更多的块引用。此时deque将分配一个新的更大的映射器复制旧映射器中的引用到新映射器中然后释放旧映射器。
deque的设计 deque的迭代器 deque的插入 deque模拟连续空间 (2)容器适配器
不提供iterator因为一定是一端进一端出。提供iterator会导致可以从任意地方进出容器破坏一致性。
1.stack 2.queue queue和stack源码剖析 (3)关联式容器
1.mutiset key就是valuevalue就是key。 2.multimap (4)哈希结构
1.unordered_multiset 2.unordered_multimap (5)元素不可以重复
1.set 2.map 3.unordered_set 4.unordered_map 三.OOP VS GP 因为在模板sort的内部对迭代器进行了跳跃式操作只有随机访问迭代器可以这么操作。
而list的迭代器是双向迭代器只支持和–。 优点 四.分配器
C标准库在很多地方采用特殊对象处理内存的分配和规划这样的对象称为分配器(allocator)。allocator表现出一种特殊内存模型被当成一种用来把内存需求转换为内存低级调用的抽象层。
C标准库中链表模板的完整参数定义是
templateclass T, class AllocallocatorT
class list;当省略最后的模板参数时容器将采用标准中预定义的分配器std::allocatorT。该分配器调用new/delete操作符申请和释放内存足以满足大多数需求。而当需要定制容器中的内存操作时可以按照标准中的分配器规范将内存操作封装在一个新的分配器类模板中并传入容器比如
std::listmy_data, my_allocatormy_data custom_list;标准库中可以接受分配器的容器模板包括
序列型容器vector、deque、list、forward_list集合容器set、multiset、map、multimap散列表容器unordered_set、unordered_multiset、unordered_map、unordered_multimap
具体来说 分配器是一个类(class Alloc)而不是函数或者模板 分配器是和具体类型相关的因为默认构造器std::allocatorT随容器保存类型的不同而不同。 可以想象分配器的行为应该类似new/delete操作符而不是malloc/free前者需要知道空间所存放的类型而后者只关心空间的大小。 分配器内至少需要有两个成员函数分别响应容器的申请以及释放内存的请求。 分配器的首要作用是申请与释放内存。通过两个成员函数allocate和deallocate来实现。无论其定义如何两成员函数必须能够实现如下用法
a.allocate(n); // 申请能保存n个value_type的数据 如果申请空间失败抛出异常std::bad_alloc
a.allocate(n, p);
a.deallocate(p, n); //要释放的空间指针p和空间大小n五. 红黑树 源码剖析 测试 以红黑树为底层的容器
set、multiset 源码剖析 map、multimap 源码剖析 map独有的[] 六. 哈希表 空间足够的时候假如有2的32次方元素变化可以用4G的空间来存储。但是这是不可能的。
空间不够的时候假如有2的32次方元素变化因此需要取模将元素放入对应的格子中。但是会发生碰撞因此用链表将碰撞的元素串起来。
如果某个格子串起来的元素的个数大于格子的总数说明格子空间不够了因此重新划分格子数目。 源码剖析 测试 对数值来说传进去的数值就是编号。 对字符来说选一种方法能尽可能打乱。 unordered容器 七. 算法 算法的所有操作都依赖迭代器。
迭代器的分类 随机访问迭代器vector、array、deque
双向访问迭代器list、set、multisest、map、multimap
单向访问迭代器forward_list
验证容器的迭代器种类 迭代器分类对算法的影响 distance算法针对不同的迭代器使用不同的方法计算距离。 返回类型就是difference_type。 算法源代码剖析
1.accumulate 2.for_each 3.replace,replace_if,replace_copy replace 函数用于将容器中的某个值替换为另一个值。
函数原型
templateclass ForwardIt, class T, class U
void replace(ForwardIt first, ForwardIt last, const T old_value, const U new_value);first, last指定要搜索的容器范围。old_value要被替换的值。new_value替换后的新值。
示例
#include iostream
#include vector
#include algorithm int main() { std::vectorint vec {1, 2, 3, 2, 4, 2, 5}; std::replace(vec.begin(), vec.end(), 2, 9); for (int x : vec) { std::cout x ; } // 输出1 9 3 9 4 9 5 return 0;
}在这个例子中我们将 vec 中所有的 2 替换为 9。
replace_if 函数用于根据谓词即一个返回布尔值的函数或函数对象的条件来替换容器中的元素。
函数原型
templateclass ForwardIt, class UnaryPredicate, class T
void replace_if(ForwardIt first, ForwardIt last, UnaryPredicate p, const T new_value);first, last指定要搜索的容器范围。p一个一元谓词用于测试每个元素是否应被替换。new_value替换后的新值。
示例
#include iostream
#include vector
#include algorithm bool is_even(int n) { return n % 2 0;
} int main() { std::vectorint vec {1, 2, 3, 4, 5, 6}; std::replace_if(vec.begin(), vec.end(), is_even, 0); for (int x : vec) { std::cout x ; } // 输出1 0 3 0 5 0 return 0;
}在这个例子中我们使用 is_even 谓词来检查 vec 中的每个元素是否为偶数并将所有偶数替换为 0。
replace_copy 函数与 replace 类似但它不会修改原始容器而是将替换后的结果复制到另一个容器中。
函数原型
templateclass InputIt, class OutputIt, class T, class U
OutputIt replace_copy(InputIt first, InputIt last, OutputIt d_first, const T old_value, const U new_value);first, last指定要搜索的输入容器范围。d_first指向输出容器的开始迭代器。old_value要被替换的值。new_value替换后的新值。
示例
#include iostream
#include vector
#include algorithm int main() { std::vectorint vec {1, 2, 3, 2, 4, 2, 5}; std::vectorint result; result.resize(vec.size()); // 预先分配足够的空间 std::replace_copy(vec.begin(), vec.end(), result.begin(), 2, 9); for (int x : result) { std::cout x ; } // 输出1 9 3 9 4 9 5 // 注意原始 vec 容器没有被修改 return 0;
}在这个例子中我们将 vec 中所有的元素复制到result容器中如果遇到值为2的元素将其改为9复制到result中。
4.count,count_if count 函数用于统计容器中等于某个特定值的元素数量。
函数原型
templateclass InputIt, class T
size_t count(InputIt first, InputIt last, const T value);first, last指定要搜索的容器范围。value要搜索的值。
示例
#include iostream
#include vector
#include algorithm int main() { std::vectorint vec {1, 2, 3, 2, 4, 2, 5}; size_t count_of_two std::count(vec.begin(), vec.end(), 2); std::cout Number of 2 in vec: count_of_two std::endl; // 输出Number of 2 in vec: 3 return 0;
}count_if 函数用于统计容器中满足某个谓词即一个返回布尔值的函数或函数对象的元素数量。
函数原型
templateclass InputIt, class UnaryPredicate
size_t count_if(InputIt first, InputIt last, UnaryPredicate p);first, last指定要搜索的容器范围。p一个一元谓词用于测试每个元素是否应被计入统计。
示例
#include iostream
#include vector
#include algorithm bool is_even(int n) { return n % 2 0;
} int main() { std::vectorint vec {1, 2, 3, 4, 5, 6}; size_t count_of_evens std::count_if(vec.begin(), vec.end(), is_even); std::cout Number of even numbers in vec: count_of_evens std::endl; // 输出Number of even numbers in vec: 3 return 0;
}在这个例子中我们定义了一个 is_even 谓词来检查一个整数是否为偶数并使用 count_if 统计 vec 中偶数的数量结果是 3。
5.find,find_if 6.sort 7.binary_search 八. 仿函数(函数对象) STL仿函数编写条件 unary_function一个参数
binary_function两个参数
九. 适配器 1.binder2nd 注意区分小括号是直接调用函数还是创建函数对象。
2.not1 3.bind 7411967)]
八. 仿函数(函数对象)
[外链图片转存中…(img-FKy1J6zp-1711347411967)]
[外链图片转存中…(img-K8lnpskn-1711347411967)]
[外链图片转存中…(img-4fNkLvv0-1711347411967)]
STL仿函数编写条件
[外链图片转存中…(img-LQs5p3Y0-1711347411967)]
unary_function一个参数
binary_function两个参数
九. 适配器
[外链图片转存中…(img-ssSnydJm-1711347411968)]
[外链图片转存中…(img-Wan0qRXc-1711347411968)]
1.binder2nd
[外链图片转存中…(img-Zzkjq2ht-1711347411968)]
注意区分小括号是直接调用函数还是创建函数对象。
2.not1
[外链图片转存中…(img-eVhrrKOu-1711347411968)]
3.bind
[外链图片转存中…(img-XHB9sF1W-1711347411968)]
[外链图片转存中…(img-hDiOBKs8-1711347411968)]
[外链图片转存中…(img-8kZRm5Ds-1711347411968)]
[外链图片转存中…(img-PgOUiWZA-1711347411968)]
[外链图片转存中…(img-CM2boWpx-1711347411968)]
