###《Effective STL》--Chapter5

时间:2023-03-08 16:18:16

点击查看Evernote原文

#@author:       gr
#@date: 2014-09-17
#@email: forgerui@gmail.com

Chapter5 算法

Topic 30: 确保目标区间足够大

  如果所使用的算法需要指定一个目标区间,那么必须确保目标区间足够大,或者保证它会随着算法的运行而增大。可以使用back_inserterfront_inerter或者inserter返回的迭代器。

transform(values.begin(), values.end(), back_inserter(results), transmogrify);

Topic 31: 了解各种与排序有关的选择

  根据不同的需求选择不同的排序函数。稳定排序一般比不稳定排序开销更大。

  

  vector,string,deque或者数组执行一次完全排序,可以使用sortstable_sort。如果对前n个元素进行排序,可以使用partial_sort。如果只需找到前n个元素,而不需要对这n个元素进行排序,则使用nth_element

  

  如果将一个标准序列容器中的元素按照是否满足某个特定的条件区分开来,那么partitionstable_partition可能正是你所需要的。

  

  如果数据在一个list中,仍然可以使用partitionstable_partition算法,其它的方法对于list不适应。但可以使用list::sort取代sortstable_sort算法。如果需要partial_sortnth_element的效果,可以通过间接的方法实现。

  

Topic 32: 如果确实需要删除元素,则在remove之后调用erase

  删除容器中一些元素,remove是将相关的元素移到容器的最后,将.end()前移,并没有真正删除元素。需要再次调用erase删除元素。

  

  listremove函数实际上已经默认调用了erase了,所以不需要再次调用。

  

  map没有提供remove函数,使用erase删除。

  

Topic 33: 对包含指针的容器使用remove函数时要特别小心

使用remove时,指针会指向其他地方,这样有些内存就会无法访问,而造成内存泄漏。

方法一是在使用erase-remove之前,将要删除的元素的指针删除并置为空,然后再用erase-remove清除容器中所有的空指针。

方法二是使用智能指针shared_ptr,让系统进行管理。

Topic 34: 了解哪些算法要求使用排序的区间作为参数

需要排序区间的STL算法:

binary_search, lower_bound, upper_bound, equal_range, mergeincludes, set_intersection, set_union, set_difference

排序算法一般使用等价来进行排序,uniqueunique_copy使用相等来判断两个对象是否相同。

Topic 36: 理解copy_if算法的正确实现

  STL中没有提供copy_if的实现,需要自己实现。它的调用形式应该是下面这样的:

//判断Widget是否有损坏
bool isDefective(const Widget& w);
//调用copy_if形式
copy_if(c.begin(), c.end(), ostream_iterator<Widget>(cerr, "\n"), isDefective);
//copy_if的实现
OutputIterator copy_if(InputIterator begin, InputIterator end, OutputIterator destBegin, Predicate p){
while(begin != end){
if (p(*begin))
*destBegin++ = *begin;
++begin;
}
return destBegin;
}

Topic 37: 使用accumulate或者for_each进行区间统计

  accumulatefor_each都可以进行区间统计。可以传递一个函数对象,对每个元素都调用这个函数对象,实现区间统计。实际上从命令上也可以看出,accumulate更偏重于区间统计,而for_each是对每区间的每一个元素做一个操作,当然也可以用来统计信息。

  此外,accumulate可以直接返回统计结果,而for_each返回的是一个对象,需要从这个对象中提取统计信息,即在函数中加入一个成员函数,以获得想要的统计信息。

// 容器迭代器调用
accumulate(v.begin(), v.end(), 0.0);
accumulate(istream_iterator<int>(cin), istream_iterator<int>(), 0.0);
// 调用函数
accumulate(ss.begin(), ss.end(), 0, stringLengthSum);
// PointAveraget是一个函数子类,包含operator=(const Point&)和result()成员函数
for_each(lp.begin(), lp.end(), PointAverage()).result();