用C++写算法题需要掌握的一些知识

vector

向量，相当于一个能够动态扩容的数组。

方法

begin() 返回指向容器中第一个元素的迭代器

end() 返回指向容器中最后一个元素后面的位置的迭代器

rbegin() 返回指向容器中最后一个元素的反向迭代器

rend() 返回指向容器中第一个元素前面的反向迭代器

erase(…) 传入一个下标值，删除该下标对应的元素值，后面的元素会自动往前移动。

clear() 从容器中删除所有元素。

size() 返回容器的长度

max_size() 返回容器最大长度

push_back(…) 在容器末尾插入数据

pop_back() 删除容器最后一个元素

empty() 返回一个 bool 值，判断容器是否为空

at(…) 传入下标值，返回该下标位置保存的元素值

front() 返回容器中第一个元素的引用。

back() 返回容器中最后一个元素的引用。

iterator insert(iterator i, const T & val) 将 val 插入迭代器 i 指向的位置，返回 i

算法

find()

将迭代器输入到序列中的初始位置和最终位置。的范围内搜索就是[first,last)，它包含所有的元件第一和最后一个，包括由指向的元件第一但不被指向的元素最后。

int a[10] = {10,20,30,40};
vector<int> v;
v.push_back(1);    v.push_back(2);
v.push_back(3);    v.push_back(4); //此后v里放着4个元素：1,2,3,4
vector<int>::iterator p;
p = find(v.begin(),v.end(),3); //在v中查找3

if(p != v.end()) //若找不到,find返回 v.end()
cout << "1) " <<  * p << endl; //找到了

// v.end() 是最后一个元素的后一个位置，而 find 函数第一个参数是 左闭右开 区间,[first, last) 则 find(v.begin(), v.end(), 3) 则表示在第一个位置到最后一个位置（包含最后一个元素）查找元素3。

sort()

该算法可以用来对区间 [first, last) 从小到大进行排序。下面两行程序就能对数组 a 排序：

int a[4] = {3, 4, 2, 1};
sort(a, a+4);

iterator

通过迭代器可以读取它指向的元素，*迭代器名就表示迭代器指向的元素。通过非常量迭代器还能修改其指向的元素。

迭代器都可以进行++操作。反向迭代器和正向迭代器的区别在于：

对正向迭代器进行++操作时，迭代器会指向容器中的后一个元素；
而对反向迭代器进行++操作时，迭代器会指向容器中的前一个元素。

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int> v;  //v是存放int类型变量的可变长数组，开始时没有元素
    for (int n = 0; n<5; ++n)
        v.push_back(n);  //push_back成员函数在vector容器尾部添加一个元素
    vector<int>::iterator i;  //定义正向迭代器
    for (i = v.begin(); i != v.end(); ++i) {  //用迭代器遍历容器
        cout << *i << " ";  //*i 就是迭代器i指向的元素
        *i *= 2;  //每个元素变为原来的2倍
    }
    cout << endl;
    //用反向迭代器遍历容器
    for (vector<int>::reverse_iterator j = v.rbegin(); j != v.rend(); ++j)
        cout << *j << " ";
    return 0;
}

写++i、++j相比于写i++、j++，程序的执行速度更快。回顾++被重载成前置和后置运算符的例子如下:

CDemo CDemo::operator++ ()
{  //前置++
    ++n;
    return *this;
}
CDemo CDemo::operator ++(int k)
{  //后置++
    CDemo tmp(*this);  //记录修改前的对象
    n++;
    return tmp;  //返回修改前的对象
}

stack

void pop(); 弹出（即删除）栈顶元素

T & top(); 返回栈顶元素的引用。通过此函数可以读取栈顶元素的值，也可以修改栈顶元素

void push (const T & x); 将 x 压入栈顶

#include <iostream>
#include <stack>  //使用stack需要包含此头文件
using namespace std;
int main()
{
    int n, k;
    stack <int> stk;
    cin >> n >> k;  //将n转换为k进制数
    if (n == 0) {
        cout << 0;
        return 0;
    }
    while (n) {
        stk.push(n%k);
        n /= k;
    }
    while (!stk.empty()) {
        cout << stk.top();
        stk.pop();
    }
    return 0;
}

queue（队列）

FIFO 队列，先进先出

empty

size

front

back

push_back

pop_front

push 插入数据

pop 弹出数据

unordered_map

和 NSDictionary 类似

unordered_map<int, int> map;

map[i] = 1;

string

string

string s1;
s1 = "Hello";  // s1 = "Hello"
s2 = 'K';  // s2 = "K”

length 成员函数返回字符串的长度。size 成员函数可以实现同样的功能。

除了可以使用+和+=运算符对 string 对象执行字符串的连接操作外，string 类还有 append 成员函数，可以用来向字符串后面添加内容。append 成员函数返回对象自身的引用。例如：

string s1("123"), s2("abc");
s1.append(s2);  // s1 = "123abc"
s1.append(s2, 1, 2);  // s1 = "123abcbc"
s1.append(3, 'K');  // s1 = "123abcbcKKK"
s1.append("ABCDE", 2, 3);  // s1 = "123abcbcKKKCDE"，添加 "ABCDE" 的子串(2, 3)

5. string对象的比较
6. 除了可以用 <、<=、==、!=、>=、> 运算符比较 string 对象外，string 类还有 compare 成员函数，可用于比较字符串。compare 成员函数有以下返回值：

小于 0 表示当前的字符串小；

等于 0 表示两个字符串相等；

大于 0 表示另一个字符串小。

string s1("hello"), s2("hello, world");
int n = s1.compare(s2);
n = s1.compare(1, 2, s2, 0, 3);  //比较s1的子串 (1,2) 和s2的子串 (0,3)
n = s1.compare(0, 2, s2);  // 比较s1的子串 (0,2) 和 s2
n = s1.compare("Hello");
n = s1.compare(1, 2, "Hello");  //比较 s1 的子串(1,2)和"Hello”
n = s1.compare(1, 2, "Hello", 1, 2);  //比较 s1 的子串(1,2)和 "Hello" 的子串(1,2)