乐趣区

关于c++:算法笔记STL以及常见问题

jiezi

vector

vector<typename> name

函数 性能 工夫复杂度
push_back(x) 在 vector 前面增加一个元素 O(1)
pop_back() 删除 vector 的尾元素 O(1)
size() 取得 vector 的元素个数 O(1)
clear() 清空 vector 中的所有元素 O(N)，N 为 vector 元素个数
insert(it,x) 向 vector 的任意迭代器 it 处插入一个元素 x O(N)
erase(it) 删除迭代器 it 处的元素 O(N)
erase(first,last) 删除 [first,last) 内的所有元素 O(N)

queue

queue<typename> name

函数 性能 工夫复杂度
push(x) 将 x 进行入队 O(1)
front() 取得队首元素，应用前调用 empty()函数 O(1)
back() 取得队尾元素，应用前调用 empty()函数 O(1)
pop() 令队首元素出队 O(1)
empty() 检测 queue 是否为空 O(1)
size() 返回 queue 内元素的个数 O(1)

priority_queue

priority_queue<typename> name

函数 性能 工夫复杂度
push(x) 将 x 入队 O(logN)，N 为以后优先队列中的元素个数
top() 取得队首元素（即 堆顶元素 ）, 应用前调用 empty()函数 O(1)
pop() 令队首元素（即 堆顶元素）出队 O(logN)，N 为以后优先队列中的元素个数
empty() 检测优先队列是否为空 O(1)
size() 返回优先队列内元素的个数 O(1)

priority_queue<int> q 数字越 大优先级越大

priority_queue<int ,vector<int>,less<int>> q 数字越 大优先级越大

priority_queue<int,vector<int>,greater<int>> q 数字越 小优先级越大

#include <iostream>
#include <stdio.h>
#include <queue>


using namespace std;


struct fruit
{
    string name;
    int price;
    friend bool operator < (fruit f1,fruit f2)// 只能对小于号进行重载
    {
        return f1.price>f2.price;
        // 具体了解：如果 f1.price>f2.price 为 true，那么就认为 f1 "<" f2，所以 f1 应该在 f2 前面
        // 与 sort 函数中的 cmp 正好相同
    }
} f1,f2,f3;

int main()
{    priority_queue<fruit> q;
    f1.name = "桃子";
    f1.price = 3;
    f2.name = "梨子";
    f2.price = 4;
    f3.name = "苹果";
    f3.price = 1;
    q.push(f1);
    q.push(f2);
    q.push(f3);
    //printf("%s %d\n",q.top().name,q.top().price);
    cout<<q.top().name<<" "<<q.top().price<<endl;
    return 0;
}

priority_queue 的用处：解决贪婪问题；对 Dijkstra 算法进行优化。

stack

stack< typename > name

函数 性能 工夫复杂度
push(x) 将 x 入栈 O(1)
top() 取得栈顶元素 O(1)
pop() 弹出栈顶元素 O(1)
empty() 检测 stack 是否为空 O(1)
size() 返回 stack 内元素的个数 O(1)

set

set 内的元素 主动递增排序 ，且 主动去除了反复元素

set 迭代器拜访办法：

set<typename>::iterator it;

set<int>::iterator it;

set<char>::iterator it;

int main(){
      set<int> st;
      for(set<int>::iterator it=st.begin(); it!=st.end(); it++){printf("%d",*it);    
    }  
}
函数 性能 工夫复杂度
insert(x) 将 x 插入 set 容器中，并主动递增和去重 O(logN)
find(value) 返回 set 中对应值为 value 的迭代器 O(logN)
erase(it) 删除单个元素，it 为所须要删除元素的迭代器 O(1)
erase(value) 删除单个元素，value 为所须要删除元素的值 O(logN)
erase(first,last) 删除一个区间内的所有元素，即删除[first,lase) O(last-first)
size() 用来取得 set 内元素的个数 O(1)
clear() 用来清空 set 中的所有元素 O(N)，其中 N 为 set 内元素的个数

map

map 能够将任何根本类型（包含 STL 容器）映射到任何根本类型（包含 STL 容器）。

map<typename1,typename2> mp;

如果是字符串到整型的映射，必须应用 string 而不能用 char 数组。

map<string,int> mp;

map 容器中元素的拜访个别有两种拜访形式：

  1. 通过下标拜访；当建设映射的时候，就能够间接应用 map[‘c’] = 20 这样和一般数组一样的形式。

  2. 通过迭代器拜访；

    map<typename1,typename2>::iterator it;

    应用 it->first 来拜访键，应用 it->second 来拜访值。

map 会以键从小到大的程序主动排序。

函数 性能 工夫复杂度
find(key) 返回键为 key 的映射的迭代器 O(logN)，N 为 map 中映射的个数
erase(it) 删除单个元素，it 为须要删除的元素的迭代器 O(1)
erase(first,last) 删除左闭右开区间[first,last)，first 和 last 均为迭代器 O(last-first)
size() 用来取得 map 中映射的对数 O(1)
clear() 用来清空 map 中的所有元素 O(N)，N 为 map 中映射的个数

string

“xyz”>”abc” 成立，因为“x”>”a”

如何在一个 string 类型的变量前面增加删除 字符

string a;
a.push_back('a');
a.pop_back()

string 类型的变量 只能用双引号括起来，不能用单引号括起来：

string a = 'abc';// 谬误，python 能够这么干，c++ 不能
string b = "abc";// 正确
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {int in_degree[numCourses];
        vector<int> graph[numCourses];
        int nums = 0;
        queue<int> topo;
        for(int i=0; i<numCourses; i++){in_degree[i] = 0;
        }
        for(vector<int> tmp:prerequisites){graph[tmp[0]].push_back(tmp[1]);
            in_degree[tmp[1]]++;
        }
        for(int i=0; i<numCourses; i++){if(in_degree[i]==0){topo.push(i);
            }
        }
        while(!topo.empty()){int now = topo.front();
            topo.pop();
            nums++;
            for(int i=0; i<graph[now].size(); i++){in_degree[graph[now][i]]--;
                if(in_degree[graph[now][i]] == 0){topo.push(graph[now][i]);
                }
            }
        }
        if(nums==numCourses){return true;}
        return false;
    }
};

参考书目：《算法笔记》

退出移动版