c++ - 用 C++ 编写 Stack 类的各种实现

Question

我最近参加了 Java 数据结构类(class)，我可以用 Java 编写各种结构并以各种方式轻松实现它们。我目前正在将这些知识转移到有点不同的 C++ 世界。我目前为 Stack 接口(interface)编写了一个头文件(就像您在 Java 中为 Stack 编写接口(interface)一样)，我想以各种方式(链表、数组、 vector 等)实现它，这样我就可以掌握实现的想法任何语言的结构。我目前在使用 C++ 时遇到的问题是理解在我的 Stack 和引用 (E&) 中使用指针的概念，并确保我可以编写 Stack.h 的各种源代码实现。这是我当前的堆栈 header ...

/*
 * File: stack.h
 * -------------
 * Interface file of the Stack class. Follows a last-in/ first-out (LIFO) order. Includes contracts for the method bodies of Stack.
*/

#ifndef _stack_h
#define _stack_h

/*
 * declaration of Stack using template with type E for any data type or object using the Stack structure.
 *
 */

  template <typename E>
  class Stack {

    public: 

    //constructor blank
    Stack();

    //destructor
    ~Stack();

    //constructor with integer size
    Stack(int);

    //number of items in stack.
    int size() const;

    //is stack empty?
    bool empty() const;

    //top element of stack
    const E& top() const throw(StackEmpty);

    //push e onto the stack.
    void push(const E& e);

    //remove top element from stack
    void pop() throw(StackEmpty);

    //pop and return.
    E popReturn();

    //returns a string form of stack.
    std::string toString();
};

// Error exception
class StackEmpty : public RuntimeException {
    public:
       StackEmpty(const std::string& err) : RuntimeException(err) {}
};

#endif

抱歉格式化! :) 目前我正在研究这个堆栈的数组和链表实现。我知道头文件会在它包含的文件之间创建链接。我想确保在创建用于测试的堆栈时，我可以使用我用这个头文件编写的两个实现。我也不确定是否应该使用关键字 virtual 来制作官方界面。我知道在 Java 中，当您为 Stack 声明一个实现时，您将使用

Stack test = new ArrayStack();

C++使用全局化的头文件和使用这个Stack的不同实现是不是一样的？此外，这段代码是从 C++ 的数据结构书中挖掘出来的，但遗憾的是，作者并没有说明是否要将这些接口(interface)作为头文件，以及在何处包含空堆栈的错误检查异常。我只是把它放在这个文件中。 C++ 对我来说并不是一门很棒的语言，但我知道如果我想构建更大的项目，如编译器、游戏、音频/视频播放器、操作系统，并为一种新语言编写 IDE，那么掌握 C++ 和 C 语言很重要。如果可能的话，请让我了解我目前的情况，我将不胜感激。如果有人也能解释 C++ 中的指针和引用，我会非常接受这些知识。我相信 E& 是一个引用，但书中没有具体说明。谢谢你! :)

附言这就是我认为对于 C++ 使用头文件的不同实现会起作用的方法....

#include "stack.h"

Stack test = new ArrayStack();
Stack test2 = new LinkedStack();

Answer 1

您的代码有很多问题。

template <typename E>

除非你真的需要运行时多态性(在这种情况下你几乎肯定不需要)你想传递你将用作模板参数的底层存储而不是使用继承:

template <typename E, typename Container = std::vector<E> >

这样，您可以避免(例如)对真正不需要的基本操作调用虚函数。

//constructor blank
Stack();

您可能根本不需要声明此默认构造函数。 (请参阅下面关于您声明的其他构造函数的评论)。

//destructor
~Stack();

如果您打算像您建议的那样使用 Stack 作为基类，那么您需要将析构函数设为 virtual。

//constructor with integer size
Stack(int);

除非您真的想使用固定大小的底层容器，否则没有必要在此处指定大小。如果你想指定一个大小，我可能会提供一个默认值(这是使前面的默认构造函数声明无关紧要的一部分)所以你最终会得到这样的东西: Stack(int size = 20) ;

//top element of stack
const E& top() const throw(StackEmpty);

这很糟糕。像您的 throw(StackEmpty) 这样的动态异常规范被证明是一个错误。它们已经被弃用一段时间了，并且可能很快就会消失¹。此外，如果您打算使用继承，那么这些接口(interface)函数中的大多数可能应该是虚拟的(可能是纯虚拟的)。

//push e onto the stack.
void push(const E& e);

这没问题，但如果您想充分利用 C++，您可能还想添加一个采用右值引用的重载。

//remove top element from stack
void pop() throw(StackEmpty);

这个动态异常规范和上面有同样的问题。

//pop and return.
E popReturn();

这有一个严重的设计缺陷——如果 E 的复制构造函数抛出异常，它将(不可避免地)破坏数据。有两种众所周知的方法可以避免这个问题。一种是直接消除它并要求用户编写如下代码:

Foo f = myStack.top();
myStack.pop();

这样，如果复制构造函数抛出异常，myStack.pop() 永远不会执行。另一种众所周知的可能性是这样的:

void pop(E &dest) { 
    dest = top();
    pop();
}

无论哪种方式，我们最终都会得到异常安全的代码——它要么完成(并且值从栈顶传输到目的地)要么完全失败(并且数据保留在栈中)，所以没有效果。

//returns a string form of stack.
std::string toString();

在 C++ 中，这通常被命名为 to_string。

// Error exception
class StackEmpty : public RuntimeException {
    public:
       StackEmpty(const std::string& err) : RuntimeException(err) {}
};

标准已经定义了std::runtime_error。除非/除非您对 C++ 足够了解以确切知道您想要以不同的方式执行哪些操作，否则最好使用它。

另请注意:如果您采纳最初的建议并使您的堆栈成为纯模板而不是尝试使用继承，那么许多其他评论将变得毫无意义。

最后，C++ 的 stack 类可以更像这样结束:

template <class T, class C = std::vector<T> >
class Stack { 
    C data;
public:
    void push(T const &t) { 
        data.push_back(t);
    }

    T top() const {  return data.back(); }

    void pop(T &d) { 
        if (data.empty())
            throw std::runtime_error("Attempt to pop empty stack");
        d = data.top();
        data.pop_back();
    }

    bool empty() const { return data.empty(); }
};

您已表示要使用不同的底层容器对其进行测试。以下是使用三个标准容器的方法:

#include "stack.h"
#include <vector>
#include <list>
#include <deque>
...
// These two are equivalent:
Stack<int, std::vector<int>> vs;
Stack<int> vs1;

Stack<int, std::list<int>> ls;  
Stack<int, std::deque<int>> ds;

---

<支持> 1. 是的，Java 几乎完整地复制了这个错误，然后通过添加紧密耦合设法使它变得更糟，这破坏了异常处理的最大优势之一。我只能说:那很痛；不要再这样做了。