(一)随记-STL

 

一、树

(1)BST-二叉查找树、二叉排序树;

    左子树所有结点的值均小于或等于它根结点的值;右子树上所有结点的值均大于或等于它根结点的值;

(2)RBT-红黑树、平衡二叉查找树;

    防止二叉查找树变成线性,

(2)AVL-平衡二叉树:任何结点的两个子树高度差不会超过1;

    根据平衡因子做判断,左旋右旋等完整解析:https://baijiahao.baidu.com/s?id=1669654153406486945&wfr=spider&for=pc

 

一、迭代器失效

(1)关联容器迭代器,比如map、set、multimap、multiset, 删除当前的iterator, 仅仅会使当前的iterator失效,只要在erase时,递增当前iterator即可,因为map类的容器;使用了红黑树或者平衡二叉树来实现;即便插入、删除一个结点,可以调整自身的平衡性,不会对其它结点产生影响;erase迭代器只是被删元素的迭代器失效,但是返回值为void, 所以要采用erase(iter++)自增的方式来删除迭代器;

// 正确代码
for (it = m.begin(); it != m.end(); it++) {
  if (it->first==5) {
    m.erase(it++);
  }
}

(2)序列容器迭代器,比如vector、deque, 删除当前的迭代器iterator时,其后所有元素的迭代器都会失效,这是因为序列式容器都是连续分配的内存空间,当对其进行erase操作时,后面的所有元素都会向前移动;因此earse需要返回下一个有效的iterator;

for (it = m.begin(); it != m.end(); it++) {
  (*it)->doSomething();
  if (*it > 3) {
    it = m.erase(it); // 返回下一个有效的迭代器
  } else {
    ++ it;
  }
}

  

上一篇:【Reactor】总结


下一篇:《你不常用的c#之一》:略谈unsafe