太依赖标准库，有时让人变得笨拙

现在做程序的时候，开发人员都会偏向使用高级语言，例如Java，C#，PHP，一个很重要的原因就是开发效率高，开发速度快。而之所以这些高级语言能让写代码的速度变得那么快，一个重要原因就是伴随着这些高级语言的强大的接口类库。很多工作都简化成只要引用几个类库，调用几个方法就可以了。

不过太过简单了，有时也未必是好事，比如给数组排序只要 .Sort()就得出结果了，也不用管用冒泡排序，还是用了快速排序，或者因为不能全部加载而用了归并排序。

可是真说回来，谁在意呢。使用标准库，调用标准接口，大家都能看懂，而且经过多年的累积代码也更安全，效率自然也是更优的。

但是若真不在意，有时候也会让程序变得难以阅读，代码变得丑陋，效率也不见得很好。我就在使用C++的时候碰到了这个不幸的事情，太依赖C++的标准容器，导致自己也被绕进去出不来。

 

碰到的问题大致的意思可以归结为这样（实际问题是关于字符串子串的）：

有一个城市图，需要统计一个城市到另一个城市的道路条数。有可能一些城市直接不存在道路。一开始就会给出一共有多少个城市（不超过200个）。

 

这很明显是一个动态规划的问题，先要算出城市A和城市B之间的道路条数，如果B和C之间有连通，那么A到B上的道路条数都可以追加到A到C上。

既然可能有城市没有道路，那么我可以用std::list来存储城市，这样方便增删。每个城市到很多城市，那么城市下应该还有一个std::list来存储该城市所能到达的城市。

为了不新建类，我又用到的C++ <utility> 中的std::pair。于是建立的数据结构就像下边这样：

 

#include <list>
#include <utility>
using namespace std;

typedef unsigned char city_index;
//pair/city_index: the end index of city
//pair/int: the counter for city in specific situation
typedef pair<city_index, int> end_count;
typedef list<end_count> end_list;

//pair/city_index: restart, the index of start city
//pair/end_list: the list of indics end city
typedef pair<city_index, end_list> start_ends;
typedef list<start_ends> start_list;

复制代码

看着这样的定义，我还得意了一下：看，用了typedef，定义变量什么的我就不是写那么长的类型名称了。不过其实我错了：看着std::pair 的一堆fisrt和second我根本不知道是什么类型；定义个start_ends变量我也完全想不起来里面到底有什么成员，智能感知也无法告诉我；std::list的iterator又只是双向遍历器，无法直接获取中间某个值，每次都不得不从 it = list.begin() 一直 ++it 下去；因为不停的增与删，连自己了想不清是什么情况增加的又是什么情况删除的，又该如果判定是增还是删又是否已存在。

总之各种纠结的问题，把原本思路很清楚的问题，到实现的时候却因为不合理的数据结构而让实现变得艰难。

 

实现上，根本不需要用到什么标准库容器，也不需要什么std::pair来做个键值，然后一层套一层的让问题变得那么复杂，当然也不需要定义class来封装这些结构。因为类是自己定义的，那些接口方法还得自己实现自己纠结。

只要用二维数组就好了，并不需要什么复杂的数据结构。虽然C++ FAQ上一直强调数组是邪恶的（arrays are evil），强烈推荐我们使用std::vector来代替之。但是只要处理的好，数组是很便利和高效的。

而很多时候在用std::vector时候，我们大部分时间也只是当数组来用调用个[]，只是觉得std::vector有个size()可以得到数组的大小，而不需要自己记录。可惜要想用二位数组，我们就只能一层套一层了：std::vector<std::vector<type>>。

 

既然如此，那就直接用个二位数组，就会更加简单易懂：

#define MAX_NO_CITY 256

int roads[MAX_NO_CITY][MAX_NO_CITY];
int number_of_city;

复制代码

 

因为题目说了不会超过200个城市，所以就开个256x256的数组，虽然会浪费点空间，但是实际上这点空间是值得的，比起std::list增删中内存分配消耗的时间，换来的效率要高很多。

而且数组变量的含义也很清晰：第一维表示的是开始城市，第二维代表的是结束城市，数值就是两个城市之间的道路数了，之间没有道路的就是0，不想从中删除。

每次都从1到number_of_city进行遍历即可，不需要考虑太多的条件让问题变得纠结。

 

不过高级语言的类库依然还是开发中的利器，不可不用，更不可抛弃。只是有时候也不能让自己太陷入这种“便利”之中。