Please enable JavaScript.

Coggle requires JavaScript to display documents.

CSP准备 (2、一些基本数据结构复习 (容器 (顺序容器：string、vector、deque、list (慎重选择删除元素的方法…

- - - - 慎重选择删除元素的方法
        
        对vector、string或deque使用erase-remove习惯用法
        
        c.erase(remove(c.begin(), c.end(), value), c.end());
        
        对于list，采用remove更加有效
        
        c.remove(value)
        
        对于关联容器，正确方法是调用erase
        
        c.erase(value)
      - 对于string和vector：使用reserve来避免不必要的重新分配
        
        当一个元素需要被插入而容器的容量不够时，就会发生重新分配过程（原始内存的分配与释放，对象的拷贝和析构，迭代器、指针和引用的失效）
        
        因此，避免重新分配的关键在于，尽早地使用reserve，把容器的容量设为足够大的值，最好是在容器刚被构造出来之后就使用reserve
        
        vector<int> v;
        
        for(int i = 1; i <= 1000; ++i)
        
        v.push_back(i);
        
        在每次发生重新分配时，vector通常把容量加倍，而1000大致等于2^10
        
        vector<int> v;
        
        v.reserve(1000);
        
        for(int i = 1; i <= 1000; ++i)
        
        v.push_back(i);
        
        则在该循环过程中，将不会发生重新分配
    - - 当效率至关重要时，请在map::operator[]与map::insert之间谨慎作出选择
        
        当向map中添加元素时，要优先选用insert。
        
        typedef map<int, Widget> IntWidgetMap;
        
        IntWidgetMap m;
        
        m.insert(IntWidgetMap::value_type(1, 1.50));
        
        当更新已经在map中的元素的值时，要优先考虑选择map::operator[]
        
        map<int, Widget> m={{1, 22}};
        
        m[1] = 1.5;
  - - - 二分搜索法（需要先进行升序排序）
  - - - 对于标准容器提供的insert和erase函数，它们仅接受iterator类型的参数。
- - - - 可以避免很多不必要的判断语句，从而提高程序效率。
      - 可以使得数组arr内的循环不必判断是否越界
    - - arr[0]=key;
        
        for(i = arr.length; arr[i] != key; --i);
        
        return i;
- - - - 囚徒困境
        
        警察抓了两个小偷，如果都不肯招，于是聪明的警察，给他们挖了这么一个坑，具体如下图。
        两人都不招，都判三年，两人都招，都判五年，一个人招，一个人不招，那么招的判一年，不招的判十年。
        
        优势策略
        
        “一报还一报”
        
        这个策略一共只有两条规则：（1）第一步先合作（不招供），（2）从第二步开始，对方上一轮出的是什么，我就出什么。
        
        “输则改之，赢着加冕”
        
        这策略很简单。如果我上一轮占了便宜（双方都合作，或者他合作了我背叛），那这一轮我继续上轮策略。如果我上一轮吃了亏（双方都背叛，或者我合作了他背叛），那这一轮我就换一种策略。
- - - - string s;
        
        const char *str = s.c_str();