C背景转C++：将UnionFind对象推入vector相关技术问题咨询

嘿，看你正在从C转C++，自己动手实现并查集——这可是练手数据结构的好选择！先把你贴的代码整理清楚，咱们聊聊这里面的问题和改进方向：

你当前的UnionFind代码（补全了截断的部分） #

class UnionFind {
private:
    int count;
    UnionFind* parent;
    int val;
public:
    UnionFind(int _val) : count(1), parent(this), val(_val) {
        printf("UnionFind(): parent=%p this=%p\n", parent, this);
    }
    ~UnionFind() {
        printf("~UnionFind()\n");
    }
    int getcount() {
        if (parent == this) return count;
        return Find()->count;
    }
    int getval() { return val; }
    // 你截断的应该是Find和Union相关函数，先假设未实现
    UnionFind* Find();
    void unite(UnionFind* other);
};

先说说当前设计的几个小问题 #

• 内存管理风险高：每个元素对应一个独立的UnionFind对象，用指针维护父节点关系，后续合并、析构时很容易出现内存泄漏或者重复释放的问题（比如合并后原节点的父指针指向其他对象，手动delete时可能误删）。
• 性能低效：单个对象的额外开销（比如虚表、内存对齐）在元素数量多的时候会被放大，远不如数组式实现紧凑高效。
• 核心逻辑缺失：Find()函数（路径压缩的核心）还没实现，这可是并查集能做到近似O(1)操作的关键。

推荐的标准实现（数组+vector版） #

这是行业内最常用的并查集实现方式，既高效又容易维护，也更贴合C++的容器使用习惯：

#include <vector>
#include <iostream>

class UnionFind {
private:
    std::vector<int> parent;  // 存储每个元素的父节点索引
    std::vector<int> size;    // 存储每个根节点对应的集合大小（用于按秩合并）
    int count;                // 当前连通分量的总数

public:
    // 构造函数：初始化n个独立的元素
    UnionFind(int n) : count(n) {
        parent.resize(n);
        size.resize(n, 1);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;  // 每个元素初始父节点是自己
        }
    }

    // 查找根节点，同时执行路径压缩（核心优化）
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // 直接把当前节点挂到根节点上，减少后续查找路径
        }
        return parent[x];
    }

    // 合并两个元素所在的集合
    void unite(int x, int y) {
        int root_x = find(x);
        int root_y = find(y);

        if (root_x == root_y) return;  // 已经在同一个集合，无需合并

        // 按秩合并：把小集合合并到大集合下，保持树的平衡
        if (size[root_x] < size[root_y]) {
            std::swap(root_x, root_y);
        }
        parent[root_y] = root_x;
        size[root_x] += size[root_y];
        count--;  // 连通分量数减一
    }

    // 获取当前连通分量的数量
    int getCount() const {
        return count;
    }

    // 判断两个元素是否属于同一个连通分量
    bool isConnected(int x, int y) {
        return find(x) == find(y);
    }
};

// 简单测试示例
int main() {
    UnionFind uf(5);
    uf.unite(0, 1);
    uf.unite(2, 3);
    std::cout << "当前连通分量数：" << uf.getCount() << std::endl; // 输出3
    std::cout << "0和1是否连通：" << uf.isConnected(0, 1) << std::endl; // 输出1（true）
    std::cout << "0和2是否连通：" << uf.isConnected(0, 2) << std::endl; // 输出0（false）
    uf.unite(1, 2);
    std::cout << "合并后连通分量数：" << uf.getCount() << std::endl; // 输出2
    return 0;
}

如果你坚持想用单个对象的方式（不推荐，但可以补全） #

如果只是想尝试这种面向对象的写法，那至少要补全Find()和合并函数，同时注意内存管理：

#include <iostream>
#include <algorithm> // 用于swap

class UnionFind {
private:
    int count;
    UnionFind* parent;
    int val;
public:
    UnionFind(int _val) : count(1), parent(this), val(_val) {
        printf("UnionFind(): parent=%p this=%p\n", parent, this);
    }
    ~UnionFind() {
        printf("~UnionFind()\n");
    }

    // 带路径压缩的查找
    UnionFind* Find() {
        if (parent != this) {
            parent = parent->Find(); // 路径压缩，直接指向根节点
        }
        return parent;
    }

    int getcount() {
        return Find()->count;
    }

    int getval() { return val; }

    // 合并两个集合
    void unite(UnionFind* other) {
        UnionFind* root_this = Find();
        UnionFind* root_other = other->Find();

        if (root_this == root_other) return;

        // 按大小合并，保持树的平衡
        if (root_this->count < root_other->count) {
            std::swap(root_this, root_other);
        }
        root_other->parent = root_this;
        root_this->count += root_other->count;
    }
};

// 测试示例
int main() {
    UnionFind* u1 = new UnionFind(1);
    UnionFind* u2 = new UnionFind(2);
    UnionFind* u3 = new UnionFind(3);

    u1->unite(u2);
    std::cout << "u1的集合大小：" << u1->getcount() << std::endl; // 输出2
    u2->unite(u3);
    std::cout << "u1的集合大小：" << u1->getcount() << std::endl; // 输出3

    // 记得手动释放内存，避免泄漏
    delete u1;
    delete u2;
    delete u3;
    return 0;
}

不过再次提醒：这种单个对象的写法在实际项目中几乎不会用到，内存管理太容易出问题，性能也不如数组版。作为C++新手，优先掌握数组+vector的标准实现更有价值。

内容的提问来源于stack exchange，提问作者learnlearnlearn