Union-Find in C++

Question

A few days ago I start learning C++. This code is a simple Union-Find data structure.

Questions:

• Why can't I use const union_find<T> &uf instead of union_find<T> &uf?
• Is it possible to replace union_find<T> with something like self<T> (self refers to current class)?
• Did I use references instead of pointers in the right places?

union_find.cpp:

template<class T>
class union_find {
public:
  union_find(const T &obj) {
    _parent = this;
    _obj = obj;
  }

  void merge(union_find<T> &uf) {
    _parent = &uf;
  }

  T find() {
    union_find<T> *root = _parent;

    while (root != root->_parent) {
      root = root->_parent;
    }

    return root->_obj;
  }
private:
  T _obj;
  union_find<T> *_parent;
};

main.cpp:

#include <iostream>
#include <string>
#include "union_find.cpp"

int main() {
  union_find<std::string> foo("foo");
  union_find<std::string> bar("bar");
  union_find<std::string> baz("baz");
  bar.merge(foo);

  std::cout << foo.find() << std::endl; // foo
  std::cout << bar.find() << std::endl; // foo
  std::cout << baz.find() << std::endl; // baz

  return 0;
}

Answer 1

Welcome to Code Review.

1. union_find.cpp looks like a header-only library. It's thus strange its not named like a header.

2. Make all single-argument-constructors explicit unless you really want to see them used for implicit conversion.
   In our case, you really don't.

3. class union_find should be un-copyable, un-movable and not assignable.

   union_find(union_find&&) = delete;
   union_find(const union_find&) = delete;
   void operator=(union_find&&) = delete;
   void operator=(const union_find&) = delete;
   

4. Consider implementing path-compression in find(). See your reference.

5. Consider returning a reference from find(). No need to make the choice on copying for the caller.

6. If you call merge() on a non-root-node, it leaves the rest of its component behind.

7. Congratulations on not writing using namespace std;.

8. Avoid std::endl unless you really need the explicit std::flush. In which case you probably want to be explicit...

9. return 0; is implicit for main().

Your questions:

1. You cannot use a constant reference there because you are assigning to the member-pointer to non-const.

2. There is nothing like self in C++. Though at least there is no need to write the template-argument-list, as you can use the injected class-name.
   As an example:

   void merge(union_find &uf) // removed <T> from union_find
   

3. Yes, you made the right choices between references and pointers. You just missed a place for using a reference instead of a copy.