工作两年了，还只会用sort进行排序？

//看例子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-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;
}

//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);

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
*/

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
*/

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

//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
    */

//先看一下 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后面接上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;
}

//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，它们也没有被删除，它们的内存和其他资源泄漏了

//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());

//改进：用智能指针可以接触以上问题

//实现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);
    }
}

//实现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());
}

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;
}

//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
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);

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;

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的修改造成了一个副作用

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;