无序向量

template <typename T> class Vector {};    // template定义方式

模板和模板, 模板和类之间可以互相组合。意味着数据结构之间也可以互相组合

template <typename T> class Vector {
};
class BinTree {
};
template <typename T> class Tree {
};

int main() {
  // ..
  Vector<int> myVector;    // Right

  Vector<float> myfVector;

  Vector<BinTree> binForest;       // Combine with other class;
  Vector<Tree<int>> binForest;     // Combine with template;
  return 0;
}

无序向量: 没有顺序, 甚至不可能排成顺序。

元素访问(寻秩访问)

v.get(r), v.put(e)

A[r]

重载下标运算符”[]”

// 寻秩访问
/* // my test
template <typename T>
T& Vector<T>::operator[](std::size_t n) {    // 这个类 Vector<T>
  assert(n < _size);
  return _elem[n];
}
*/

template <typename T>
T& Vector<T>::operator[](Rank r) const {   // 不改变数据成员, 定义成常量成员函数
  // 在vector内部, 定义了秩的类型, 统一用Rank
  assert(r < _size);   // 对下标秩进行溢出检测
  return _elem[r];
}

左值, 右值, 引用??
引用类型可作为左值。

寻秩访问

代码健壮性简化

assert 断言,
#include <cassert>
assert(r < _size);

插入

// 插入
/* my test
template <typename T>
void Vector<T>::insert(const Rank r, const int value) {
  // 检查移动后是否需要扩容
  if (++_size > _capacity) expand();
  // 将秩为r后的所有元素后移一位
  for (Rank i = _size-2; i >= r; i--) {     // 为了不覆盖数据, 从尾部开始移动
    _elem[i+1] = _elem[i];     // 向后移动一位
  }
  // 在r秩位置上填入要插入的值
  _elem[r] = value;
}
*/
template <typename T>
void Vector<T>::insert(const Rank r, T const &e) {
  // value不应该是某一中特点的类型, 而应该利用template的特性
  assert(0<= r && r < _size);
  expand();  // 若有必要扩容  结合expand()中, _size < _capacity的定义
  for (int i = _size; i > r; i--)  // 习惯把改变后的值的索引设置成i
    _elem[i] = _elem[i-1];     // 后继元素顺次后移一个单元
  _elem[r] = e; _size++;
}

Template中泛型T的作用,
模板类中函数的互相搭配,
插入元素对vector操作的顺序
对_capacity和_size的影响。

删除算法

自前向后的迁移操作
缩容

// 删除操作
/* my test code
template <typename T>
void Vector<T>::del(const Rank lo, const Rank hi) {
  for (Rank i = lo; i < _size; i++) {
    // 清空区间元素
    if (i < hi) { _elem[i] = 0;
    } else {
      // 将元素整体前移
      _elem[i - (hi-lo)] = _elem[i];
      // 前移后元素清空
       _elem[i] = 0;
    }
  }
  // 缩短规模和空间容量
  _size -= hi-lo; _capacity -= hi-lo;
}
*/


template <typename T>
int Vector<T>::del(Rank lo, Rank hi) {
  // 处理退化情况
  if (lo == hi) return 0;
  const int length = hi - lo;
  // 自前向后的迁移操作
  while (lo < _size) {
    if (hi < _capacity) {_elem[lo++] = _elem[hi++];
    } else {_elem[lo++] = 0;}   // 处理hi++超出_capacityg容量的情况
  }
  // 更新规模或者缩容
  _size -= length;
  shrunk();
  // 返回被删除元素的数目
  return hi-lo;
}

1, 规模仍旧不变? 删除一段区间, 这里可以不改变规模, 相当于后面留空? 改进成改变size的版本用于shrunk
2 , _elem[hi++]能够被一直索引到? 超过_capacity时, 返回未定义的值
3, _elem[hi++]为什么不清空?把_capacity的剩余空间对应元素赋值给它的方法清空
4, 看出移动操作过程中, 变量的同步性
5, 缩容不光光是改变_capacity的值, 仍旧要释放空间

查找

无序向量： T为可判等, 重载 “==”或者”!=”
有序向量： T为可比较，重载 “<” 或 “>”

// 查找
/* my test code
template <typename T>
int Vector<T>::find(Rank lo, Rank hi, T const &e) const {
  // 查找e在区间[lo,hi)内
  // 从右往左查找
  while (hi >= lo) {
    if (_elem[hi] == e) {return hi;
    }
    hi--;
  }
  // 没有在while循环中返回, 不存在匹配元素
  return -1;
}
*/

template <typename T>
Rank Vector<T>::find(Rank lo, Rank hi, T const &e) const {
  // O(hi - lo) = O(n), 在命中多个元素时可返回秩最大者
  while (lo < hi-- && e != _elem[hi]) {}   // 逆向查找
  return hi;   // hi < lo失败; 否则hi即命中元素的秩
}

利用while本身的条件语句；后置递增的特性
返回hi? 将判断是否成功, 交给上层的调用者;以及成功后被上层算法进一步利用

最好情况 O(1), 最坏情况O(n)
输入敏感(input-sensitive): 最好情况和最坏情况相差悬殊的算法。

删除单元素

视为区间操作的特例

// 删除单个元素
/* my test code
template <typename T>
void Vector<T>::remove(Rank r) {
  // 单元素的删除操作, 视为区间操作的特例 [r, r+1)
  remove(r, r+1);
}
*/
template <typename T>     // 删除向量中秩为r的元素, 0 <= r < size
T& Vector<T>::remove(Rank r) {  // O(n-r)
  T& old_t = _elem[r];    // 备份被删除的元素
  remove(r, r+1);         // 调用区间删除算法
  return old_t;           // 返回被删除元素
}

颠倒考虑

复杂度分析:
每次循环的耗时正比于删除区间的后缀长度 O(n-hi)
循环的次数等于区间宽度 O(hi-lo)
总体 O(n^2) 复杂度

right, but not fast!!

唯一化

实现

// 唯一化
/*
template <typename T>
void Vector<T>::deduplicate(Rank lo, Rank hi) {
  // 对向量中的元素遍历,
  for (Rank i = lo; i < hi; i++) {
    // find右往左查, 返回lo-1代表失败
    // 删除当前元素, 不再对后续元素查找
    if (find(lo, i, _elem[i]) != lo-1) {remove(i); break;}
    if (find(i+1, hi, _elem[i]) != i) { remove(i);}
  }
}
*/

template <typename T>
int Vector<T>::deduplicate() {
  int old_size = _size;
  Rank i = 1;
  while (i < _size) {
    find(0, i, _elem[i]) < 0 ?
                             i++  // 小于0说明无雷同, 继续查找
                             : remove(i);    // 删除雷同者(至多一个?!)
  }
  return  old_size - _size;      // 返回规模的变化量
}

记录规模? 考虑返回值怎么设计，这里我估计会在更高级的接口中用到
从1开始? 因为要在当前i的前缀中查找
至多一个? 删除至多一个, 实际不一定至多一个
为什么不需要改变_size和_capacity大小? 说明remove为更底层的操作, 在底层操作中, 定义底层的数据成员的修改, 这样做的话, 在更高级的操作中, 可以不去管这些细节。也是封装调用的好处。

**正确性证明**：
不变性: 对于当前元素V[i]的前缀V[0, i)中, 各元素彼此互异
初始时, i = 1, 两个元素成立,…

单调性:
1)前缀单调非降, 后缀减少, 且前缀迟早增至_size; // 与1)结合
2)后缀单调下降, _size迟早减至0; // 2)更容易把握

故算法必然终止, 至多迭代O(n)轮

复杂度

主要来自find() 和 remove();
find()从右向左针对前缀, remove()从左向右针对后缀, 因此每次while循环不超过O(n);
while循环会进行n次,
总体复杂度为 O(n^2)

练习三种优化方案（未完成）

1, 仿照uniquify()高效版本的思路.
元素移动的次数可以降至O(n), 但比较次数依然是O(n^2); 而且破坏稳定性
2, 先对需要删除的重复元素标记, 然后统一删除.
稳定性保持, 但因查找长度更长, 从而导致更多的对比操作
3, V.sort().uniquify(): 简明实现最优的O(nlogn)

遍历

visit

关于函数指针和函数对象的笔记
函数指针机制 ??

函数对象机制 ??

两种方法优劣

实例: 将向量中所有的元素统一加一
重载操作符 “++”
重载操作符 “()”

练习更为复杂的遍历

减1

// 遍历运用函数对象机制，对各个元素减1
/* my test code
// 单个T类型元素减1的类
template <typename T>
Vector<T>::struct Decrease {
  virtual void operator() {T &e--;}     // 重载()操作, 类对象当作函数来用
};

template <typename T>
void decrease(Vector<T>& V) {
  V.traverse(Decrease<T>());
}
// 泛型模板在调用的时候都要带<type>
*/

template <typename T>
struct Decrease {
  virtual void operator()(T &e) {e--;}
};

template <typename T>
void decrease(Vector<T> & V) {
  V.traverse(Decrease<T>());
}

为什么不是Vector::struct Decrease?

// Decrease对象, 不需要声明在vector类内, 这是借用函数对象作为traverse的参数, traverse声明在类内, 这个参数的类型是VST, 即函数对象。

为什么需要virtual

void operator()(T &e)?

// 第一个括号是代表重载运算符是(), 第二个是该重载函数的参数列表

三个函数之间的关系?

Decrease(T&)函数对象, Vector::traverse(VST&)遍历函数, decrease(Vector)

// 在类的外部定义decrease函数, 它具有泛型T, 参数为Vector& 类型
// decrease()函数内部, 实例V调用traverse方法, 通过多次调用这个函数对象去遍历所有元素

为什么需要函数对象?

本质问题: 为什么需要函数对象or 函数指针, 为什么不直接调用函数呢?

将遍历traverse作为一种统一的接口, 具体的操作让其他的函数对象来完成, 这样子的接口相对清晰。

加倍

Double(T &e)

template <typename T>
struct Double_value {
  virtual void operator()(T& e) {e *= 2;}   // 函数对象对元素翻倍
};

template <typename T>
void double_value(Vector<T>& V) {
  V.traverse(Double_value<T>());      // 函数对象作为遍历函数的参数
}

求和

函数中传入指针

Sum(T& e, T* sumPtr)

// 用于traverse的求和函数对象
template <typename T>
struct Sum {
  virtual void operator()(const T& e, T* sumPtr) {(*sumPtr) += e;}
};


template <typename T> template <typename VST>
T& Vector<T>::traverse(VST visit, T* e) {
  // 重载traverse(), 对Sum对象函数传入保存求和结果的指针
  for (int i = 1; i < _size; i++) visit(_elem[i], e);   // 从第二个值开始累加
  return *e;       // 返回求和结果
}

Sum()函数对象中传入的参数, 在traverse的visit中定义好的, 因此需要重载traverse函数, 让它传入一个保存求和结果的指针。

前面都没什么问题,
实际调用的函数, 第一次我是这样写的, 返回的结果正确无误。

template <typename T>
void sum_ptr(Vector<T>& V) {
  T* sumPtr = &(V[0]);        // 别定义空指针, 该指针指向向量首位
  T sum = V.traverse(Sum<T>(), sumPtr);     // 调用并赋值
  std::cout << "sum = " << sum << std::endl;
}

但print_vector()之后

-- --------print_vector--------- --
_size = 3
_capacity = 10
0:52                 ==> _elem的首位被修改, 原本应该是10
1:24
2:18
3:0
4:0
5:0
6:0
7:0
8:0
9:0

因为Sum函数对象中, 会通过解引用指针, 不小心修改了V[0]的值!!!

于是我便做了如下修改:

template <typename T>
void sum_ptr(Vector<T>& V) {
  T sum_init = V[0];              // 创建一个副本, 避免通过指针修改V[0]
  T* sumPtr = &(sum_init);        // 别定义空指针, 该指针指向副本
  T sum = V.traverse(Sum<T>(), sumPtr);     // 调用并赋值
  std::cout << "sum = " << sum << std::endl;
}

-- --------print_vector--------- --
_size = 3
_capacity = 10
0:10
1:24
2:18
3:0
4:0
5:0
6:0
7:0
8:0
9:0

重载函数什么时候用virtual?

类内static存放

static sumStc
静态数据成员在类内部声明, 外部定义, 作用相当于全局变量。

// 通过类内static求和的函数对象
template <typename T>
struct Sum_static {
  static T sum_t;     // 内部声明存放求和结果的static变量
  virtual void operator()(T& e) {
    sum_t += e; std::cout << "revise static sum_t, sum_t = "
                          << sum_t << std::endl;    // 当心全局变量出错
  }
};

template <typename T>
T Sum_static<T>::sum_t = 0;   // 外部定义静态数据成员

template <typename T>
void sum_static(Vector<T> V) {
  Sum_static<T> sumstc;           // 实例化模板别忘记<type>
  V.traverse(Sum_static<T>());
  T sum = sumstc.sum_t;
  std::cout << "in sum_static, sum = " << sum << std::endl;
}

关于static, 我的相关练习source code