C++容器、模板与虚函数的深入解析

### C++ 容器、模板与虚函数的深入解析 #### 1. Vector 容器效率分析 在考虑使用何种容器执行特定任务时，分析 `Vector` 成员函数的效率（时间要求）是很有必要的。这里以 `N` 表示当前数组大小，部分 `Vector` 函数的效率如下表所示： | 函数 | 效率（时间要求） | | --- | --- | | size | O(1) | | operator[] | O(1) | | operator= | O(N) | | 复制构造函数 | O(N) | | push_back | O(N) | 从表中可以看出，如果要对整个向量进行操作，所需时间为 O(N)；如果仅对单个元素进行操作，所需时间通常为 O(1)，但 `push_back` 除外，它需要 O(N) 的时间，因为要将旧内容复制到新的内存块中。 下面是相关的练习题： 1. 以 O 表示法，`print` 函数所需的时间是多少？ 2. 编写 `pop_back` 函数，它的时间要求是多少？如果不是 O(1)，说明你做了过多的工作！ 3. （较难）重写 `push_back` 函数，使其在添加新元素时，不是每次都重新分配内存，而是一次分配足够容纳十个新元素的内存，仅在每添加十个元素时进行一次内存分配。这样做是否会改变时间成本（以 O 表示法）？你认为这样做值得吗？ 4. 编写一个 `Queue` 类，它类似于 `Stack`，但从添加元素的相反端取出元素，即先进先出。按照惯例，在一端“入队”（`enqueue`），在另一端“出队”（`dequeue`）。以 O 表示法，`enqueue` 和 `dequeue` 的时间分别是多少？ #### 2. 将 Vector 转换为类模板 为了避免为不同类型（如整数、字符串等）的 `Vector` 编写全新的类，我们可以使用类模板。类模板本质上是创建类的一组指令，就像函数模板是创建函数的指令一样。将 `Vector` 转换为类模板的步骤如下： 1. 更改任何 `Vector` 声明，明确它是存储何种类型的 `Vector`。例如，`Vector` 变为 `Vector<int>`。 2. 将 `vector.cpp` 的内容移到 `vector.h` 中，并删除 `vector.cpp`。因为在调用 `push_back` 之前，处理 `int` 类型的 `push_back` 版本并不存在，编译器需要知道如何创建该函数，所以函数体必须放在 `.h` 文件中。 3. 在以下位置添加 `template <typename T>`： - 类定义之前。 - 类定义之外的每个函数体之前。 4. 适当地将 `int` 替换为 `T` 或 `const T&`，就像函数模板那样。 5. 在以下情况下将 `Vector` 替换为 `Vector<T>`： - 当它是 `Vector::` 的一部分时。 - 不在类内部时，例如： ```cpp std::ostream& operator<<(std::ostream& out, const Vector<T>& foo); Vector<T> somethingThatReturnsVector(); ``` 以下是将 `Vector` 转换为类模板的示例代码： ```cpp //Vector class: a variable-length array // -- from _C++ for Lazy Programmers_ #ifndef VECTOR_H #define VECTOR_H template <typename T> //Step #3 (a): add template <typename T> class Vector { public: class OutOfRange {}; //exception, for [] operators Vector () { contents_ = new T[0]; howMany_ = 0; }//#4: int -> T Vector (const Vector& other) { copy (other); } ~Vector () { delete [] contents_; } const Vector& operator= (const Vector& other) { if (contents_) delete [] contents_; copy (other); return *this; } bool operator== (const Vector& other) const; bool operator!= (const Vector& other) const { return !((*this) == other); } unsigned int size () const { return howMany_; } const T& operator[] (unsigned int index) const; //#4: int -> const T& T& operator[] (unsigned int index); void push_back (const T& newElement); //#4: int -> const T& void print (std::ostream&) const; private: T* contents_; //#4: int -> T unsigned int howMany_; void copy (const Vector& other); }; template <typename T> //#3b: add template <typename T> inline //#5b: Vector->Vector<T> std::ostream& operator<< (std::ostream& out, const Vector<T>& foo) { foo.print(out); return out; } //#2: move contents of vector.cpp into vector.h // (still contained in #ifndef) template <typename T> //#3b: add template <typename T> bool Vector<T>::operator==(const Vector& other) const //#5a: Vector::->Vector<T>:: { bool noDifferences = true; //quit if you find a difference or run out of elements for (unsigned int i = 0; i < size() && noDifferences; ++i) if ((*this)[i] != other[i]) noDifferences = false; return noDifferences; } ... #endif //VECTOR_H ``` 现在可以使用这个 `Vector` 模板来存储不同的基本类型。以下是使用字符串类型的 `Vector` 模板的示例： ```cpp //Example with a Vector of string // -- from _C++ for Lazy Programmers_ #include <iostream> #include <cassert> #include <string> #include "vector.h" using namespace std; int main () { //Setting up the band... Vector<string> FabFour; string names[] = { "John","Paul","George","Ringo" }; enum { NUM_BEATLES = 4 }; for (int i = 0; i < NUM_BEATLES; ++i) FabFour.push_back(names[i]); cout << "The Fab Four: " << FabFour << endl; //Trying other base types... Vector<int> V; for (int i = 1; i < 11; ++i) V.push_back(i); Vector<Vector<double>> Grid; return 0; } ``` #### 3. 调试类模板时的常见问题及解决方法 在使用类模板时，可能会遇到一些编译器报错，以下是常见问题及解决方法： - 编译器提示未编写类模板的某个成员函数，但实际上已经编写了。此时需要检查是否将所有内容都移到了 `.h` 文件中。 - 编译器提示类模板不是一种类型，可能是在变量声明时遗漏了 `<myBaseType>`。 - 编译器抱怨在声明 `Vector<Vector<int>> Grid;` 时使用了 `operator >>`，旧的编译器可能会有这个问题，解决方法是在两个 `>` 之间加一个空格：`Vector<Vector<int> > Grid;` #### 4. 不常见的类模板 类模板有一些不常见的用法，例如可以有多个 `typename`，也可以让模板参数是一个值。 ##### 4.1 多个 typename 的类模板 以下是一个简化的 `pair` 类模板示例，它允许指定两种类型： ```cpp template <typename S, typename T> struct pair { pair(); pair(const S& s, const T& t); pair(const pair& other); //operators =, ==, !=, and others S first; T second; }; int main () { pair<int,string> P (1, "C++ for Lazy Programmers"); cout << "The number " << P.first << " C++ text EVER is " << P.second << "!\n"; return 0; }; ``` ##### 4.2 模板参数为值的类模板 以下是一个允许指定整数的类模板示例： ```cpp template <int SIZE> class Stack //Stack of chars with at most SIZE elements { public: ... bool full () const { return howMany_ >= SIZE; } private: char contents_[SIZE]; int howMany_; }; int main (int argc, char** argv) { Stack<30> S; ... } ``` 下面是相关的练习题： 1. 使用前面的 `Queue` 类模板，创建一个子类 `PriorityQueue`，其中每个项目都有一个关联的优先级。当入队一个新项时，它会排在队列中所有优先级较低的项之前，这里可能会用到 `pair