c++ 基础用法、基础知识以及一些常规的操作

时间:2021-07-20 14:45:35

1.二叉平衡树:左子树和右子树的深度差小于等于1

2.二叉搜索树:左子树小于根节点的值,右子树大于根结点的值

3.队列:push(),pop(),front(),back(),empty(),size()

4.vecotr: clear(),push_back(),pop_back()

二维vector初始化:vector<vector<int> > result(m,vector<int>(n)) 只初始化大小

             vector<vector<int> > result(m,vector<int>(n,0)) 初始化大小,也初始化vector中的值,都初始化为0

              result(m,n)是m个大小都初始化为n的值,result(m,vector<int>(n))才是大小为(m,n)

5.栈:push(),pop(),top(),size(),empty()

6.0x80000000,0x7FFFFFFF

7.multiset实现大根堆(底层用红黑树实现),multiset用迭代器访问:

multiset<int,greater<int>>::iterator greaternumber

greaternumber = container.begin()

greaternumber != container.end();greaternumber++

container.erase(*greaternumber)

container.insert(*iter)

multiset<int,greater<int>> 最大的数在begin的位置

multiset<int,less<int>> 最小的数在begin的位置

8.‘ ’字符,“ ”字符串

9.左移 >> ,右移 <<

10.异或 ^= 0等于自己,^=自己等于0

11.优先队列:priority_queue<int,vector<int>,less<int> >  最大的数在顶部,priority_queue<int,vector<int>,greater<int> > 最小的数在顶部

      push(),pop(),top()

      优先队列容器与队列一样,只能从队尾插入元素,从队首删除元素。但是它有一个特性,就是队列中最大或最小的元素总是位于队首,所以出队时,并非按照先进先出的原则进行,

      而是将当前队列中最大最小的元素出队。

12.to_string

13.vector<int> result;

result.insert(result.begin(),tmp);

vector通常采用的时候push_back(),从后面增加;在begin处insert,与push_back方式相比,相当于是一种逆序的操作。

145. Binary Tree Postorder Traversal二叉树的后序遍历用到了这种操作

14.string:  返回值是string的,如果返回空字符串,返回的是"",不是" ",也不是''

substr是提取子字符串,第一个参数是开始的index,第二个是个数,不是结尾的index

    find函数找到了返回的是字符串的第一个字符的index,找不到返回的是string:;npos

15.deque:双端队列

front()、back()查看队列的头元素和尾元素

pop_front()、pop_back()把队列的头或者尾元素弹出

push_back()把元素从尾巴上输入到队列中。

注意:不再具有队列的push、top、pop的操作

16.堆的实现有multiset和priority_queue

priority_queue和queue不同在于,queue是先进去的在头部,priority_queue是优先级高的在头部,这个优先级可以自己定义的。由于与queue很相似,操作也很相似,top()、push()、pop()。

priority_queue的定义是priority_queue<Type, Container, Functional>,type是存储数据的类型,container是存储使用的容器的类型,一般使用vector,functional是比较的方式。

priority_queue <int,vector<int>,less<int> > q是升序序列、priority_queue <int,vector<int>,greater<int> > q是降序序列。记忆的方式可以认为是less的在头部、或者greater的在头部。

#include <queue>

multiset<int,greater<int>> numbers:大根堆,即begin处是最大的值;multiset<int,less<int>> numbers:小根堆,即begin处是最小的值。记忆的方式是greater最大的头部

multiset<int,greater<int>>::iterator it 使用迭代器访问

#include <set>

17. unordered_map:  size(): 返回有效元素个数

           find():通过给定主键查找元素,没找到:返回unordered_map::end

count():返回匹配给定主键的元素的个数,也就是同一个key,对应多少个value

我记得哪个容器使用的是count,跟unordered_map的count运用场景不一样

         unordered_map可以通过主键来访问,返回是value值。比如m[1] = 1。find返回的则是迭代器,且迭代器指向的是键值对,first对应键,second对应值。

         rbegin是最后一个元素

           m.find(key) != m.end()就不在容器中

18.双向链表list的splice函数,void splice (iterator position, list& x, iterator i);  //将列表x中迭代器 i 指向的元素移到当前list的position指向的位置处,由于i指向的元素从列表x中被移除,所以迭代器 i 此时是invalid的;position是当前列表的迭代器,i是列表x的迭代器。时间复杂度为0(1)

list:pop_back删除最后一个元素

push_front在前面加入

19.pair、make_pair:   std::pair主要的作用是将两个数据组合成一个数据,两个数据可以是同一类型或者不同类型,->first、->second用于访问pair中的第一个和第二个元素

           make_pair:无需写出型别, 就可以生成一个pair对象

               例: std::make_pair(42, '@');

                  而不必费力写成: 
                  std::pair<int, char>(42, '@')

          pair中访问first、second不用加括号,a.first a.second,这个应该是成员变量,不像其他容器是成员函数

20.auto:可以在声明变量的时候根据变量初始值的类型自动为此变量选择匹配的类型

21.迭代器:是一种检查容器内元素并遍历元素的数据类型。C++更趋向于使用迭代器而不是下标操作,因为标准库为每一种标准容器(如vector)定义了一种迭代器类型,而只有少数容器(如vector)支持下标操作访问容器元素。