STL --最常见的容器使用要点

如果只是要找到STL某个容器的用法，可以参考msdn和C++ Library Reference,msdn 上面的知识点应该是最新的，C++ Library Reference虽古老但是很多经典的容器使用有很多例子，二者可以相互参考，另外，本博客中提到的一些链接也是学习的好材料。

另有一篇文章总结很简洁，可以参考：烂笔头的专栏

一、vector

dfsf

二、map

dfdsf

三、set

总览：

set中每个元素都是不同的。

set中的元素默认是升序排列的，按照msdn中的描述来说是这样的：

Sorted, because its elements are ordered by key values within the container in accordance with a specified comparison function

Elements follow a strict weak ordering at all times.

应用注意：

set底层实现是红黑树，红黑树是理想平衡二叉查找树的一种统计学上的最优实现，具体原理参见wiki，需要知道的是树上所做的插入删除查找操作都是logN的复杂度，所以效率很高
如果要改变一个set中某个位置的值，不是直接改变，而是先删除再插入

常用函数说明：

迭代函数：begin() end() rbegin() rend()
查找函数：

iterator find(

   const Key& _Key

);

返回的是迭代器，如果找不到，返回s.end()

删除函数：erase，它有好几种调用形式

iterator erase(

   iterator _Where

);

iterator erase(

   iterator _First,

   iterator _Last

);

size_type erase(

   const key_type& _Key

);

count函数：因为set不允许重复元素，所以count为1表示存在，count为0表示不存在

使用示例：longest consecutive sequence—leetcode problem

class Solution {

public:

    int longestConsecutive(vector<int> &num) {

        // Start typing your C/C++ solution below

        // DO NOT write int main() function

        if(num.size()==0){

            return 0;

        set<int> s;

        for(int i = 0; i<num.size(); i++){

            s.insert(num[i]);

        int len = 0;

        // If not erase, it is O(n^2). Smart.

        for(int i = 0; i<num.size(); i++){

            int v = num[i];

            if(s.find(v)!=s.end()){

                s.erase(v);

                int count = 1;

                int u = v;

                while(s.find(--u)!=s.end()){

                    s.erase(u);

                    count++;

                u = v;

                while(s.find(++u)!=s.end()){

                    s.erase(u);

                    count++;

                if(count>len){

                    len = count;

        return len;

};

收集资料的过程中看到了几篇读书笔记,感觉很给力,自己没空读的书,有人整理得如此整齐,真是不错.

四、list

秒客网

STL --最常见的容器使用要点

总览：

相关文章