STL算法之copy
copy
使用必须包含头文件<algorithm>
由于copy进行的是复制操作,而复制操作不外乎assignment operator和copy constructor(copy算法用的是前者),但是某些元素型别用于的是trivial assginment operator,因此,如果能够使用内存直接复制行为(例如C标准函数memmove或memcpy),变能够节省大量时间。为此,SGI STL的copy算法用尽各种办法,包括函数重载、性别特性、偏特化等编程技巧,无所不用其极地加强效率。如下图所示:
copy算法是一一进行元素的复制操作,如果输出区间的起点位于输入区间内,copy算法便(可能)会在输入区间的(某些)元素尚未被复制之前,就覆盖其值,导致错误结果。我们使用”可能”这个字眼,是因为如果copy算法根据其所接收的迭代器的特性决定调用memmove()来执行任务,就不会造成上述错误,因为memmove()会先将整个输入区间的内容复制下来,没有被覆盖的危险。
以下是copy的实现代码:
// copy 函数运用function overloading, type traits,partial
// specialization, 无所不用其极的改善效率
//copy有一个全特化和两个偏特化版本
template<class InputIterator, class OutputIterator>
inlineOutputIterator copy(InputIterator first, InputIterator last,
OutputIteratorresult)
{
return__copy_dispatch<InputIterator,OutputIterator>()(first, last, result);
}
inline char* copy(const char* first, const char* last, char*result) {
memmove(result, first, last - first);
return result + (last - first);
}
inline wchar_t* copy(const wchar_t* first, constwchar_t* last,
wchar_t*result) {
memmove(result, first, sizeof(wchar_t) * (last - first));
return result + (last - first);
}
//__copy_dispatch有一个完全泛华版本和两个偏特化版本
template<class InputIterator, class OutputIterator>
struct__copy_dispatch
{
OutputIterator operator()(InputIteratorfirst, InputIterator last,
OutputIterator result) {
return __copy(first, last, result,iterator_category(first));
}
};
template<class T>
struct__copy_dispatch<T*, T*>
{
T* operator()(T* first, T* last, T*result) {
typedef typename__type_traits<T>::has_trivial_assignment_operator t;
return __copy_t(first, last, result,t());
}
};
template<class T>
struct__copy_dispatch<const T*, T*>
{
T* operator()(constT* first, const T* last, T* result) {
typedef typename__type_traits<T>::has_trivial_assignment_operator t;
return __copy_t(first, last, result,t());
}
};
//__copy有两个版本,一个用于对输入参数类型为InputIterator迭代器设计,
//另一个对输入参数类型为RandomAccessIterator迭代器设计
template<class InputIterator, class OutputIterator>
inlineOutputIterator __copy(InputIterator first, InputIterator last,
OutputIteratorresult, input_iterator_tag)
{
for ( ; first != last; ++result, ++first)
*result = *first;
return result;
}
template<class RandomAccessIterator, class OutputIterator>
inlineOutputIterator
__copy(RandomAccessIterator first,RandomAccessIterator last,
OutputIterator result, random_access_iterator_tag)
{
return __copy_d(first, last, result,distance_type(first));
}
//__copy_d()是对输入参数为RandomAccessIterator的实现
template<class T>
struct__copy_dispatch<const T*, T*>
{
T* operator()(constT* first, const T* last, T* result) {
typedef typename__type_traits<T>::has_trivial_assignment_operator t;
return __copy_t(first, last, result,t());
}
};
//__copy_t()有两个版本,分别对应指针所指向对象具备trival assignmentoperator
//和non-trival assignment operator
template<class T>
inlineT* __copy_t(const T* first, const T* last, T* result, __true_type) {
memmove(result, first, sizeof(T) * (last- first));
return result + (last - first);
}
template<class T>
inlineT* __copy_t(const T* first, const T* last, T* result, __false_type) {
return __copy_d(first, last, result, (ptrdiff_t*) 0);
}
copy_backward()以逆行方向复制,实现技巧与copy相似。
分享到:
相关推荐
STL将算法库分成4组: 1)非修改式序列操作,find()、for_each()等; 2)修改式序列操作,transform()、random_shuffle()、copy等; 3)排序和相关操作,sort()等; 4)通用数字运算。 ........
在STL的泛型算法中有4类基本的算法: 1)变序型队列算法: 可以改变容器内的数据; 2)非变序型队列算法:处理容器内的数据而不改变他们; 3)排序值算法:包涵对容器中的值进行排序和合并的算法,还有二叉搜索算法 ,4)...
第四篇 C++ STL算法技术 第21章 非变易算法 284 21.1 逐个容器元素for_each 284 21.2 查找容器元素find 285 21.3 条件查找容器元素find_if 286 21.4 邻近查找容器元素adjacent_find 287 21.5 范围查找...
条款36:了解copy_if的正确实现 条款37:用accumulate或for_each来统计区间 仿函数、仿函数类、函数等 条款38:把仿函数类设计为用于值传递 条款39:用纯函数做判断式 条款40:使仿函数类可适配 条款41:了解...
STL(Standard TemplateLibrary),即标准模板库,从根本上说,STL是一些“容器”的集合,这些...算法(Algorithms):各种常用算法,如Sort,Search,Copy,Erase,从实现的角度来看,STL算法是一种Function Templat
6.1.5 stl算法的一般形式 292 6.2 算法的泛化过程 294 6.3 数值算法 [stl_numeric.h] 298 6.3.1 运用实例 298 6.3.2 accumulate 299 6.3.3 adjacent_difference 300 6.3.4 inner_product 301 6.3.5 partial_...
条款36: 用not1和remove_copy_if来表现copy_if 条款37: 用accumulate或for_each来统计序列 仿函数,仿函数类,函数等等 条款38: 把仿函数类设计成值传递的 条款39: 用纯函数做predicate 条款40: 增强仿函数类的...
6.1.5 STL算法的一般形式 292 6.2 算法的泛化过程 294 6.3 数值算法 [stl_numeric.h] 298 6.3.1 运用实例 298 6.3.2 accumulate 299 6.3.3 adjacent_difference 300 6.3.4 inner_product 301 6.3.5 partial_...
第四篇 C++ STL算法技术 第21章 非变易算法 284 21.1 逐个容器元素for_each 284 21.2 查找容器元素find 285 21.3 条件查找容器元素find_if 286 21.4 邻近查找容器元素adjacent_find 287 21.5 范围查找...
提防在指针的容器上使用类似remove的算法 条款34:注意哪个算法需要有序区间 条款35:通过mismatch或lexicographical比较实现简单的忽略大小写字符串比较 条款36:了解copy_if的正确实现 条款37:用...
3. copy / copy_n /copy_backward 29 4. fill / fill_n 29 5. remove / remove_if 30 6. unique 31 7. rotate 32 8. random_shuffle 32 9. partition / stable_partition 33 10. sort / stable_sort 33 11. partial_...
条款36: 用not1和remove_copy_if来表现copy_if 条款37: 用accumulate或for_each来统计序列 仿函数,仿函数类,函数等等 条款38: 把仿函数类设计成值传递的 条款39: 用纯函数做predicate 条款40: 增强仿函数类的...
算法:各种常用的算法,如sort,find,copy,for_each等 (3).迭代器:用于连接容器和算法,,可初略理解为指针,用法相像 (4).仿函数:行为类似函数,相当于运算符重载中的operator(),协助算法完成不同的策略 (5)....
第四篇 C++ STL算法技术 第21章 非变易算法 284 21.1 逐个容器元素for_each 284 21.2 查找容器元素find 285 21.3 条件查找容器元素find_if 286 21.4 邻近查找容器元素adjacent_find 287 21.5 范围查找...
STL算法是一种 function template。 3、迭代器(iterators):扮演容器与算法之间的胶合剂,是所谓的“泛型指针”。所有STL容器都有自己的专属的迭代器。 4、仿函数(functors):行为类似函数,可以作为算法的某些...
1. 所有STL sort算法函数的名字列表: 函数名 功能描述 sort 对给定区间所有元素进行排序 stable_sort 对给定区间所有元素进行稳定排序 partial_sort 对给定区间所有元素部分排序 partial_sort_copy 对给定区间...
LightSTLLightSTL是STL的一个子集和一个超集,是我在分析STL源码后结合自己的理解进行编写的主要目的在于提高数据结构与算法和C++编程LightSTL开发进度底层配置和主要容器iterator_traits(100%)type_traits(100%)...
STL本例程提供了C++的STL常用数据结构及其算法的使用范例,为面试笔试编程题提供便利
C++ 实现的一个简单的希尔排序的示例代码,写的比较简单,VC环境下运行通过了,给大家学习使用吧,直接copy进去运行就行了
13_干活要知道在什么框架之下干活 14_结构体类型和变量定义及基本操作 15_结构体元素做函数参数pk结构指针做函数参数 16_结构体做函数基本操作 17_结构体做函数内存分配指针 18_结构中套一级指针 19_结构体中套二级...