C++容器和算法

容器：某一类型数据的集合。

C++标准顺序容器包括：vector，list，queue

容器初始化

        vector<int> t;
        for (int i = 0; i < 50; i ++) {
                t.push_back(i);
        }

        vector<int> c; // 空容器
        vector<int> c1(t); // 容器t的副本
        vector<int> c2(3, 4); // 3个值为4的容器
        vector<int> c3(t.begin(), t.end() - 10); // 容器t的begin()和end()-10之前的数据副本
        vector<int> c4(5); // 创建包含5个空默认值的副本

容器类型的规则：支持复制和赋值操作

容器的迭代访问

窗口的迭代访问非常类似指针的操作，都支持++和--的位移操作，迭代器内置了操作符重载。

*item
item->num
++item
item++
--item
item--
iter1 == iter2
iter1 != iter2

迭代器访问

for (vector<string>::iterator iter = strs2.begin(); iter != strs2.end(); iter ++) {
        std::cout << *iter << std::endl;
    }

迭代器的首元素迭代器和尾元素迭代器可以通过begin()和end()方法获取，并通过++方法进行迭代。

迭代器操作的API：

Iterators:

beginReturn iterator to beginning (public member function )endReturn iterator to end (public member function )rbeginReturn reverse iterator to reverse beginning (public member function)rendReturn reverse iterator to reverse end (public member function)容器的元素类型

Member types

of template <class T, class Allocator=allocator<T> > class vector;

 通过reverse类型属性，可以逆序访问容器的迭代器

增加和删除元素

容器的API提供在具体什么位置增加或者删除元素，或者在什么元素增加或者删除元素：

Modifiers:

assignAssign vector content (public member function)push_backAdd element at the end (public member function)pop_backDelete last element (public member function)insertInsert elements (public member function)eraseErase elements (public member function )swapSwap content (public member function )clearClear content (public member function)

容器大小

Capacity:

sizeReturn size (public member function)max_sizeReturn maximum size (public member function )resizeChange size (public member function)capacityReturn size of allocated storage capacity (public member function)emptyTest whether vector is empty (public member function)reserveRequest a change in capacity (public member function)

关联容器

C++中的关联容器包括 map 和 set

map与key, value相对应，整合起来map与pair类型对应

set 直接与 value相对应

1. 同时存在multimap和multiset两个对象，支持一个key对应多个value

C++的容器算法

最常见的是find方法，C++中的示例：

// 包含必要的头文件

#include <algorithm>

vector<int> vec(2, 35);
vec.push_back(8);
vec.push_back(80);
vec.push_back(98);
vec.push_back(25);
vec.push_back(12);
vector<int>::const_iterator result = find(vec.begin(), vec.end(), 80);
std::cout << 80 << (result == vec.end() ? " is not present" : " is present") << std::endl;

除了少数情况下，C++的容器算法都是在一个范围内的元素进行操作。所以其参数顺序情况一般为：iter_begin, iter_end, search_value。

C++容器使用的算法与数据结构书中大致相同：

1. 只读算法（查找）

2. 写算法（排序）

3. 合并

4. 堆

5. 最大/最小值等

常用只读算法：

....

实践了fill, fill_n, back_inserter, copy, replace, sort, count_if

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;
void log(std::string log) {
    std::cout << log << std::endl;
}
void apiTest() {
}
int main()
{
    vector<int> vec(2, 10);
    vec.push_back(3);
    vec.push_back(4);
    vec.push_back(15);
    vec.push_back(45);
    vec.push_back(24);
    vec.push_back(234);
    fill(vec.begin() + 1, vec.end() - 2,3);
    fill_n(back_inserter(vec), 10, 2);
    replace(vec.end() - 5, vec.end(), 2, 8);
    vector<int>::const_iterator iter = vec.begin();
    for (;iter != vec.end();iter++) {
        std::cout << *iter << std::endl;
    }
    vector<int> vec2;
    copy(vec.begin(), vec.end(), back_inserter(vec2));
    return 0;
}

输出结果：