工作两年了，还只会用sort进行排序？
算法
条款27：确保目标区间足够大
//思考这样一个问题：stl容器被添加时（insert, push_front,push_back）自动扩展它们自己来容纳新对象，是不是就不必担心要为容器的对象腾出空间了？
//transform：https://blog.csdn.net/lanzhihui_10086/article/details/42342893 //1，四个参数，源区间的元素转换到目标区间，复制和修改一起做 //2，五个参数，将前两个原序列中的元素合并，并将结果写入目标区间
//看例子1
int transmogrify(int x)
{
//这个函数从x产生一些新值
return x * x;
}
//例子1
std::vector<int> values = {1,2,3};
std::vector<int> results;
//把transmogrify应用于values中的每个对象, 把返回的values附加到 results
// transform(values.begin(),values.end(),results.end(),transmogrify);
/**
产生问题：transform把transmogrify应用于 values[0]并把结果赋给 *result.end(),同理把 values[1]的结果
放入 *(results.end() + 1), 但是 *results.end()没有对象，调用transform是错误的，因为它会给不存在的对象赋值
可以编译，但是运行肯定是段错误
如何修改正确？见 1-1
*/
//1-1
//transform的结果放入叫做 results容器的结尾的方式是调用 back_inserter来产生指定目标区间起点的迭代器
transform(values.begin(),values.end(),back_inserter(results),transmogrify);
for(auto i:results)
{
std::cout<<"1-1: "<<i<<std::endl;
}
/**
1, back_inserter返回的迭代器会调用push_back，因此可以在任何提供puah_back的容器上使用 back_inserter（vector,string,deque,list）
2, front_inserter，让一个算法在容器的前段插入东西，利用 push_front，只有 deque和list，注意会是反序插入， 见1-2
*/
//1-2
std::list<int> listresults;
transform(values.begin(),values.end(),front_inserter(listresults),transmogrify);
for(auto i:listresults)
{
std::cout<<"1-2: "<<i<<std::endl;
}
/**
1，fornt_inserter利用push_front添加每个result， 结果对象会和 values中对应的对象顺序相反，如何保证顺序相同，那就以相反的顺序迭代values，见1-3
2， vector不提供push_front，不用利用 front_inserter
*/
//1-3
std::list<int> listresults_;
transform(values.rbegin(),values.rend(),front_inserter(listresults_),transmogrify);
for(auto i:listresults_)
{
std::cout<<"1-3: "<<i<<std::endl;
}
//总结 /** 1，front_inserter让你强制算法在容器前段插入它们的结果 2，back_inserter把结果放在容器后端 3，inserter可以把结果放在容器的任意位置，见 1-4 */
//1-4
std::vector<int> results_;
//前面条款讲到可以调用reserve，要承受每次发生插入时移到元素的开销，但是避免了重新分配容器内存
results_.reserve(results_.size() + values.size());//确定results至少还能装得下 values.size()个元素
//把结果放在中间
transform(values.begin(),values.end(),inserter(results_,results_.begin() + results_.size() /2),transmogrify);
for(auto i:results_)
{
std::cout<<"1-4: "<<i<<std::endl;
}
//再思考这样一个问题：假设你让 transform覆盖results的元素，如果results至少有和values一样多的元素，那很简单，如果没有，必须使用resize来确保 //见2
//2
std::vector<int> results_1;
if(results_1.size() < values.size())
{
//确保results至少和values一样大
results.resize(values.size());
}
transform(values.begin(),values.end(),results_1.begin(),transmogrify);
//或者你可以清空 results然后用通常的方式插入
results_1.clear();
results_1.reserve(values.size())//保留足够空间
transform(values.begin(),values.end(),pack_inserter(results_1),transmogrify);
// 无论何时你使用一个要求指定目的区间的算法，确保目的区间已经足够大或者在算法执行时可以增加大小。 // 如果你选择增加大小，就使用插入迭代器，比如ostream_iterators或从back_inserter、front_inserter或inserter返回的迭代器
条款28：了解你的排序选择
//思考这样一个问题：想到排序算法，脑海中只有一个 sort ，最多有个 qsort //qsort：https://www.cnblogs.com/CCBB/archive/2010/01/15/1648827.html //对任意类型的一维数组进行排序，快速排序算法，相比sort较慢 //问题1：部分排序 partial_sort ：http://c.biancheng.net/view/7469.html //假设一个Widget的vector，选择20个质量最高的Widget发送给你最忠实的客户，需要做的只是排序以鉴别出20个最好的Widget，剩下的可以保持无序 //见 1
class Widget{
public:
Widget(int v):value(v){}
Widget(){}
void Init(int v)
{
this->value =v;
}
int value;
};
bool qualityCompare(const Widget& lhs, const Widget& rhs)
{
return lhs.value > rhs.value;
}
//见1
//1
std::vector<Widget> widgets;
widgets.resize(40);
for (size_t i = 0; i < widgets.size(); i++)
{
widgets[i].Init(i);
}
//把最好的20个元素按顺序放在 widgets的前端
partial_sort(widgets.begin(), widgets.begin() + 20, widgets.end(),qualityCompare);
for (size_t i = 0; i < 20; i++)
{
std::cout<<"1: "<<widgets[i].value<<std::endl;
}
/**
质量最高的是 widgets[0],其次是widgets[1]，如果你不关系这个最好的20个元素的顺序，只是挑出20个最好的，这就是多余的工作了
使用 nth_element， 见 2
*/
//2 //nth_element：http://c.biancheng.net/view/7476.html //该函数可以从某个序列中找到第 n 小的元素 K，并将 K 移动到序列中第 n 的位置处。 //不仅如此，整个序列经过 nth_element() 函数处理后，所有位于 K 之前的元素都比 K 小，所有位于 K 之后的元素都比 K 大。
nth_element(widgets.begin(),widgets.begin() + 19,widgets.end(),qualityCompare);
for (size_t i = 0; i < 20; i++)
{
std::cout<<"2: "<<widgets[i].value<<std::endl;
}
/**
前20个最好的元素是无序的，但是会遇到，比如有多个相等值得元素，这个时候会怎么办呢？比如 12个质量是1级，15个元素质量是2级， 需要 12+8
怎么判断15个中得哪些要放到最好得20个中去呢？多个元素有等价得值怎么排序？
利用稳定排序算法 stable_sort 见 3
*/
//3 //stable_sort: http://c.biancheng.net/view/7460.html //功能上实现排序以后，还保证了排序后得相对位置不变
stable_sort(widgets.begin(),widgets.end(),qualityCompare);
for (size_t i = 0; i < 20; i++)
{
std::cout<<"3: "<<widgets[i].value<<std::endl;
}
//4，再次谈谈 nth_element
//除了能找到区间顶部得 n个元素，还可以找到区间得中值或者找到在指定百分点得元素
std::vector<Widget>::iterator begin(widgets.begin());
std::vector<Widget>::iterator end(widgets.end());//方便表示widgets得起点和终点
//这个迭代器指示了要找得中等质量得Widget得位置
std::vector<Widget>::iterator goalPosition;
goalPosition = begin + widgets.size() /2;//在有序得vector得中间
nth_element(begin,goalPosition,end,qualityCompare);//goalPosition得值现在是中等质量得值
std::cout<<"4: "<<(*goalPosition).value<<std::endl;
//4-1
//找到质量等级为 75%得Widget
std::vector<Widget>::size_type goalOffset = 0.25* widgets.size();
nth_element(begin,begin +goalOffset,end,qualityCompare);
//begin + goalOffset现在指向 质量等级为75%的Widget
/再者：问题 //假设你不需要鉴别出20个质量最高得Widget，取而代之，你需要鉴别出所有质量等级为1或2得 //完全排序肯定可以，找到第一个质量等级比2差得，找到了质量差得区间起点 //一个更好得策略是使用 partition算法，重排区间中得元素以所有满足某个标准得元素都在区间得开头 //移动所有等级为2或更好得Widget到widgets得前端,并且返回一个指向第一个不满足widget得迭代器 //见5 //partition: http://c.biancheng.net/view/7513.html //根据用户自定义的筛选规则，重新排列指定区域内存储的数据，使其分为 2 组，第一组为符合筛选条件的数据，另一组为不符合筛选条件的数据
//5
bool hasAcceptableQuality(const Widget& w)
{
return w.value > 20;
}
std::vector<Widget>::iterator goodEnd = partition(widgets.begin(),widgets.end(),hasAcceptableQuality);
std::cout<<"5: "<<(*goodEnd).value<<std::endl;
/**
从widgets.begin()到goodEnd的区间容纳了所有质量是1或2的Widget，从goodEnd到widgets.end
()的区间包含了所有质量等级更低的Widget。如果在分割时保持同样质量等级的Widget的相对位置很重要，
我们自然会用stable_partition来代替partition
*/
//总结： /** 1, 算法sort、stable_sort、partial_sort和nth_element需要随机访问迭代器，所以它们可能只能用于vector、string、 deque和数组，唯一我们可能会但不能使用sort、stable_sort、partial_sort或nth_element的容器是list，list通过提供sort成 员函数做了一些补偿 2, partition和stable_partition与sort、stable_sort、partial_sort和nth_element不同，它们只需要双向迭代器。因此你可 以在任何标准序列迭代器上使用partition和stable_partition。 ● 如果你需要在vector、string、deque或数组上进行完全排序，你可以使用sort或stable_sort。 ● 如果你有一个vector、string、deque或数组，你只需要排序前n个元素，应该用partial_sort。 ● 如果你有一个vector、string、deque或数组，你需要鉴别出第n个元素或你需要鉴别出最前的n个元素， 而不用知道它们的顺序，nth_element是你应该注意和调用的。 ● 如果你需要把标准序列容器的元素或数组分隔为满足和不满足某个标准，你大概就要找partition或 stable_partition。 ● 如果你的数据是在list中，你可以直接使用partition和stable_partition，你可以使用list的sort来代替sort和 stable_sort。如果你需要partial_sort或nth_element提供的效果，你就必须间接完成这个任务，但正如我 在上面勾画的，会有很多选择 */
条款29：remove做不到删除元素
//先看一下 remove得声明
template<class ForwardIterator,class T>
ForwardIterator remove(ForwardIterator first,ForwardIterator last,const T& value);
/**
1， remove接收指定它操作的元素区间的一对迭代器。它不接收一个容器，所以remove不知道它作用于哪个容器。
此外，remove也不可能发现容器，因为没有办法从一个迭代器获取对应于它的容器。
2，因为remove无法知道它正在操作的容器，所以remove不可能从一个容器中除去元素。
这解释了另一个令人沮丧的观点——从一个容器中remove元素不会改变容器中元素的个数
见 1
*/
//1
std::vector<int> v;
v.reserve(10);
for(int i=1; i <= 10; ++i){
v.push_back(i);
}
std::cout<<"1: "<<v.size()<<std::endl;
v[3]=v[5]=v[9]=99;
std::remove(v.begin(),v.end(),99);//删除所有等于99得元素
std::cout<<"1: "<<v.size()<<std::endl;//依然是10
//remove并不“真的”删除东西，因为它做不到。
/** 那 remove 做了什么呢？ remove移动指定区间中的元素直到所有“不删除的”元素在区间的开头（相对位置和原来它们的一样）。 它返回一个指向最后一个的下一个“不删除的”元素的迭代器。返回值是区间的“新逻辑终点”。 */
/**
如果你真的要删除东西的话，你应该在remove后面接上erase。
*/
v.erase(std::remove(v.begin(),v.end(),99));//删除所有等于99得元素
std::cout<<"1: "<<v.size()<<std::endl;//9
for(auto i:v)
{
std::cout<<"1: "<<i<<std::endl;
}
条款30：提防在指针得容器使用类似remove得算法
//管理一堆动态分配的Widgets, 见1
class Widget{
public:
bool isCertified() const{
return false;
}
};
//1
std::vector<Widget*> v;
v.push_back(new Widget);
//除去未通过检验的Widet
v.erase(remove_if(v.begin(),v.end(), std::not1(std::mem_fun(&Widget::isCertified))), v.end());
//没有什么指向两个未通过检验的Widget，它们也没有被删除，它们的内存和其他资源泄漏了
//你无法避免在那样的容器上使用remove，排除这个问题一种方法是在应用erase-remove惯用法之前先删除 指针并设置它们为空，然后除去容器中的所有空指针 //见 2
//2
//把所有指向未通过检验Widget的指针删除并且设置为空
for_each(v.begin(), v.end(),delAndNullifyUncertified);
//从v中去除空指针，0必须映射到一个指针，让C++可以推出第三个参数的类型
v.erase(remove(v.begin(),v.end(),static_cast<Widget*>(0)), v.end());
//改进：用智能指针可以接触以上问题
条款31：实现简单忽略大小写字符串比较
//我怎么使用STL来进行忽略大小写的字符串比较
//实现1
int ciCharCompare(char c1,char c2)
{
int lc1 = tolower(static_cast<unsigned char>(c1));
int lc2 = tolower(static_cast<unsigned char>(c2));
if(lc1 < lc2) return -1;
if(lc1 > lc2) return 1;
return 0;
}
//遵循strcmp，比较前转成了小写
//实现2
//基于mismatch算法，因为mismatch确定了两个区间中第一个对应的不相同的值的位置
//调用mismatch之前，我们必须先满足它的前提。特别是，我们必须确定一个字符串是否比另一个短，短的字符串作为第一个区间传递
//mismatch: https://vimsky.com/examples/usage/stdmismatch-examples-c.html
//std::not2: https://blog.csdn.net/sinat_31608641/article/details/112915561
//https://changlu.blog.csdn.net/article/details/104297666
int ciStringCompareImpl(const std::string& s1,const std::string& s2)
{
typedef std::pair<std::string::const_iterator, std::string::const_iterator> PSCI;
PSCI p = std::mismatch(s1.begin(), s1.end(), s2.begin(), std::not2(std::ptr_fun(ciCharCompare)));
if (p.first == s1.end())
{
if(p.second == s2.end()) //s1 == s2
{
return 0;
}
else //s1 比 s2 短
{
return -1;
}
}
return ciCharCompare(*p.first,*p.second);//两个字符串的关系和不匹配的字符一样
}
int ciStringCompare(const std::string& s1,const std::string& s2)
{
if(s1.size() <= s2.size())
{
return ciStringCompareImpl(s1,s2);
}
else
{
return -ciStringCompareImpl(s2,s1);
}
}
/** 1, 一旦你知道了字符串中第一个不同字符的位置，就可以很容易决定哪个字符串, 如果有的话，在另一个前面。 2, 唯一可能感到奇怪的是传给mismatch的判断式，也就是not2(ptr_fun(ciCharCompare))。 2,1 当字符匹配时这个判断式返回true，因为当判断式返回false时mismatch会停止。 2,2 我们不能为此使用ciCharCompare，因为它返回-1、1或0，而当字符匹配时它返回0，就像strcmp。 2,3 如果我们把ciCharCompare作为判断式传给mismatch，C++会把ciCharCompare的返回类型转换为bool，而当然bool中 零的等价物是false，正好和我们想要的相反！ 2,4 同样的，当ciCharCompare返回1或-1，那会被解释成true，因为，就像C，所有非零整数值都看作true */
//实现3
//lexicographical_compare：
bool ciCharLess(char c1,char c2)
{
return tolower(static_cast<unsigned char>(c1)) < tolower(static_cast<unsigned char>(c2));
}
bool ciStringCompare2(const std::string& s1, const std::string& s2)
{
return lexicographical_compare(s1.begin(),s1.end(),s2.begin(),s2.end(),ciCharLess);
//return stricmp(s1.c_str(),s2.c_str());
}
/** 1, exicographical_compare是strcmp的泛型版本。strcmp只对字符数组起作用，但lexicographical_compare对所有任何类型的值的区间都起作用 2, strcmp总是比较两个字符来看看它们的关系是相等、小于或大于另一个。lexicographical_compare可以传入一个决定两个值是否满足一个用户定义标准的二元判断式。 3, lexicographical_compare用来寻找s1和s2第一个不同的位置，基于调用ciCharLess的结果 3,1 如果，使用那个位置的字符，ciCharLess返回true，lexicographical_compare也是； 3,2 如果，在第一个字符不同的位置，从第一个字符串来的字符先于对应的来自第二个字符串的字符，第一个字符串就先于第二个 3,3 就像strcmp，lexicographical_compare认为两个相等值的区间是相等的，因此它对于这样的两个区间返回false：第一个区间不在第二个之前。 3，4 也像strcmp，如果第一个区间在发现不同的对应值之前就结束了，lexicographical_compare返回true：一个先于任何区间的前缀是一个前缀 */
int main()
{
//1
std::cout<<"1: "<<ciCharCompare('lyy','Lxk')<<std::endl;
//2
std::cout<<"2: "<<ciStringCompare("lyy","Lxk")<<std::endl;
//3
std::cout<<"3: "<<ciStringCompare2("lyy","Lxk")<<std::endl;
}
条款32：用accumlate或for_each来统计区间
//有时候你需要把整个区间提炼成一个单独的数，或，更一般地，一个单独的对象
/** 1, count告诉你区间中有多少等于某个值的元素，而count_if告诉你有多少元素满足一个判断式。 2， 区间中的最小和最大值可以通过min_element和max_element获得 3，你需要统计一个区间，但你需要有定义你需要统计的东西的能力 accumulate 4，那三个其它的算法是inner_product、adjacent_difference和partial_sum //https://www.jianshu.com/p/cfc6d38bccba adjacent_difference 差分数组 //https://vimsky.com/examples/usage/std-inner_product-in-cpp.html inner_product 内积 //https://cloud.tencent.com/developer/section/1009828 partial_sum 子范围元素的部分和 */
//实例1 //带有一对迭代器和初始值的形式可以返回初始值加由迭代器划分出的区间中值的和 //见 1
//1
std::list<double> ld = {1,2,3,4,5};
double sum = accumulate(ld.begin(),ld.end(),0.0);
std::cout<<"1: "<<sum<<std::endl;
//实例2 //accumulate只需要输入迭代器，所以你甚至可以使用istream_iterator和istreambuf_iterator //见 2
//2
std::cout<< "The sum of the ints on the standard input is" // 打印cin中
<< std::accumulate(std::istream_iterator<int>(std::cin), // 那些int的和
std::istream_iterator<int>(),
0);
//实例3 //accumulate的另一种形式，带有一个初始和值与一个任意的统计函数，这变得一般很多 //考虑怎么使用accumulate来计算容器中的字符串的长度和 //见3
std::string::size_type stringLengthSum(std::string::size_type sumSoFar, const std::string& s)
{
return sumSoFar + s.size();
}
//3
std::set<std::string> ss = {"ly","lxk"};
std::string::size_type lengthSum = accumulate(ss.begin(),ss.end(),0,stringLengthSum);
std::cout<<"3: "<<lengthSum<<std::endl;
//4
//计算区间的积
float product = accumulate(ld.begin(),ld.end(),1.0f,std::multiplies<float>());
std::cout<<"4: "<<product<<std::endl;
//实例5 //寻找point的区间平均值
struct Point{
Point(double initX,double initY):x(initX),y(initY){}
double x,y;
};
class PointAverage:public std::binary_function<Point,Point,Point>{
public:
PointAverage():numPoints(0),xSum(0),ySum(0){}
const Point operator()(const Point& avgSoFar, const Point& p){
++numPoints;
xSum += p.x;
ySum += p.y;
return Point(xSum/numPoints,ySum/numPoints);
}
private:
size_t numPoints;
double xSum;
double ySum;
};
//5
std::list<Point> lp = {Point(1,2),Point(3,4)};
Point avg =accumulate(lp.begin(),lp.end(),Point(0,0),PointAverage());
std::cout<<"5: "<<avg.x<<" "<<avg.y<<std::endl;
//那就是禁止传给accumulate的函数中有副作用。成员变量numPoints、xSum和ySum的修改造成了一个副作用
//实例6 //for_each: https://blog.csdn.net/u014613043/article/details/50619254 //https://blog.csdn.net/qq_43755653/article/details/103098006 /** 1, for_each带有一个区间和一个函数（一般是一个函数对象）来调用区间中的每个元素， 但传给for_each的函数只接收一个实参（当前的区间元素），而且当完成时for_each返回它的函数 2, for_each听起来好像你只是要对区间的每个元素进行一些操作，而且，当然，那是那个算法 的主要应用。用for_each来统计一个区间是合法的，但是它没有accumulate清楚 3，accumulate直接返回那些我们想要的统计值，而for_each返回一个函数对象，我们必须从这个对象中提 取想要的统计信息。在C++里，那意味着我们必须给仿函数类添加一个成员函数，让我们找回我们追求的统 计信息 */
class PointAverage1:public std::unary_function<Point, void> {
public:
PointAverage1(): xSum(0), ySum(0), numPoints(0) {}
void operator()(const Point& p)
{
++numPoints;
xSum += p.x;
ySum += p.y;
}
Point result() const
{
return Point(xSum/numPoints, ySum/numPoints);
}
private:
size_t numPoints;
double xSum;
double ySum;
};
//6
PointAverage1 pp = for_each(lp.begin(), lp.end(), PointAverage1());
Point avg_ = pp.result();
std::cout<<"6: "<<avg_.x<<" "<<avg_.y<<std::endl;