21xrx.com
2025-03-21 19:52:03 Friday
文章检索 我的文章 写文章
C++类模板经典例题
2023-06-27 22:55:59 深夜i     10     0
C++ 类模板 经典 例题

C++类模板经典例题是C++编程语言中非常重要的一个知识点。类模板是一种可以生成多个具体实例的类描述。其基本思想是通过使用参数模板生成不同的具体类型，从而避免代码重复，提高代码的可重用性。在这篇文章中，我们将对C++类模板经典例题进行介绍，帮助大家更好地理解该知识点。

C++类模板经典例题可以分为两类：第一类是常见的实现缓存的队列；第二类是实现经典的二叉查找树。下面我们将逐一介绍这两类例题的具体实现方法。

第一类例题实现缓存的队列。该例题需要我们实现一个有序队列，其中元素可以根据其优先级进行排序，并且具有缓存的功能。缓存的功能是指，如果有一个元素已经存在于队列中，则将其移动到队列的首部，而不是向队列中添加一个新元素。在这种情况下，需删除队列末尾的元素。

代码的实现方法如下：

c++
template <typename T>
class Queue {
private:
  struct Node {
    T data;
    Node *next;
  };
  Node *head;
  Node *tail;
  std::map<T, Node *> hmap;
  const int kSize;
public:
  Queue(int size) : kSize(size)
    head = nullptr;
    tail = nullptr;
  
  bool add(const T &data) {
    auto iter = hmap.find(data);
    if (iter != hmap.end()) {
      auto node = iter->second;
      if (node == head)
        return true;
      
      if (node == tail)
        tail = node->next;
      
      auto prev = head;
      while (prev->next != node)
        prev = prev->next;
      
      prev->next = node->next;
      node->next = head;
      head = node;
      return true;
    }
    if (hmap.size() == kSize) {
      hmap.erase(tail->data);
      auto to_delete = tail;
      tail = tail->next;
      delete to_delete;
    }
    auto node = new Node nullptr ;
    if (!head)
      head = node;
      tail = node;
    
    else
      node->next = head;
      head = node;
    
    hmap[data] = node;
    return true;
  }
};

第二类例题实现经典的二叉查找树。该例题需要我们实现一个二叉查找树，可以进行插入、查找和删除等操作，并且可以对查找结果进行统计。在该例题中，可以使用模板参数来指定元素类型的比较函数和统计函数。

代码实现方法如下：

c++
template <typename T, typename TCompare = std::less<T>, typename TStat = int (*)(const T &)>
class BST {
private:
struct Node {
T value;
Node *left;
Node *right;
int count;
Node(T v) : value(v), left(nullptr), right(nullptr), count(1) {}
};
Node *root;
TCompare compare_func;
TStat stat_func;
Node *insert(Node *node, const T &value) {
if (!node) {
return new Node(value);
}
if (compare_func(value, node->value)) {
node->left = insert(node->left, value);
}
else {
node->right = insert(node->right, value);
}
node->count = 1 + (node->left ? node->left->count : 0) + (node->right ? node->right->count : 0);
return node;
}
Node *search(Node *node, const T &value) const {
if (!node || !compare_func(node->value, value) && !compare_func(value, node->value))
return node;
if (compare_func(value, node->value)) {
return search(node->left, value);
}
return search(node->right, value);
}
Node *getmin(Node *node) const {
while (node && node->left)
node = node->left;
return node;
}
Node *remove_min(Node *node) {
if (!node->left)
return node->right;
node->left = remove_min(node->left);
node->count = 1 + (node->left ? node->left->count : 0) + (node->right ? node->right->count : 0);
return node;
}
Node *remove(Node *node, const T &value) {
if (!node)
return nullptr;
if (compare_func(value, node->value)) {
node->left = remove(node->left, value);
}
else if (compare_func(node->value, value)) {
node->right = remove(node->right, value);
}
else {
Node *left = node->left;
Node *right = node->right;
delete node;
if (!right)
return left;
Node *min = getmin(right);
min->right = remove_min(right);
min->left = left;
min->count = 1 + (min->left ? min->left->count : 0) + (min->right ? min->right->count : 0);
return min;
}
node->count = 1 + (node->left ? node->left->count : 0) + (node->right ? node->right->count : 0);
return node;
}
public:
BST() : root(nullptr), compare_func(TCompare()), stat_func(TStat()) {}
BST(TCompare comp) : root(nullptr), compare_func(comp), stat_func(TStat()) {}
BST(TCompare comp, TStat stat) : root(nullptr), compare_func(comp), stat_func(stat) {}
virtual ~BST() {
clear(root);
}
bool insert(const T &value) {
root = insert(root, value);
return true;
}
bool erase(const T &value) {
if (search(value) == nullptr)
return false;
root = remove(root, value);
return true;
}
Node *search(const T &value) const {
return search(root, value);
}
Node *getmin() const {
return getmin(root);
}
Node *getmax() const {
Node *node = root;
while (node && node->right)
node = node->right;
return node;
}
int count(const T &value) const {
Node *node = search(root, value);
return node ? node->count : 0;
}
void clear() {
clear(root);
root = nullptr;
}
void clear(Node *node) {
if (node) {
clear(node->left);
clear(node->right);
delete node;
}
}
};

综上所述，C++类模板经典例题是C++编程语言中非常重要的一部分。通过学习和实践，大家将能够更好地掌握类模板的使用技巧，提高代码的重用性和可维护性。希望本篇文章对大家有所帮助，有兴趣的读者可以进行实验和实践。

  
  
下一篇: C++命名空间std

评论区