Loading...
Navigation
Table of Contents

C++ STL & AlgorithmCode

algorthm

参见官网

基本

  • c min(a, b, comp) 返回对ab之间较小的引用,如果一样小,返回acomp可选
  • itr min_element(itr1, itr2, comp) 返回指向[itr1, itr2)区间里最小元素的迭代器;如有多个最小的,返回第一个
  • find(itr1, itr2, val) 返回指向区间[itr1, itr2)中第一个值等于val的迭代器,如果没有找到匹配元素,则返回itr2
  • unique(itr1, itr2)unique_copy(in_itr1, in_itr2, out_itr) unique的作用是去掉容器中连续元素(consecutive duplicates)中的重复元素(不一定要求数组有序),但并不改变数组大小,返回指向去重之后最后一个元素后面的位置的迭代器。
vector<int > v {1, 2, 2, 3, 2, 2, 4};
vector<int>::iterator new_end = unique(v.begin(),v.end()); //"删除"相邻的重复元素
v.erase(new_end, v.end());  //把后面冗余的元素去掉
v.resize(new_end - v.begin()); //也可以用这个操作
//erase()适合知道末尾迭代器时候,resize()适合知道长度时
  • unique_copy(in_itr1, in_itr2, out_itr)是将[in_itr1, in_itr2)区间里的unique一下,然后赋值给out_itr,返回一个iterator,指向copy完的后一个元素
int a [] = {1, 1, 2, 2, 3};
vector<int> v(5, 0);
vector<int>::iterator itr = unique_copy(a, a + 5, v.bein());
//此时 v = [1, 2, 3, 0, 0], itr指向第一个0
  • void reverse(itr1, itr2) 翻转[itr1, itr2)区间中的元素
  • void roatate(itr1, itr2, itr3)[itr1, itr2)区间和[itr2, itr3)区间旋转交换一下,用的是内部交换,不会申请新的内存
vector<int> v =  {1, 2, 3, 4, 5};
rotate(v.begin(), v.begin() + 2, v.end); //v = {3, 4, 5, 1, 2}
  • rotate的源代码实现很有水平
void rotate (ForwardItr first, ForwardItr middle, ForwardItr last){
  ForwardItr next = middle;
  while (first != next){
    swap (*first++, *next++);
    if (next == last) next = middle;
    else if (first == middle) middle = next;
  }
}

合并

  • itr merge(itr_a1, itr_a2, itr_b1, itr_b2, itr_res) 将排好序的[itr_a1, itr_a2)排好序的[itr_b1, itr_b2)区间的元素按顺序合并,写入到itr_res中,返回指向最后写入位置后一个位置的迭代器;注意,输入必须是排好序的
int a[] = { 1, 3, 2, 5, 4 };
int b[] = { 3, 3, 6 };
sort(a, a + 5);
sort(b, b + 3);

vector<int> v(10);
auto itr = merge(a, a + 5, b, b + 3, v.begin());
v.resize(itr - v.begin()); //v = {1, 2, 3, 3, 3, 4, 5, 6}

auto itr2 = set_union(a, a + 5, b, b + 3, v.begin());
v.resize(itr2 - v.begin()); //v = {1, 2, 3, 3, 4, 5, 6}
注意这里有两个3, set_union不会对输入去重!
  • itr set_union(itr_a1, itr_a2, itr_b1, itr_b2, itr_res) 用法和merge()相同,只不过merge时候去重,但是只考虑merge时候去重,不考虑输入本身里面是否有重复元素。

先排序后查找

  • sort(itr1, itr2, comp)stable_sort()
bool myCompare(int a, int b) {return a > b;}  //降序排列 
vector<int> a = {2, 3, 1};
sort(a.begin(), a.end()); //默认升序
sort(a.begin(), a.end(), myCompare);
sort(a.begin(), a.end(), greater<int>);

注意:

  • leetcode中sort的比较函数compare要声明为静态成员函数或全局函数,不能作为普通成员函数,否则会报错: invalid use of non-static member function. 非静态成员函数是依赖于具体对象的,而std::sort这类函数是全局的,因此无法在sort中调用非静态成员函数. 静态成员函数或者全局函数是不依赖于具体对象的,可以独立访问。
  • std::greater<T>, std::greater_equal<T>, std::less<T>std::less_equal<T>是stl里自带的两个比较器(struct)
  • itr lower_bound(itr1, itr2, val)upper_bound() 作用于升序数组,内部实现是二分查找. lower_bound()返回迭代器,指向键值>= key的第一个元素;upper_bound返回一个迭代器,指向键值<= key的最后一个元素的后一个元素。
vector<int> v {1, 2, 2, 4, 5};
vector<int>::iterator ptr = lower_bound(v.begin(), v.end(), 2); //ptr指向v[1]
vector<int>::iterator ptr2 = upper_bound(v.begin(), v.end(), 2); //ptr2指向v[3]
int pos = ptr - v.begin(); //迭代器转化为下标
  • bool binary_search(itr1, itr2, val, comp) 在排好序的数组中找到val便返回truecomp可选
  • itr partition(itr1, itr2, func)func(val) == true(第1块)的元素排在false(第2块)的前面,func自己传入;返回第2块的第1个元素;partition是不稳定的,即不能保证的顺序;稳定的可使用stable_partition
bool is_odd (int i) {return (i % 2) == 1;}
vector<int> v =  {1, 2, 3, 4, 5};
auto itr = partition(v.begin(), v.end(), is_odd); //v = {1, 3, 5, 2, 4}
cout << *itr; //2

shuffle/random_shuffle

c++中有random_shuffle()shuffle()两种方式来shuffle数组,具体参考这里

std::vector<int> v;
//1. 使用random_shuffle()
std::random_shuffle(v.begin(), v.end());
//2. 先产生一个随机数,然后使用shuffle() 
std::random_device rd;
std::mt19937 g(rd());
std::shuffle(v.begin(), v.end(), g);

iterator

iterator分为基本的input iterator和output iterator,然后是高级的forward iterator、bidirectional iterator和random access iterato,后面的包含前面的所有属性;

如vector使用的iterator都是random iterator,所有可以和数字算数加减;set使用的是bidirectional iterator,就只能自增自减。

iterator层次关系
iterator属性

关于插入型迭代器back_insert_iteratorfront_insert_iteratorinsert_iterator,参考插入型迭代器(Insert Iterator)插入迭代器


vector,array和list

vector

vector是变长数组,有empty()size() | push_back()pop_back()| insert()erase()clear() | front()back()begin()end() | v1.swap(v2)等成员函数。vector使用的都是random access iterator。

//初始化
vector<int> a1 = {1, 2, 3}; //{1, 2, 3}
vector<int> a2(3); //{0, 0, 0}
vector<int> a3(3, 2); //{2, 2, 2}
vector<int> a4 {1, 2, 3}; //列表初始化
int tmp = {1, 2, 3};
vector<int> a4(tmp, tmp + 3); //用数组/迭代器初始化vector
vector<int> a5(a1); //copy初始化
vector<int> a6 = a1; //同上,copy初始化
//参考 https://blog.csdn.net/veghlreywg/article/details/80400382
vector<vector<int> > a(5, vector<int>{ 1, 2, 3 }); // 必须用列表初始化,因为()已经被占用
vector<string> s(5, string("")); //声明空string数组
vector<string> s(5, string()); // 和上面等价

//访问元素
cout << a1[0]; //不检查index是否越界,返回引用
cout << a1.at(0); //检查index是否越界,返回引用
cout << a1.front(); //第一个元素的引用
cout << a1.back(); //最后一个元素的引用
cout << *a1.begin(); //第一个元素的迭代器
cout << *a1.end(); //最后一个元素后面的那个迭代器

//插入
a1.push_back(123); //尾部插入,返回void
vector<int>::iterator itr = a1.begin + 3; //迭代器
auto itr2 = a1.insert(pos, 123); //在某个位置插入,返回这个位置的迭代器
a1.insert(pos, 10, 123); //在某个位置插入10次
a1.insert(a1.begin(), a2.begin(), a2.end()); //范围插入
a1.insert(a1.end(), a2.begin(), a2.end()); //再a1末尾处插入

//删除
a1.pop_back(); //尾部删除
vector<int>::iterator pos = a1.begin + 3; //迭代器
a1.erase(pos); //删除这个位置的元素
a1.erase(pos, pos + 3); //删除这个区间的元素
a1.clear(); //清空这个vector
a.resize(2); //重置长度

array

array是定长数组,有empty()size() | front()back()begin()end() | fill()*,swap()等成员函数,无插入删除函数。

array<int,5> a1={1,2,3,4,5}; //注意初始化方式和vector不同
array<int,5> a2;
a2.fill(1); //arr2全部填充1
a2.swap(a1); //交换a1和a2
array<array<int,2>,3 > myarray2D={1, 2, 3, 4, 5, 6}; //2维数组?

list

list是双向链表,与vector相比,它允许快速的插入和删除,但是随机访问却比较慢,详见CSDN


string

string中没有\0的概念;有begin()end() (random access iterator) | size()length() (两者完全一样),resize()empty() | char& opeator[] (size_t pos)string& operator+= ()insert()erase() | s1.swap(s2) | c_str()find()rfind().substr(pos,len) (newly constructed string)

//初始化
string s0 ("abcdef"); //"abcdef"
string s1(s0); //"abcdef"
string s2(s0.begin(), s0.end()); //"abcdef"
string s3(s0, 2, 3); //"cde"
char a[] = { 'a', 'b', 'c', 'd', 'e', '\0' };
string s4(a); //"abcde"
string s5(a, 3); //"abc"
string s6(3, '='); //"==="
s1 = "another string"; //operator=
s1 = 'a'; //使用char赋值
s1 = s1 + s2; //operator+

//尾部加长
s0.push_back('a');
s0 += "aaa";
s0 += 'a';
s0.append("aaa");
s0.append('a'); //append还有多个重载
s0.insert(s0.end(), s1.begin(), s1.end()); //尾部加长

//insert
s0.insert(2, "aaa"); //insert(size_t pos, const string& str);
s0.insert(2, a); //insert(size_t pos, const char* s);
s0.insert(2, a, 3); //insert(size_t pos, const char* s, size_t n);
s0.insert(2, 3, '?'); //insert(size_t pos, size_t n, char c); 插入了"???"
s0.insert(s0.begin() + 2, 3, '?'); //insert(iterator p, size_t n, char c); 插入了"???"
s0.insert(s0.begin() + 2, '?'); //insert (iterator p, char c); 插入了"?"
s0.insert(s0.begin() + 2, s1.begin(), s1.end()); //insert(itr1, itr2_1, itr2_2);


//按位置删除
string s0 ("abcdef"); //"abcdef"
s0.erase(2, 3); //"abf"
s0.erase(s0.begin()); //"bf"
s0.erase(s0.begin(), s0.end());
s0.pop_back(); //删除最后一个字符

//.c_str()
char* cstr = s0.c_str();
char cstr2 = new char[s0.size() + 1];
strcpy(cstr2, cstr);

//.find() 返回第一次出现的位置
//.rfind() 返回最后一次出现的位置
string s0("abcdef");
string s1("cde");
int pos = s0.find(s1); //2, 即'c'所在的位置
int pos2 = s0.find("abc", 2); //-1, 找不到返回string::npos, 即-1

类型转换

<string>头文件里还有各种string和int/double互相转换的函数。

int stoi (const string&  str, size_t* idx = 0, int base = 10); //转为integer
long stol (const string&  str, size_t* idx = 0, int base = 10); //转为long
unsigned long stoul (const string&  str, size_t* idx = 0, int base = 10);

float stof (const string&  str, size_t* idx = 0);
double stod (const string&  str, size_t* idx = 0);
string to_string (anytype val); //val可以是int, double等等

string读取

string只支持两种方式读,都是非成员函数重载:

  • cin >> s 和传统的cin一样,首先清空缓冲区的分隔字符 (Enter、Space和Tab),然后开始读取,遇到分隔字符后结束,并保留缓冲区尾部的分隔字符;
  • istream& getline (istream& is, string& str) 当碰到Enter字符时结束,缓冲区里的Enter字符被丢掉;
  • istream& getline (istream& is, string& str, char delim) 当碰到delim字符时结束,缓冲区里的delim字符被丢掉。

以下代码演示了,如何读取一行未知长度的数组,然后转为int放进vector里。

//方案1 (推荐)
//最差input样例: "  1 22  33"
//正常input样例: "1 22 33"
//死循环input样例: "1 22 33 ", 即每一行最后一个字符不是Enter符
string s;
vector<int> v;
char a = ' ';
while (a != '\n') {
    string tmp;
    cin >> tmp;
    v.push_back(atoi(tmp.c_str()));
    a = cin.get();
}

//方案2
//最差input样例: "  1 22  33 "
//一般input样例: "1 22 33"
string s;
getline(cin, s);
vector<int> v;
int start = 0;
while (start < s.size() and s[start] == ' ')
    start++;
int i = start;
while (i <= s.size()) {
    if (i >= s.size() or s[i] == ' ') {
        string tmp = s.substr(start, i - start); //(pos, len)
        v.push_back(atoi(tmp.c_str()));
        start = i + 1;
        while (start < s.size() and s[start] == ' ')
            start++;
        if (start == s.size()) break;
        i = start + 1;
    }
    else
        i++;
}

set(multiset)/unordered_set

set里的element是弱递增排序的(内部用二分查找树实现的),unordered_set是无序的(内部用hash表实现的),单值查询unordered_set速度更快;两者的方法基本一致:begin()end() | insert()erase()set1.swap(set2) | find()count();set和unordered_set用的都是bidirectional iterator。

set里的元素一旦插入便不能修改(const类型),但可以删除再插入

vector<int> v {1, 2, 2, 3};
set<int> s(v.begin(), v.end()); //只能用range constructor初始化!
set<int> s2 = s; //拷贝初始化

//插入
pair<set<int>::iterator, bool> ret = s.insert(20);
//case 1: 输入单个value, 返回一个pair<迭代器, 是否插入成功>
set<int>::iterator itr2 = s.insert(s.begin(), 25);
//case 2: 输入(position, value), 返回一个迭代器, 指向25所在的位置(插入成功), 或已存在的25的位置(25已存在)
s.insert(v.begin(), v.end());
//case 3: 输入两个iterator

//删除
auto itr = s.erase(itr); //使用迭代器删除
int num = s.erase(20); //按值删除, 返回删除的元素数目, 为1或0
auto itr = s.erase(itr, s.end()); //按范围删除

//查找
auto itr = s.find(20); //若找不到, 返回s.end()
int num = s.count(20); //返回1或0

map/unordered_map

pair

pair 属于utility头文件,随便加个map或者vector头文件就能使用,pair更像是一个struct,所以first后面不加()

pair<int, string> p1(2018, "hi"); //使用()初始化, 而不是{}
pair<int, int> p2 = make_pair(10, 20);
cout << p2.first << p2.second.c_str();

map

map内部是按照key的顺序来排序存储的,而不是插入时间;有 begin()end() | empty()size() | map1[]map1.at() | inser()erase()map1.swap(map2)clear() | find()count() | map1.lower_bound(key)upper_bound();使用的是bidirectional iterator。

map<int, string> m; //或者用另一个map初始化此map
map<int, string>::iterator itr = m.begin(); //指向pair的bidirectional iterator
cout << itr->first << (*itr).second;

// 插入
m1[2012] = "school"; //case1: 如果2012存在, 则会修改value为"school"
pair<map<char, int>::iterator, bool> ret = m1.insert(pair<int, string>(2018, "hi"));
//case2: 其返回类型是"插入位置"和"是否插入成功"
map<int, string>::iterator itr = m1.begin();
m1.insert(itr, pair<int, string>(2017, "wow"));  //case3: 指定位置插入
m1.insert(itr, make_pair(2018, "wow"));

//通过key查找
cout << m[2012].c_str(); //返回对应于key=2012的value
cout << m[2013].c_str(); //注意, 因为没有2012, 所以会进行插入操作, 并且打印value
itr = m.find(2012); //返回指向key==2012的迭代器, 否则返回指向m.end()的迭代器
int i = m.count(2012); //key==2012的个数, 在map里结果非0即1

//通过key和迭代器删除
m.erase(2012); //case1: 按照key删除
itr = m.find(2013);
m.erase(itr); //case2: 按照迭代器删除
m.erase(itr, itr + 2); //case3: 批量删除

//lower_bound和upper_bound
map<char, int> m1;
m1['a']=20; m1['b']=40; 
m1['d']=60; m1['e']=80;
map<char,int>::iterator itr = m1.lower_bound ('c');  //指向了'd': 60
itr = mymap.upper_bound ('d'); //指向了'e': 80

stack

stack是栈,有empty()size() | push()pop() | top()这几个成员函数

#include <stack>
stack<int> a;
a.empty(); //true
a.push(12);
a.top() = 1; //top()返回int&
int t = a.top(); //这里不建议用引用, 用赋值即可
a.pop(); //pop返回值是void

queue/deque

queue是单端队列,有empty()size() | push()pop() | front()back()这几个成员函数。

deque也是一种容器,其是一种头尾部都能插入删除的双端队列。有empty()size() | push_back()pop_back()| push_front()pop_front()| front()back()begin()end()等成员函数. 详见C++三种容器 list,vector和deque的区别

heap/priority_queue

priority_queue是queue里面封装好的堆容器,有empty()size() | push()pop()top()方法。

如果不想用priority_queue类,也可以用algorithm里的make_heap(itr1, itr2), push_heap()pop_heap()等方法来建堆,详见make_heap

以下演示了使用小根堆寻找一个数组第K大的元素的例子

int findKthLargest(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> a; //小根堆, 最小元素优先级最高
    //priority_queue<int> a; //大根堆
    for (auto & i : nums) {
        if (a.size() < k)
            a.push(i);
        else if (i > a.top()) {
            a.pop(); //q.top()是小根堆的堆顶
            a.push(i); //堆底push
        }
    }
    return a.top();
}

Last updated on Sep 23, 2019.