C++哈希表Iterator中begin()函数的工作原理及初始化逻辑问询

问题背景 #

我正在用C++实现自定义哈希表，在理解与迭代器（Iterator）配合使用的begin()函数时遇到了障碍，具体疑惑点：

1. begin()在初始化迭代器中的作用；
2. begin()如何将迭代器设置为指向哈希表的第一个元素。

已尝试分析begin()函数逻辑、尝试不同迭代器初始化方式、查阅文档及示例，但未找到清晰解释。

相关代码片段 #

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int hash_code(const string& str) {
    int h = 0;
    for (int i = 0; i < str.length(); i++) {
        h = 31 * h + str[i];
    }
    return h;
}

class HashTable;

class Node {
private:
    string data;
    Node* next;

    friend class HashTable;
    friend class Iterator;
};

class Iterator {
public:
    string get() const;
    void next();
    bool equals(const Iterator& other) const;

private:
    const HashTable* container;
    int bucket_index;
    Node* current;

    friend class HashTable;
};

class HashTable {
public:
    HashTable(int nbuckets);
    int count(const string& x);
    void insert(const string& x);
    void erase(const string& x);
    Iterator begin() const;
    Iterator end() const;
    int size() const;

private:
    vector<Node*> buckets;
    int current_size;

    friend class Iterator;
};

HashTable::HashTable(int nbuckets) {
    for (int i = 0; i < nbuckets; i++) {
        buckets.push_back(nullptr);
    }
    current_size = 0;
}

int HashTable::count(const string& x) {
    int h = hash_code(x);
    h = h % buckets.size();
    if (h < 0) {
        h += buckets.size();
    }

    Node* current = buckets[h];
    while (current != nullptr) {
        if (current->data == x) {
            return 1;
        }
        current = current->next;
    }
    return 0;
}

void HashTable::insert(const string& x) {
    int h = hash_code(x);
    h = h % buckets.size();
    if (h < 0) {
        h += buckets.size();
    }

    Node* current = buckets[h];
    while (current != nullptr) {
        if (current->data == x) {
            return;
        }
        current = current->next;
    }
    Node* new_node = new Node;
    new_node->data = x;
    new_node->next = buckets[h];
    buckets[h] = new_node;
    current_size++;
}

void HashTable::erase(const string& x) {
    int h = hash_code(x);
    h = h % buckets.size();
    if (h < 0) {
        h += buckets.size();
    }

    Node* current = buckets[h];
    Node* previous = nullptr;
    while (current != nullptr) {
        if (current->data == x) {
            if (previous == nullptr) {
                buckets[h] = current->next;
            } else {
                previous->next = current->next;
            }
            delete current;
            current_size--;
            return;
        }
        previous = current;
        current = current->next;
    }
}

int HashTable::size() const {
    return current_size;
}

string Iterator::get() const {
    return current->data;
}

bool Iterator::equals(const Iterator& other) const {
    return current == other.current;
}

void Iterator::next() {
    if (bucket_index >= 0 && current->next != nullptr) {
        current = current->next;
    } else {
        do {
            bucket_index++;
        } while (bucket_index < container->buckets.size() && container->buckets[bucket_index] == nullptr);

        if (bucket_index < container->buckets.size()) {
            current = container->buckets[bucket_index];
        } else {
            current = nullptr;
        }
    }
}

Iterator HashTable::begin() const {
    Iterator iter;
    iter.current = nullptr;
    iter.bucket_index = -1;
    iter.container = this;
    iter.next();
    return iter;
}

Iterator HashTable::end() const {
    Iterator iter;
    iter.current = nullptr;
    iter.bucket_index = buckets.size();
    iter.container = this;
    return iter;
}

疑惑解答 #

1. begin()在初始化迭代器中的作用 #

begin()的核心作用是生成指向哈希表第一个有效元素的迭代器，作为遍历的起始标记。它负责：

• 初始化迭代器的基础状态：绑定当前哈希表实例（container = this），设置初始桶索引为-1、当前节点为空。
• 触发迭代器的首次定位操作（调用next()），让迭代器自动找到哈希表中第一个存在元素的位置。
• 返回初始化完成的迭代器，供外部用于遍历（从第一个元素开始，不断调用next()直到等于end()）。

2. begin()如何将迭代器设置为指向哈希表的第一个元素 #

begin()通过以下步骤完成首个元素的定位：

1. 初始化迭代器基础状态：创建Iterator对象后，先把current设为nullptr，bucket_index设为-1（表示还未开始遍历任何桶），同时让迭代器绑定当前哈希表实例。
2. 调用next()触发首次查找：
   • 此时bucket_index是-1，不满足next()中“当前桶存在下一个节点”的条件，进入else分支。
   • 执行do-while循环：从bucket_index = -1自增到0，开始检查每个桶是否为空。如果当前桶是空的，就继续自增索引，直到找到第一个非空的桶。
   • 找到非空桶后，将current指向该桶的头节点（也就是按桶顺序的第一个有效元素）；如果所有桶都为空，current保持nullptr，此时这个迭代器和end()返回的迭代器状态一致。

内容的提问来源于stack exchange，提问作者Mohammed Mogeab Ahmed Al-hajj