《STL源码剖析》勘误

STL源码剖析勘误

最近抽空读完了《STL源码剖析》，补上了当年只读一半的遗憾。

之前读过很多侯先生翻译的书，获益良多。但这本他亲自撰写的书，行文中却显得有些疏漏，不如他译作时那般细致。行文中有不少表述不清或与事实不符之处，略作记录如下。

• 对预定义宏的疑惑

在原书23页，有以下代码代码片段与注释

#ifdef __STL_NEED_TYPENAME
# define typename // 侯捷： 难道不该 #define typename class 吗？
#endif

侯先生的注释其实是误会了。这个宏的作用是在某些古老的编译器（如 gcc2.7）中，将 typename 这个当时还不是关键字的词“空气化”，从而避免标准写法编译失败：

typename iterator_traits<InputIterator>::value_type value;

这些老编译器无法识别上述写法，而如下的非标准写法却可以通过：

iterator_traits<InputIterator>::value_type value;

为兼容标准与老编译器，才需要通过宏将 typename 变为空。即

#ifdef __STL_NEED_TYPENAME //如果是上古编译器，此宏会被定义
# define typename // 此时源码里面写typename时，等于什么也不写
#endif

侯先生大概以为源码中会有如下写法：

template<typename T, typename U>
void fun(){};

若真如此，则在老旧编译器中需改为 class。但 SGI STL 中，模板声明一律用 class，并无 typename 的使用，自然也无需替换。

---

• 误以为distance可接收 output iterator

  第 99 页：

换句话说，当客端调用distance()并使用output iterator或forward iterator 或者 bidirectional iterator时，统统都会传递调用input iterator的那个__distance()函数。

这是想当然的说法。事实上，output iterator 连最基本的 == 操作都无法保证支持，根本不能作为 distance 的参数。标准库对此有限制。

---

• 误读 vector::insert_aux 的复制逻辑

第 122–123 页中有如下代码：

try｛
    //将原vector的内容拷贝到新vector
    new_finish = uninitialized_copy(start, position, new_start);
    //为新元素设定初值x
    construct(new_finish,x);
    //调整水位
    ++new_finish;
    //将原vector的备用空间中的内容也忠实拷贝过来（侯捷疑惑，啥用途？）
    new_finish = uninitialized_copy(position, finish，new_finish);
   ｝

侯先生将 [position, finish) 误认为是“备用空间”，其实这是插入点之后的有效元素，复制操作不可省略。

---

• 代码笔误：错误判断迭代器是否越界

第 138 页：

ite = find(ilist.begin(), ilist.end(), 1);
if (ite!=0)
    cout << *(ilist.erase(ite)) << endl;

ite != 0 显然错误，应为 ite != ilist.end()。

---

• 对list的sort算法类型错误归类

  第 142 页：

//本函数采用quick sort
template <class T, class Alloc>
void list<T, Alloc>::sort(){
    // ...
}

list 不支持随机访问，因此并不适合使用快速排序。在list内部，SGI STL 实际采用的是一种简洁高效的归并排序。

---

• 误解 __adjust_heap 的行为

在原书的178页，有如下注释

if(secondChild == len){ // 没有右子节点，只有左子节点
    // Percolate down: 令左子值为洞值，再令洞号下移至左子节点处。
    *(first + holeIndex) = *(first + (secondChild - 1));
    holeIndex = secondChild - 1;
}
// 将欲调整值填入目前的洞号内。注意，此时肯定满足次序特性
// 依侯捷只见，下面直接改为*(first + holeIndex) = value; 应该可以
__push_heap(first, holeIndex, topIndex, value);

此处又是作者想当然了。在前面找洞的过程中，并没有参考value值，因此，无法保证插入后立即满足次序特性，插入后必须重新调用__push_heap调整位置。若真按侯先生的方式改，那就要出bug了。

反面例子很容易构造，将176页heap内的31替换成35,24替换成33，即可验证。

---

• 红黑树插入分析遗漏一种情况

原书210页到211页，作者讨论了红黑树插入新节点后，树结构被破坏的四种情况，分别是

1. s为黑且X为外侧插入
2. s为黑且X为内测插入
3. s为红且X为外侧插入，对P和G单旋转后，并改变X的颜色后，GG为黑
4. s为红且X为外侧插入，对P和G单旋转后，并改变X的颜色后，GG为红

显然，作者没有分析s为红且X为内侧插入这种情况，如果出现这种情况，可以先按情况2方案处理，处理之后就会转化成情况3或者情况4。

---

• 对“由上而下”的理解错误

原书212页提到

5.2.2 一个由上而下的程序

并配了图解析。

但实际上，参考225页的源码就知道，所谓“由上而下”，并不是如作者所述的那样，它不是从根部往下处理，它的“由上而下”只体现在待平衡点X和它祖父节点G之间的局部，整体而言，这仍是自底向上的流程。先局部处理插入点到“它祖父”之间的关系，再向上处理“它祖父”到“它祖父的祖父”的关系，以此类推。

另外，此处还有明显笔误，“但是如果A的父节点P亦为红色”，这里的“A”应该是X。

---

• 红黑树__insert 的参数注释错误

  第 224 页：

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc>
typename rb_tree<Key, Value, KeyOfValue, compare, Alloc>::iterator
rb_tree<Key, Value, KeyOfValue, compare, Alloc>::
  __insert(base_ptr x_, base_ptr y_, const Value& v){
  //参数x_为新值插入点，参数y_为插入点之父节点，参数v为新值    
      //...
  }

“参数x_为新值插入点”这个说法与事实不符，看后面的源码可以发现，实际插入点由函数内部创建的 z = create_node(v) 决定。x_ 更多表示当前位置参考，或空节点。

---

• 未理解使用辅助函数的目的

  第 300 页：

template<class InputIterator, class OutputIterator>
OutputIterator adjacent_difference(InputIterator first, InputIterator last, OutputIterator result){
    if(fisrt == last) return result;
    *result = *first; //首先记录第一个元素
    return __adjacent_difference(fisrt, last, result, value_type(first));
    
    //侯捷认为(并经证实)，不需像上行那样传递调用，可改用以下写法(正个函数)
    //if(fisrt == last) return result;
    //*result = *first;
    //iterator_traits<InputIterator>::value_type value = *first;
    //while (++first != last){ //走过整个区间
    // ...以下同__adjacent_difference()的对应内容    
        
    }
}

侯先生推荐以下写法：

iterator_traits<InputIterator>::value_type value = *first;`

事实上，这样的写法是不符合c++标准的，标准的写法是：

typename iterator_traits<InputIterator>::value_type value = *first;

若侯先生确曾验证该写法，可能当时所用编译器并未严格遵循标准。

此外，类似iterator_traits<InputIterator>::value_type value = *first这种写法表达冗长，不如原代码那样清晰简洁。原来的value_type(first)简短而精确。

总而言之，此处作者并未理解源码中使用辅助函数的动机，并给了一个不符合c++规范的替代方案。实际上，这个替代方案更繁琐，晦涩。

---

• 未深究iota名字的含义

原书305页，有这样的注释

// 侯捷： itoa是什么的缩写
// 函数意义：在[first, last)区间内填入value, value+1, value+2...
  template <class ForwardIterator, class T>
  void iota(ForwardIterator first, ForwardIterator last, T value){
      while(first != last) *first++ = value++;
    }
  

其实 iota 是希腊字母“ι”，来源于编程语言 APL，并不是什么词组的缩写。

---

• 对nth_element的描述不严谨

第 374 页：

// 将小于*(iv.begin() + 5)(本例为40)的元素置于该元素之左
// 其余元素之于该元素之右，不保证维持原有的相对位置
nth_element(iv.begin(), iv.begin()+5, iv.end());
copy(iv.begin(), iv.end(), ostream_iterator<int>(cout, " "));
cout<<endl; //20 12 22 17 17 22 23 30 30 33 40

(本例是40)描述不对，正确的元素是序列第（5+1）大元素，本例里应该是22。

类似的表述错误也出现在原书409页。

---

• 对插入排序的描述与事实不符

第 390 页：

insertion Sort以双层循环的形式进行。外循环遍历整个序列，每次迭代决定出一个子区间：内层循环遍历子区间，将子区间的每一个“逆转对(inversion)”倒转过来。所谓“逆转对”是值任何两个迭代器 i, j, i <j 而 *i > *j。一旦不存在“逆转对”，序列即排序完毕。

显然，上面描述的是冒泡排序而不是插入排序。

在392页对__unguarded_inear_insert函数做注释时，侯先生也错误地将“平移”操作注释成“消除逆转对”。

---

• 可以写得更好的地方

此外，书中还有些虽不构成错误，但可以更好的地方。。

比如 algorithm 部分按字典序介绍，远不如按功能分类来得直观；又比如，部分注释只讲了“做什么”，没讲“为什么”；红黑树的理论缺乏；__rotate_cycle 的解释也缺位（本可借此引出美妙的数学同余关系）。

---

按惯例，读书之后总要写些感想。但这次写着写着，就成了勘误表。

虽然写着写着成了勘误表，但不得不说，这本书确实也让我受益良多——它陪我度过了三个愉快的周末，也唤起了我某些美好的回忆。