做网站教程如乐,做系统网站建设,用自己的电脑做网站,精准网络营销推广1.OOP面向对象编程 vs. GP泛型编程
OOP将data和method放在一起#xff0c;目的是通过封装、继承、多态提高软件的可维护性和可扩展性GP将data和method分开#xff0c;可以将任何容器与任何算法结合使用#xff0c;只要容器满足塞饭所需的迭代器类型
2.算法与仿函数的区别 …1.OOP面向对象编程 vs. GP泛型编程
OOP将data和method放在一起目的是通过封装、继承、多态提高软件的可维护性和可扩展性GP将data和method分开可以将任何容器与任何算法结合使用只要容器满足塞饭所需的迭代器类型
2.算法与仿函数的区别
bool strLonger(const string s1, const string s2)
{return s1.size() s2.size();
}// 算法
cout max of zoo and hello: max(string(zoo), string(hello)) endl;
// 仿函数
cout max of zoo and hello: max(string(zoo), string(hello), strLonger) endl;3.泛化、特化、偏特化
泛化支持广泛的数据类型和情况而不是针对特定类型特化为特定类型或一组类型提供特定的实现
#include iostream// General template
template typename T
void print(T arg) {std::cout General print: arg std::endl;
}// Specialization for const char*
template
void printconst char*(const char* arg) {std::cout Specialized print for const char*: arg std::endl;
}int main() {print(123); // Uses general templateprint(Hello, world); // Uses specialized template
}偏特化针对特定类型组合提供优化的行为或特殊实现。完全特化需要指定模板的所有参数偏特化只需指定部分参数或对参数施加某些约束。 第一种偏特化处理第二个模板参数为 int 的情况。第二种偏特化处理两个模板参数相同的情况。
#include iostream// 基本模板
template typename T, typename U
class MyClass {
public:void print() {std::cout Base template\\n;}
};// 偏特化特化第二个类型为 int 的情况
template typename T
class MyClassT, int {
public:void print() {std::cout Partially specialized template for T and int\\n;}
};// 偏特化特化两个类型都为相同类型的情况
template typename T
class MyClassT, T {
public:void print() {std::cout Partially specialized template for T, T\\n;}
};int main() {MyClassdouble, double myClass1; // 会匹配 MyClassT, TMyClassdouble, int myClass2; // 会匹配 MyClassT, intMyClassdouble, char myClass3; // 会匹配基本模板 MyClassT, UmyClass1.print(); // 输出: Partially specialized template for T, TmyClass2.print(); // 输出: Partially specialized template for T and intmyClass3.print(); // 输出: Base template
}4.分配器allocates
分配器allocators是用来管理内存分配和回收的对象。
在 VC6 中operator new() 通常通过调用 malloc() 实现 malloc() 函数不仅会开辟用户请求的内存外还会引入额外的内存开销
void* operator new(size_t size) {void* p malloc(size);if (p 0) // 如果malloc失败则抛出std::bad_alloc异常throw std::bad_alloc();return p;
}例如:当我们需要分配512个整型数据时
int *p allocatorint().allocate(512,(int *)0);
allocatorint().deallocate(p,512);在 VC6 / BC / G中allocator 类都是使用 operator new 来分配内存并使用 operator delete 来释放内存。其中operator new() 通常通过调用 malloc() 实现开辟内存operator delete() 通常通过调用 free() 实现回收内存
// VC6 STL中容器对allocator的使用
templateclass _Ty, class _Aallocator_Ty // 调用allocator类
class vector
{ ...
};template typename T
class allocator {
public:typedef size_t size_type; // size_t是一个无符合整型数据类型typedef ptrdiff_t difference_type; // 表示同一个数组中任意两个元素之间的差异typedef T* pointer;typedef T value_type;pointer allocate(size_type n, const void* hint 0) {return (pointer) (::operator new(n * sizeof(value_type)));}void deallocate(pointer p, size_type n) {::operator delete(p);}
}在GCC2.9中
// VC6 STL中容器对allocator的使用
templateclass T, class Alloc alloc // 调用allocator类
class vector
{ ...
};①内存池由一系列内存块组成每块预分配一定数量的内存。
②自由列表每个固定大小的内存块都有自己的自由列表。
③大小分类根据内存请求的大小被分类到不同的自由列表。 GCC4.9所附的标准库其中**__pool_alloc就是GCC2.9中的alloc** // 使用方法
vectorstring, __gnn_cxx::__pool_allocstring vec;5.容器的分类 6.容器list
G2.9版本
template class T, class Alloc alloc
class list{
protected:typeof __list_nodeT list_node; // 1号代码块
public:typeof list_node* link_type;typeof __list_iteratorT,T,T* iterator; // 2号代码块
protected:link_type node;
}// 1号代码块
template class T
struct __list_node {void* prev;void* next;T data;
};// 2号代码块
template class T,class Ref,class Ptr
struct __list_iterator{typedef bidirectional_iterator_tag iterator_category; // (1)typedef T value_type; // (2)typedef Ptr pointer; // (3)typedef Ref reference; // (4)typedef ptrdiff_t difference_type; // (5)typedef __list_nodeT list_node;typedef list_node* list_type;typedef __list_iteratorT,Ref,Ptr self;link_type node;reference operator*() const{ return (*node).data; } // 返回引用pointer operator-() const{ return (operator *());} // 返回指针。获得该对象的内存地址即一个指向该对象的指针self operator() // i{ node (link_type) ((*node).next); return *this; // 返回自身的引用}// (*node).next是一个 __list_nodeT* 类型的值加上(list_type)是显式类型转换// (*node).next 等价于 node-next 等价于 ((*node))-next;// node只是一个迭代器的指针不是迭代器本身// self表示返回迭代器的引用self operator(int) // i{ self tmp *this; *this; return tmp;}
};前缀递增 (operator()) 将迭代器向前移动到下一个元素后缀递增 (operator(int)) 返回迭代器的一个临时副本在递增前的状态然后再递增迭代器。内置 - 操作符 用于直接从指针访问对象成员。重载的 operator-() 提供了一种方式通过迭代器对象模拟原生指针的行为允许通过迭代器间接访问对象成员。(*node).next等价于node-next 等价于 ((*node))-next
G4.9版本:
templatetypename _Tp, typename _Allocstd::allocator_Tp
class list:protected_List_base_Tp,_Alloc
{
public:typedef _List_iterator_Tp iterator;
}templatetypename _Tp, typename _Alloc std::allocator_Tp 这是一个类模板接受两个模板参数。_Tp 表示列表中要存储的数据类型。_Alloc 是分配器类型用于控制链表中元素的内存分配。这个参数有一个默认值即 std::allocator_Tp这是 C 标准库提供的一种通用内存分配器。: protected _List_base_Tp, _Alloc list 类从 _List_base 类继承而来使用保护protected继承。这意味着 _List_base 中的公共和保护成员在 list 类中将变为保护成员。_List_base 是一个实现链表基础功能的类
templatetypename _Tp
struct _List_iterator
{typedef _Tp* pointer;typedef _Tp reference;...
};// 自身类型的指针使得可以从任何一个节点开始
// 沿着链表向前或向后移动这对于双向遍历和双向操作非常重要。
struct _List_node_base
{_List_node_base* _M_next;_List_node_base* _M_prev;
};templatetypename _Tp
struct _List_node:public _List_node_base
{_Tp _M_data;
};7.Iterator必须提供5中associated types
算法提问
templatetypename T
incline void
algorithm(T first, T last) // 迭代器
{...T::iterator_categoryT::value_typeT::pointerT::referenceT::difference_type...
};迭代器回答
template class T,class Ref,class Ptr
struct __list_iterator{typedef bidirectional_iterator_tag iterator_category; // (1)typedef T value_type; // (2)typedef Ptr pointer; // (3)typedef Ref reference; // (4)typedef ptrdiff_t difference_type; // (5)...
};8. iterator_traits 类型萃取
但当我们向算法中传入的是指针而不是迭代器时就需要用到traits。也就是说iterator_traits 为所有类型的迭代器包括原生指针提供统一的方式来访问迭代器的属性是在 iterator 头文件中定义的。
作用
std::iterator_traits 模板用于提取迭代器相关的类型信息。
举例:
#includeiostream
#includeiterator
#includevectortemplatetypename Iterator
void print_vector(Iterator first, Iterator last)
{// using关键字用来定义类型的别名// typename关键字告诉编译器这是一个依赖于模版参数Iterator的类型而不是变量using ValueType typename iterator_traitsIterator::value_type;
}int main()
{vectorint v {1,2,3,4,5};print_vector(v.begin(), v.end());
}// 当Iterator是一个类时
templateclass Iterator
struct iterator_traits
{typedef typename Iterator::value_type value_type;
};// 两种偏特化情况
// 当Iterator是一个普通指针时
// 如int*,那么T为int得到value_type就被定义为“int”
templateclass T
struct iterator_traitsT*
{typedef T value_type;
};// 当Iterator是一个常量指针指针的指向可以修改指针指向的值不能修改)
templateclass T
struct iterator_traitsconst T*
{typedef T value_type;
};Iterator若是int*ValueType 就是 intIterator若是const int*ValueType 还是 int因为如果 ValueType 是 const int后续再使用ValueType创建其他容器时就会受到限制。因为标准库中的容器如 std::vector不能存储常量类型的元素,它们需要能被赋值和移动。
完整的iterator_traits:
templateclass Iterator
struct iterator_traits
{typedef typename Iterator::iterator_category iterator_category;typedef typename Iterator::value_type value_type;typedef typename Iterator::pointer iterator_category;typedef typename Iterator::reference reference;typedef typename Iterator::difference_type difference_type;
};templateclass T
struct iterator_traitsT*
{typedef random_access_iterator_tag iterator_category;typedef T value_type;typedef ptrdiff_t difference_type;typedef T* pointer;typedef T reference;
};templateclass T
struct iterator_traitsconst T*
{typedef random_access_iterator_tag iterator_category;typedef T value_type;typedef ptrdiff_t difference_type;typedef const T* pointer;typedef const T reference;
};
9.容器vector
定义
template class T, class Alloc std::allocatorT
class vector
{
public:typedef T value_type;typedef T* pointer;typedef T reference;typedef size_t size_type;
protected:iterator **start**;iterator **finish**;iterator **end_of_range**;Allocator alloc;
public:iterator begin() { return **start**;}iterator end() { return **finish**;}size_type size const { return size_type(end() - start());}size_type capacity() const{ return size_type(**end_of_storage** - begin());}bool empty() const { return begin() end();}reference operator[](size_type n}{return *(begin()n);referebce front() {return *begin();}reference back() {return *(end()-1);}
};push_back操作源码
template class T, class Allocstd::allocatorT
void push_back(const T value)
{if(finish end_of_storage) // 原始空间不足{size_type old_size size();// old_size 0:当前vector中没有任何元素新分配的存储空间至少有一个元素的容量// old_size ! 0:分配新的容量将是当前大小的两倍, 称为指数增长size_type new_capacity old_size 0 ? 1 : 2 * old_size;iterator new_start alloc.allocator(new_capacity);iterator new_finsih new_start;try{// 将原数据移动到新空间for(iterator old_iter start; old_iter ! finish; ){alloc.construct(new_finish, *old_iter);alloc.destroy(old_iter);}// 添加新元素alloc.construct(new_finish, value);}catch(...){// 如果构造失败释放已分配的内存for(iterator itnew_start; it!new_finish; it){alloc.destory(it);}alloc.deallocate(new_start, new_capacity);throw; // 重新抛出当前异常}// 释放旧空间if (start) {alloc.deallocate(start, end_of_storage - start);}// 更新指针start new_start;finish new_finish;end_of_storage start new_capacity;} else {alloc.construct(finish, value); // 有足够空间直接构造新元素}
}vector的迭代器iterator
template class T, class Alloc alloc
class vector
{
public:typedef T value_type;typedef T* iterator;
};// 调用方法
vectotint v;
vectorint::iterator it v.begin();10.容器deque // BufSize是指缓冲区buffer的长度
templateclass T,class Alloc alloc, size_t BufSize0
class deque
{
public:typedef T value_type;typedef size_t size_type;typedef __deque_iteratorT,T,T*,BufSiz iterator;
protected:typedef T** map_pointer; // 指向指针数组的指针
protected:iterator start;iterator finish;map_point map; // 指向指针数组的指针每一个都指向一个缓冲区size_type map_size;
public:iterator begin() {return start;}iterator end() {return finish;}size_type size() {return finish - start;}...
};deque的迭代器iterator
templateclass T, class Ref, class Ptr, size_t BufSize
struct __deque_iterator
{typedef random_access_iterator_tag iterator_category;typedef T value_type;typedef Ref reference; // Ttypedef Ptr pointer; // T*typedef size_t size_type;typedef ptrdiff_t difference_type;typedef T** map_pointer;typedef __deque_iteratorT,Ref,Ptr,BufSiz self;T* **cur**;T* **first**;T* **last**;map_point **node**;
};
