C++相关闲碎记录(4)

1、remove

#include <iostream>
#include <list>
#include <algorithm>
#include <iterator>

using namespace std;

int main() {
    list<int> coll;

    for (int i = 0; i <= 6; i++) {
        coll.push_back(i);
        coll.push_front(i);
    }

    cout << "pre: ";
    copy(coll.cbegin(), coll.cend(), ostream_iterator<int>(cout, " "));
    cout << endl;

    remove(coll.begin(), coll.end(), 3);
    cout << "post: ";
    copy(coll.cbegin(), coll.cend(), ostream_iterator<int>(cout, " "));
    cout << endl;

}
输出：
pre: 6 5 4 3 2 1 0 0 1 2 3 4 5 6   
post: 6 5 4 2 1 0 0 1 2 4 5 6 5 6

remove()并没有改变集合中元素数量，cend()返回是当初那个终点，size()还是当初的大小，只是元素顺序变化。

事实上，remove方法返回一个新的终点，可以利用改终点获取新的区间、缩减后的容器长度、删除的数据个数。

#include <iostream>
#include <list>
#include <algorithm>
#include <iterator>

using namespace std;

int main() {
    list<int> coll;

    for (int i = 0; i <= 6; i++) {
        coll.push_back(i);
        coll.push_front(i);
    }

    cout << "pre: ";
    copy(coll.cbegin(), coll.cend(), ostream_iterator<int>(cout, " "));
    cout << endl;

    list<int>::iterator end = remove(coll.begin(), coll.end(), 3);
    cout << "post: ";
    copy(coll.begin(), end, ostream_iterator<int>(cout, " "));
    cout << endl;

    // 获取删除数据的个数
    cout << "number of removed elements: " << distance(end, coll.end()) << endl;

    // 移除删除掉的元素
    coll.erase(end, coll.end());

    copy(coll.cbegin(), coll.cend(), ostream_iterator<int>(cout, " "));
    cout << endl;

}
输出：
pre: 6 5 4 3 2 1 0 0 1 2 3 4 5 6 
post: 6 5 4 2 1 0 0 1 2 4 5 6 
number of removed elements: 2
6 5 4 2 1 0 0 1 2 4 5 6

利用distance返回两个迭代器的距离，如果这两个迭代器是随机访问迭代器，就可以直接使用operator - 直接计算距离，本例中的list容器不提供随机访问迭代器，所以distance就发挥了作用。

要真正的删除元素，必须使用erase操作。

2、更易Associative（关联式）和Unordered（无序）容器

更易型算法(指那些会移除、重排、修改元素的算法)，若用于关联式容器或者无序容器、会出现问题。关联式容器和无序容器不能被当做操作目标，原因很简单，如果更易型算法用于关联式和无序容器身上，会改变某位置上的值，进而破坏了容器对于元素秩序的维护，对于关联式容器，会破坏其已经排序的特性，对于无序容器，会破坏其hash运算的结果。为了避免破坏容器内部的次序，关联式容器和无序容器所有迭代器均被声明为指向常量的value或key，如果变更关联式容器或者无序容器，会导致编译错误。

这使得你无法在关联式容器身上运用移除型算法，因为这种算法会悄悄的更改元素，被删除的元素会被后面的元素覆盖。那么如何从关联式容器或无序容器中删除元素呢？

#include <iostream>
#include <set>
#include <algorithm>
#include <iterator>

using namespace std;

int main() {
    set<int> coll = {1, 2, 3, 4, 5, 6, 7, 8, 9};

    cout << "pre: ";
    copy(coll.cbegin(), coll.cend(), ostream_iterator<int>(cout, " "));
    cout << endl;

    int num = coll.erase(3);
    cout << "the num of erased elements: " << num << endl;
    copy(coll.begin(), coll.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

}
输出：
pre: 1 2 3 4 5 6 7 8 9 
the num of erased elements: 1
1 2 4 5 6 7 8 9

?3、算法VS成员函数

举例说明，对list容器调用remove()，算法本身并不知道工作在list容器中，它对所有容器都一样，做一些四平八稳的工作，改变元素，重新排列元素，如果它移除了第一个元素，后面的元素会依次向前覆盖前面的元素，但是这违反了list通过修改指针进行元素删除的优点，为了避免这种情况，list中删除元素，使用成员函数会比remove()算法高效。

#include <iostream>
#include <list>
#include <algorithm>
#include <iterator>

using namespace std;

int main() {
    list<int> coll;

    for (int i = 0; i <= 6; i++) {
        coll.push_back(i);
        coll.push_front(i);
    }

    // 先调用算法remove获得新的结束iterator，再调用成员函数erase得到的iterator到最后区间的元素
    // 这种方法属于性能不好的方法
    coll.erase(remove(coll.begin(), coll.end(), 3), coll.end());

    // 直接使用成员函数进行删除，相当于list直接修改指针，并且是真的删除元素
    coll.remove(4);

    copy(coll.begin(), coll.end(), ostream_iterator<int>(cout, " "));
}
输出：
6 5 2 1 0 0 1 2 5 6

?4、for_each

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

using namespace std;

void print(int elem) {
    cout << elem << " ";
}

int main() {
    vector<int> coll;

    for (int i = 0; i <= 6; i++) {
        coll.push_back(i);
    }

    for_each(coll.begin(), coll.end(), print);
}
输出：
0 1 2 3 4 5 6

namespace std {
    template <typename Iterator, typename Operation>
    Operation for_each(Iterator act, Iterator end, Operation op) {
        while (act != end) {
            op(*act);
            act++;
        }
        return op;
    }
}

5、transform

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <iterator>
#include <string>

using namespace std;

int square(int value) {
    return value*value;
}

template <typename T>
void PRINT_ELEMENTS(const T& coll, const std::string& ops="") {
    std::cout << ops << std::endl;
    for (const auto& ele : coll) {
        std::cout << ele << " ";
    }
    std::cout << std::endl;
}

int main() {
    set<int> coll1;

    vector<int> coll2;

    for (int i = 0; i <= 6; i++) {
        coll1.insert(i);
    }
    PRINT_ELEMENTS(coll1, "initialized: ");
    std::transform(coll1.cbegin(), coll1.cend(), std::back_inserter(coll2), square);

    PRINT_ELEMENTS(coll2, "squared: ");
}
输出：
initialized: 
0 1 2 3 4 5 6
squared:
0 1 4 9 16 25 36

?6、判断式predicate

#include <iostream>
#include <algorithm>
#include <iterator>
#include <string>
#include <list>
#include <cstdlib>

using namespace std;

bool isPrime(int number) {
    number = abs(number);
    if (number == 0 || number == 1) {
        return false;
    }
    int divisor;

    for (divisor = number/2; number%divisor != 0; --divisor);
    return divisor == 1;
}

int main() {
    list<int> coll;

    for (int i = 24; i <= 30; i++) {
        coll.push_back(i);
    }

    auto pos = find_if(coll.begin(), coll.end(), isPrime);
    if (pos != coll.end()) {
        cout << *pos << " is first prime number found" << endl;
    } else {
        cout << "no prime number fouind" << endl;
    }
}
输出：29 is first prime number found

#include <iostream>
#include <algorithm>
#include <iterator>
#include <string>
#include <list>
#include <deque>
#include <cstdlib>

using namespace std;

class Person {
private:
    string fn;     //first name
    string ln;     //last name
public:
    Person() {}
    Person(const string& f, const string& n):fn(f), ln(n) {}
    string firstName() const;
    string lastName() const;
};

inline string Person::firstName() const {
    return fn;
}

inline string Person::lastName() const {
    return ln;
}

ostream& operator<< (ostream& os, const Person& p) {
    os << "[" << p.firstName() << " " << p.lastName() << "]";
    return os;
}


bool personSortCriterion(const Person& p1, const Person& p2) {
    return p1.lastName() < p2.lastName() ||
           (p1.lastName() == p2.lastName() && p1.firstName() < p2.firstName());
}


int main() {
    // create some persons
    Person p1("nicolai","josuttis");
    Person p2("ulli","josuttis");
    Person p3("anica","josuttis");
    Person p4("lucas","josuttis");
    Person p5("lucas","otto");
    Person p6("lucas","arm");
    Person p7("anica","holle");
    
    // insert person into collection coll
    deque<Person> coll;
    coll.push_back(p1);
    coll.push_back(p2);
    coll.push_back(p3);
    coll.push_back(p4);
    coll.push_back(p5);
    coll.push_back(p6);
    coll.push_back(p7);

    // print elements
    cout << "deque before sort():" << endl;
    deque<Person>::iterator pos;
    for (pos = coll.begin(); pos != coll.end(); ++pos) {
        cout << *pos << endl;
    }

    // sort elements
    sort(coll.begin(),coll.end(),    // range
         personSortCriterion);       // sort criterion

    // print elements
    cout << "deque after sort():" << endl;
    for (pos = coll.begin(); pos != coll.end(); ++pos) {
        cout << *pos << endl;
    }
}

?使用类做比较函数

class Pred {
private:
    int x;
    int y;
public:
    Pred(int x, int y): x(x),y(y){}
    bool operator()(int x) {
        return i > x && i < y;
    }
};

auto pos = find_if(coll.begin(), coll.end(), Pred(x, y));

相当于使用binder

auto pos = find_if(coll.begin(), coll.end(), 
            bind(logical_and<bool>(), 
                 bind(greater<int>(), _1, x),
                 bind(less<int>(), _1, y)));

7、Lambda的局限

用Lambda为关联式容器指出一个排序准则：

auto cmp = [](const Person& p1, const Person& p2) {
        return p1.lastName() < p2.lastName() || 
                (p1.lastName() == p2.lastName() && 
                 p1.firstName() < p2.firstName());
};

std::set<Person, decltype(cmp)> coll(cmp);

?由于为set声明需要指定Lambda类型，所以必须使用decltype，同时必须把Lambda对象传给coll的构造函数，否则coll会调用被传入的排序准则的default构造函数，而根据C++语言规则，Lambda没有default构造函数，也没有assignment操作符，基于这些局限，使用class定义某个函数对象作为排序准则或许更好。

Lambda的另外一个局限是它无法拥有“跨越多次调用”能够保存下来内部状态，如果需要这种状态，必须在外围声明一个对象或者变量，并使用引用捕获的方式传入Lambda，这个时候对象就更加方便。

函数对象

#include <iostream>
#include <algorithm>
#include <iterator>
#include <string>
#include <list>
#include <deque>
#include <cstdlib>

using namespace std;

#include <iostream>
#include <string>

template <typename T>
inline void PRINT_ELEMENTS (const T& coll,
                            const std::string& optstr="")
{
    std::cout << optstr;
    for (const auto&  elem : coll) {
        std::cout << elem << ' ';
    }
    std::cout << std::endl;
}
class AddValue {
private:
    int theValue;
public:
    AddValue(int v) : theValue(v) {}
    void operator() (int & elem) {
        elem += theValue;
    }
};

int main() {
    list<int> coll;
    for (int i = 0; i <= 9; i++) {
        coll.push_back(i);
    }
    PRINT_ELEMENTS(coll, "initialized: ");
    for_each(coll.begin(), coll.end(), AddValue(10));
    PRINT_ELEMENTS(coll, "after adding 10: ");
    for_each(coll.begin(), coll.end(), AddValue(*coll.begin()));
    PRINT_ELEMENTS(coll, "after adding first element: ");
    return 0;
}
输出：
initialized: 0 1 2 3 4 5 6 7 8 9 
after adding 10: 10 11 12 13 14 15 16 17 18 19 
after adding first element: 20 21 22 23 24 25 26 27 28 29

预定义函数对象

#include <iostream>
#include <algorithm>
#include <iterator>
#include <string>
#include <list>
#include <deque>
#include <cstdlib>

using namespace std;

#include <iostream>
#include <string>

template <typename T>
inline void PRINT_ELEMENTS (const T& coll,
                            const std::string& optstr="")
{
    std::cout << optstr;
    for (const auto&  elem : coll) {
        std::cout << elem << ' ';
    }
    std::cout << std::endl;
}

int main() {
    deque<int> coll = {1, 2, 3, 4, 5, 6, 11, 14, 15};
    PRINT_ELEMENTS(coll, "initialized: ");
    transform(coll.cbegin(), coll.cend(), coll.begin(), negate<int>());
    PRINT_ELEMENTS(coll, "negated: ");
    transform(coll.cbegin(), coll.cend(), coll.cbegin(), coll.begin(), multiplies<int>());
    PRINT_ELEMENTS(coll, "squared: ");
    return 0;
}
输出：
initialized: 1 2 3 4 5 6 11 14 15      
negated: -1 -2 -3 -4 -5 -6 -11 -14 -15 
squared: 1 4 9 16 25 36 121 196 225 

#include <iostream>
#include <algorithm>
#include <iterator>
#include <string>
#include <list>
#include <deque>
#include <functional>
#include <set>
#include <cstdlib>

using namespace std;
using namespace std::placeholders;

template <typename T>
inline void PRINT_ELEMENTS (const T& coll,
                            const std::string& optstr="")
{
    std::cout << optstr;
    for (const auto&  elem : coll) {
        std::cout << elem << ' ';
    }
    std::cout << std::endl;
}

int main() {
    set<int, greater<int>> coll1 = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    deque<int> coll2;
    PRINT_ELEMENTS(coll1, "initialized: ");
    // bind(multiplies<int>(), _1, 10)这里给multiplies通过bind绑定了一个参数10，使其成为单参数函数
    transform(coll1.cbegin(), coll1.cend(),
              back_inserter(coll2),
              bind(multiplies<int>(), _1, 10));  
    PRINT_ELEMENTS(coll2, "transformed: ");

    replace_if(coll2.begin(), coll2.end(), 
              bind(equal_to<int>(), _1, 70),
              42);
    PRINT_ELEMENTS(coll2, "replaced: ");

    coll2.erase(remove_if(coll2.begin(), coll2.end(),
                bind(logical_and<bool>(),
                     bind(greater_equal<int>(), _1, 50),
                     bind(less_equal<int>(), _1, 80))),
                coll2.end());
    PRINT_ELEMENTS(coll2, "removed: ");
    return 0;
}
输出：
initialized: 9 8 7 6 5 4 3 2 1 
transformed: 90 80 70 60 50 40 30 20 10 
replaced: 90 80 42 60 50 40 30 20 10    
removed: 90 42 40 30 20 10 

?调用集合中的对象的成员函数

for_each(coll.cbegin(), coll.cend(),
         bind(&Person::save, _1));

Person::save()函数被依次调用。

8、STL的使用

?使用STL，必须满足以下要求：

（1）迭代器必须合法而有效，使用之前需要初始化，迭代器可能因为其他动作的副作用而失效，对于vector和deque，一旦发生元素安插、删除或者重新分配，对于无序容器而言，一旦发生rehashing（重新散列）；

（2）迭代器如果指向结束位置，并不指向任何对象，不能对其调用operator*或者operator->操作，适用于任何容器的end(), cend(), rend();

（3）迭代器指明的区间必须是合法的；

（4）如果涉及不止一个区间，第二个区间以及后继各个区间必须拥有和第一个区间至少一样多的元素；

（5）覆写动作中的目的地区间必须拥有足够的元素，否则就必须使用insert_ierator<>迭代器。

#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    vector<int> coll1;    // empty collection
    vector<int> coll2;    // empty collection

    // RUNTIME ERROR:
    // - beginning is behind the end of the range
    vector<int>::iterator pos = coll1.begin();
    reverse (++pos, coll1.end());

    // insert elements from 1 to 9 into coll1
    for (int i=1; i<=9; ++i) {
        coll1.push_back (i);
    }

    // RUNTIME ERROR:
    // - overwriting nonexisting elements
    copy (coll1.cbegin(), coll1.cend(),  // source
          coll2.begin());                // destination

    // RUNTIME ERROR:
    // - collections mistaken
    // - cbegin() and cend() refer to different collections
    copy (coll1.cbegin(), coll2.cend(),  // source
          coll1.end());                  // destination
}

接近安全的安插元素

template <typename T, typename Cont, typename Iter>
void insert(Cont& coll, const Iter& pos, const T& value) {
    Cont tmp(coll);   //copy container and all elements
    try {
        coll.insert(pos, value);
    } catch (...) {
        coll.swap(tmp);
        throw;
    }
}

为什么说是接近安全的，当swap针对关联性容器复制“比较准则时”，如果发生异常，swap()便会抛出异常。

?9、通用操作

std::vector<float> c(l.begin(), l.end());
std::vector<std::string> c(std::make_move_iterator(l.begin()),
                           std::make_move_iterator(l.end()));
int array[] = {1, 2, 3, 4, 5};
std::set<int> c(std::begin(array), std::end(array));
// std::begin(), std::end()自C++11开始被定义于<iterator>中

//从标准输入完成初始化
std::deque<int> c{std::istream_iterator<int>(std::cin),
                  std::istream_iterator<int>()};
//注意应该使用新式的一致性初始化语法，大括号，否则就需要额外的小括号包裹初始化参数
std::deque<int> c((std::istream_iterator<int>(std::cin)), 
                   (std::istream_iterator<int>()));
std::vector<int> v2 = std::move(v1);

?无序容器只定义操作符==和不等!=，当容器内的每个元素都在另一个容器有相等元素，这些操作就返回true，次序无关紧要。由于无序容器没有提供<,<=,>,>=，所以只有==和!=是共通条件。

如果其他元素被删除，所有容器（除了vector,deque）都保证迭代器以及用以指向元素的reference继续保持有效，但对于vector，只有删除点之前的元素才保持有效。如果以clear()移除所有元素，对于vector、deque、string而言，任何由end()，cend()返回的结尾迭代器都会失效。

如果插入元素，只有list、forward list和关联式容器保证原本的迭代器和用以指向元素的reference继续保持有效，对于vector而言，当插入动作不超过容量时，迭代器才有效，否则vector开辟新的空间，迭代器就失效了。至于无序容器，上述保证对于reference一般是成立的，但对于迭代器则只有不发生rehashing才成立，而只要安插的最终元素个数小于bucket个数乘以最大负载系数，就不会发生rehashing。??