C++ vector和unordered_map浅析

我不是女神ヾ 2021-11-01 18:32 389阅读 0赞

C++内置的数组支持容器的机制，可是它不支持容器抽象的语义。要解决此问题我们自己实现这种类。在标准C++中，用容器向量（vector）实现。容器向量也是一个类模板。可以说vector的引入，方便了我们对一系列数据的处理，相比于数组，我们不用考虑下标越界等溢出问题了。

使用vecor，需要引入头文件\#include <vector>，命名空间需要引入using std::vector，再补充一下，vector是连续存储的！！！

简单的存储操作：

vector<int> v1;
    for (vector<int>::size_type i = 0; i < 10; i++) {
        v1.push_back(i);
    }
        cout << "adjective:";
        for (vector<int>::size_type i = 0; i < 10; i++) {
        cout << v1[i] << setw(4);
    }

然后比较坑的这个，注意一下就OK了：

//v1中有n个值为i的元素
    vector<int> v1(n,i);
    //v2中只有n和i两个元素
    vector<int> v2({n,i});

切记我们初始化的时候不能直接v1\[i\]=value，只能使用v1.push\_back(i);

详细的介绍请看[https://www.cnblogs.com/mengfanrong/p/3770971.html][https_www.cnblogs.com_mengfanrong_p_3770971.html]

再简单介绍下unordered\_map

C++ 11标准中加入了unordered系列的容器。unordered\_map记录元素的hash值，根据hash值判断元素是否相同。map相当于java中的TreeMap，unordered\_map相当于HashMap。无论从查找、插入上来说，unordered\_map的效率都优于hash\_map，更优于map；而空间复杂度方面，hash\_map最低，unordered\_map次之，map最大。

需要引入的头文件\#include <unordered\_map>，命名空间需要引入using std::unordered\_map，我的理解把他记做键值对，即(key,value)，很多场合都用到的，比如我们文件管理系统中的页表索引等等；参考[https://www.cnblogs.com/evidd/p/8823092.html][https_www.cnblogs.com_evidd_p_8823092.html]

来看一个两数和的算法吧

//两数和问题
    #include <iostream>
    #include <unordered_map>
    #include <vector>
    #include <iomanip>
    using std::cin;
    using std::cout;
    using std::endl;
    using std::vector;
    using std::unordered_map;
    using std::setw;
    class Change {
    public:
        vector<int> twoSum(vector<int>& nums, int target) {
            vector<int> res;
            unordered_map<int, int> hash;
            for (int i = 0; i < nums.size(); i++) {
                //记录待查值，接下来搜索
                int another = target - nums[i];
                if (hash.count(another)) {
                    //res记录下标，从0开始的，刚开始我也没反应过来
                    res = vector<int>({ hash[another],i });
                    break;
                }
                hash[nums[i]] = i;
            }
            cout << nums[res[0]] << setw(2) << nums[res[1]] << endl;
            return res;
        }
    };
    int main(int argc, char* argv[]) {
        vector<int> array;
        for (vector<int>::size_type i = 0; i < 5; i++) {
            array.push_back(i + 1);
        }
        int target = 6;
        Change c;
        vector<int> change;
        change = c.twoSum(array, target);
        return 0;
    }

转载于:https://www.cnblogs.com/SHNLQS-1273196803/p/11051218.html

[https_www.cnblogs.com_mengfanrong_p_3770971.html]: https://www.cnblogs.com/mengfanrong/p/3770971.html
[https_www.cnblogs.com_evidd_p_8823092.html]: https://www.cnblogs.com/evidd/p/8823092.html