C++ STL 之 vectot(二)

今天我们继续更新 C++ STL 中 vector 容器的使用

---

---

vector 迭代器使用

与 array 类似，vector 中也有 begin() 和 end() 这两个成员函数，其分别指向容器的第一个元素和最后一个元素，同时，begin() 和 end() 也能从容器中获取迭代器。
这个例子汇总了使用迭代器和索引访问，并尽可能应用我们所学的知识。
示例如下：

#include <bits/stdc++.h>
using namespace std;

int main(){
    //定义一个二维vector,4x4 初值全为1
    vector<vector<int> > data(4,vector<int> (4,1));
    //使用 begin() 和 end()
    vector<vector<int> >::iterator first = data.begin();
    vector<vector<int> >::iterator last = data.end();
    while(first!=last){
        //vector<int> temp= *first;
        //对一维vector使用 begin() 和 end()
        //*first 得加括号
        vector<int>::iterator f = (*first).begin();
        while(f!=(*first).end()){
            cout<< *f <<" ";
            f++;
        }
        first++;
        cout<<endl;
    }
    //begin() 和 end() 函数来从容器中获取迭代器
    int index=1;
    vector<vector<int> >::iterator _first = begin(data);
    auto _last = end(data);
    while(_first!=_last){
        for(auto& t : (*_first)){
            t = index;
            index++;
        }
        _first++;
    }
    cout<<endl;
    //使用索引方式
    for(int i=0;i<data.size();i++){
        for(int j=0;j<data[i].size();j++){
            cout<<data[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

结果如下：

image.png

在上面这个例子中，
vector<vector<int> > data(4,vector<int> (4,1));
定义了一个二维 vector，它有四个元素，每一行都是一个 vector ，其中每一维都是一个大小为 4，初始值为 1 的一位 vector。
当我们使用 data 的迭代器时，可以使用 auto 和 vector<vector<int> >::iterator，而在访问 data 的每一维时，我们可以使用 auto 和 vector<int>::iterator。同时 begin(data)，可以从 data 中获取迭代器。

和 array 类似，成员函数 cbegin() 和 cend()也是类似作用。在之前的博客中有所介绍。
部分迭代器如下：

迭代器	作用
begin()	返回指向容器中第一个元素的迭代器
end()	返回指向容器最后一个元素所在位置后一个位置的迭代器
rbegin()	返回指向最后一个元素的迭代器
rend()	返回指向第一个元素所在位置前一个位置的迭代器
cbegin()	和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素
cend()	和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素
crbegin()	和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素
crend()	和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素

使用方式和 array 大同小异。
STL里面有一个 sort() 函数模板，它只要求迭代器指定的元素能够支持排序算法的运算，使用方法：

sort(data.begin(),data.end(),complare);

complare 是你自己指定的排序方法，如果是 data 是一个 int 类型的 vector ，那么 complare 可以这样写：

bool complare(int a,int b){
    return a>b;
}

vector 例题讲解

例题来自 leetcode，虽然涉及到容器的增加元素，但没有关系，先入为主地理解下吧！

合并区间

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:

输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-intervals

首先，我们得知道什么样的两个区间是可以合并的，之后，如何更好地合并，那当然是先将区间集合排序了，可以按左端点进行升序排列，因为本节的重点不是讲题，具体合并的方式还是见程序吧。
程序如下：

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> res;
        if(intervals.empty()) 
            return res;
        mysort(intervals);
        res.emplace_back(intervals[0]);
        for(int i=1;i<intervals.size();i++){
            int index=res.size()-1;
            if(res[index][1]>=intervals[i][0]){
                if(res[index][1]<intervals[i][1]){
                    res[index][1]=intervals[i][1];
                }
            }else{
                res.emplace_back(intervals[i]);
            }
        }
        return res;
    }
    void mysort(vector<vector<int>>& intervals){
        int n=intervals.size();
        for(int i = 0; i < n-1; i++){
            for(int j = i + 1; j < n; j++){
                if (intervals[i][0]>intervals[j][0]){
                    swap(intervals[i], intervals[j]);
                }
            }
        }
    }
};

这个题还有个 plus 版的，一起来看看吧。

插入区间

给出一个无重叠的 ，按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

示例 1:

输入: intervals = [[1,3],[6,9]], newInterval = [2,5]
输出: [[1,5],[6,9]]
示例 2:

输入: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出: [[1,2],[3,10],[12,16]]
解释: 这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/insert-interval

其实，该题并没用 plus 多少，如果从前一个问题出发，将新区间插入到原有区间集合中，之后的操作就和上一题相似了。这里就直接上程序了。
程序如下：

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        intervals.insert(intervals.begin(),newInterval);
        mysort(intervals);
        vector<vector<int>> res;
        if(intervals.empty()) 
            return res;
        res.emplace_back(intervals[0]);
        for(int i=1;i<intervals.size();i++){
            int index=res.size()-1;
            if(res[index][1]>=intervals[i][0]){
                if(res[index][1]<intervals[i][1]){
                    res[index][1]=intervals[i][1];
                }
            }else{
                res.emplace_back(intervals[i]);
            }
        }
        return res;
    }
     void mysort(vector<vector<int>>& intervals){
        int n=intervals.size();
        for(int i = 0; i < n-1; i++){
            for(int j = i + 1; j < n; j++){
                if (intervals[i][0]>intervals[j][0]){
                    swap(intervals[i], intervals[j]);
                }
            }
        }
    }
};

vector 迭代器的内容就暂时介绍到这了，如果有遗落重要的，后期会加上的，之后将介绍 vector 的增删元素操作。