7
\$\begingroup\$

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;
}
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.