dsfds' blog

STL 六大部件：

• 容器（Containers）
• 分配器（Allocators）
• 算法（Algorithms）
• 迭代器（Iterators）
• 适配器（Adapters）
• 仿函数（Functors）

一个例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>
using namespace std;
int main()
{
    int ia[6] = {27, 210, 12, 47, 109, 83};
    vector<int, allocator<int>> vi(ia, ia+6);
    
    cout << count_if(vi.begin(), vi.end(),
            not1(bind2nd(less<int>(), 40)));
    return 0;
}

前闭后开区间：begin 指向第一个元素，end 指向最后一个元素的下一个位置。

遍历容器：

1
2
3
4

Container<T> c;

Container<T>::iterator ite = c.begin();
for (; ite != c.end(); ++ite) {}

C++11带来的新方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

//    for ( decl : coll ) {
//        statement;
//    }
    for ( int i : { 2, 3 ,5, 7} ) {
        std::cout << i << std::endl;
    }
    
    std::vector<double> vec;
    for ( auto elem : vec ) {
        std::cout << elem << std::endl;
    }
    
    for ( auto &elem : vec ) {
        elem *= 3;
    }

容器——结构与分类

序列型容器（Sequence Containers）：

• Array（C++11）
• Vector
• Deque
• List
• Forward-List

关联型容器（Associative Containers）：几乎所有编译器支持的底层实现都是红黑树

• Set/Multiset
• Map/Multimap

无序容器（Unordered Containers）从C++11开始：底层实现是HashTable：Separate Chaining

• Unordered Set/Multiset
• Unordered Map/Multimap

数组相关算法中的原地操作，即空间复杂度位 $O(1)$，不需要开辟新的数组空间。一共是 5 道题： Replace Elements with Greatest Element on Right Side，Remove Duplicates from Sorted Array，Move Zeroes，Sort Array By Parity，Remove Element。其中有两题之前做过了，参考 从数组中删除元素。

两道题都是在数组中查找元素，Check If N and Its Double Exist，Valid Mountain Array。问题的关键在于，在一个无序数组中查找，一般而言时间复杂度会达到 $O(n^2)$，比如第一题，看起来只能先排序一遍，然后使用二分搜索等查找方法才能把复杂度降下来，这里不给题解了，用 C 解的话还要自己写排序，看来后续要切换到用 C++ 解才行。第二题比较简单，边界条件也很好处理。

接着上一篇 向数组中插入元素 而来，下面这两道题是从数组中删除删除元素，解法一样：Remove Element 和 Remove Duplicates from Sorted Array。我还是太菜了，居然做不出来……看了 solution 之后才恍然大悟，原来如此，我把两个指针一前一后放置，然后向中间靠拢，但是后面那个指针的移动太快了，因此导致出错，真是『步子大了，喀嚓，容易扯着蛋』。

今天就不写记录了，来写下今天做的两道题：duplicate zeros，merge sorted array，均来自 Array101 模块。

在写之前，我得反省下，做这两道题花的时间实在是太长了，这直接导致下午做毕设计划的失败，今天又是没做毕设的一天。已经是周五了，下周一需要和老师约一次讨论，后面两天抓紧点完成。为了控制自己去做不想做的事情，希望做到下面这些：刷题就给自己 15mins，做不出来就不要再想了，继续想下午八成也是做不出来的，不如直接看看答案的思路，好好学习下；别打游戏了……

寒假开始学习的第一天，马马虎虎过去了，傍晚手机传来『今日游戏时长已达3h，请放下手机休息』，由此可知今天的学习成果了。若真要细究，昨天做的那些安排，今天真正完成的怕只有关于算法的那一半，FPGA 那部分是根本没碰，我是真心不想搞这个东西，不过为了那一句『做自己不喜欢做的事情，还能做好才是真的厉害』我只能坚持下去，那么明天就得真正做起来。

8 号考完了本科阶段的最后一门课，题目很简单，考得也很顺利，只是离毕业又近了一步。今天是 1 月 13 号，经过了将近两天的路程，火车转汽车再转汽车，终于在昨天下午到家了，现在还是有点恍惚，假期就这么开始了？希望结束的时候不稀里糊涂。

又过了两天，感冒还是没好全，但好在体温不高，应该不会影响我的回家计划，数值分析已经复习得差不多了，我的目标早就不是奖学金一类的东西了，因为太难了我追求不到，倒不如现在就改换赛道，做点别的事情，也让自己能够开心点，求不得苦还是少受点为好。

真是糟糕，我已经记不得昨天发生了什么，午饭吃的什么东西呢？完全没有印象了，大概不重要的事情都是这样，一晃而过，我只是按照预订的路线去经历罢了，但那些刻骨铭心的事呢？我在内心不断对它进行加工，慢慢的，它变得面目全非，当时到底发生了发生什么，当时的我到底在想什么，都无从知晓了。这大概就是记录的意义，让平淡的生活留下痕迹，保留那些难得的珍贵回忆。

这两天的复习就是在消磨时间，因为内心认为考试比较简单，没有必要花太多时间，所以早就把认为该看的内容看完了，可惜的是多出来的这点时间全都白白消耗了，打游戏，逛论坛，刷 B 站，干什么都好，就是没有正经学习。啊！该做的计划也没有做，记得用notion吧，或者找一个更好的离线版的工具，不然每天真的不知道自己都干了些什么，用文字记录虽然可以，但总是不够直白，图表形式才是最好的。罢了罢了，明天再说，又是这样的态度，可惜没有办法，只能明天再说了。

明天好好考试，然后找老师讨论下放假要完成的任务，制定一个好的计划，这大概就是接下来的安排了。晚安。

以下内容为了极客时间专栏『数据结构与算法之美』的学习笔记。

复杂度也叫渐进复杂度，包括时间复杂度和空间复杂度，用来分析算法执行效率和数据规模之间的增长关系，可以粗略地表示，越高阶复杂度的算法，执行效率越低。

大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。

今天是 1 月 6 号，两天后将进行数值分析考试，那是本学期的最后一门考试课（研究生课），也是我本科参加的最后一门考试了。这几天好好复习了一下，虽然老师上课讲的好像比较复杂，比较难，但真要考起来也不会太难，往年的考试题也比较简单，心里有底了。写个简单的知识点总结吧，就当是消磨时间了，剩下这一两天也怪难熬的。