c++使用笔记&算法题填坑

记录在使用c++中需要遇到的一些注意点、以及一些容易忘的笔记。

一、关于内存管理

老生常谈的问题,在我的notes高频出现的。

在C++中使用new来初始化对象的指针成员时必须注意如下事项:
1. 如果在构造函数中使用new来初始化指针成员,则应在析构函数中使用delete来释放。
2. new和delete必须相互兼容,new对应与delete、new [ ]对应于delete [ ]。
3. 如果存在多个构造函数,则必须以相同的方式使用new,要么都用new,要么都用new [ ],因为只有一个析构函数,因此所有的构造函数都必须与它兼容。不过,可以在一个构造函数中用new来初始化指针,而在另外一个构造函数中将指针初始化为空(NULL 或0),只是因为delete (无论是带中括号还是不带中括号)可以用于空指针。

二、一些常见错误
1. % mod的mod不能为0,否则会Runtime Error
2. 读入double一般是%lf,输出是%f
3. 对于一些模板STL的写法,尽量不要出现>>这种,而是要加个空格变成> >. 例如在dijkstra中定义的这个pair第一个元素小根堆的优先队列:priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > q; 这个坑要小心,因为本地可能跑的是正常的,但是提交就GG了。这个的根本原因还是因为可能会产生歧义(boost::array<int, 1024>>2> x;就是需要用右移的意思)
4. cin遇到空格会停止。而getline(cin, s)则会获取一行。此时如果第一行是一个整数的话,cin >> n是不会读取末尾的换行的,我们可以gets(chs)一下,把那个换行直接读掉(CCCC比赛时这一点被坑了好久,当时比赛不得不把第一行直接用getline读了,囧)
5. 实数->整数的四舍五入如果不用ceil(向上取整)floor(向下取整),需要+0.5,不过如果直接输出的话%.0f就可以了。
6.关于取模,一定要中间结果大量%mod, 比如ans=abc;一定要ans=ab%modc%mod;如果有可能结果出现负数还要最后加mod再取下模mod.

三、一些C11
1.unordered_map解决map大量查询的O(logN)开销
STL中,map对应的数据结构是红黑树。红黑树是一种近似于平衡的二叉查找树,里面的数据是有序的。在红黑树上做查找操作的时间复杂度为 O(logN)。而unordered_map对应 哈希表,哈希表的特点就是查找效率高,时间复杂度为常数级别 O(1), 而额外空间复杂度则要高出许多。所以对于需要高效率查询的情况,使用unordered_map容器。而如果对内存大小比较敏感或者数据存储要求有序的话,则可以用map容器。头文件是unordered_map,其它用法类似。

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注