Here are some things that may help you improve your program.
Use include
guards instead of #pragma once
The use of #pragma once
, while common, is not standard C++. Use include guards instead as:
#ifndef DISJOINT_SET_HPP
#define DISJOINT_SET_HPP
// your header here
#endif // DISJOINT_SET_HPP
See SF.8 for details.
Don't mark every data member with public
or private
If you are uniquely writing in this style, then almost by definition, everyone else who uses your code will find it that much more difficult to read and understand your code. Inserting unnecessary keywords adds visual clutter rather than clarity.
Avoid unneeded casts
The getRepr()
function is declared as returning type S
, but the return statement within it is this:
return static_cast<std::size_t>(parent);
That makes no sense at all because parent
is already declared to be of type S
.
Give better messages in exceptions
In the checkStructure()
function, the code checks to verify a large number of predicates, collapsing them all into a single bool
. If any of the conditions fails, the caller gets only the vague "Assertion error" message. At this point, the structure is somehow corrupted and no longer usable, which represents a rather catastrophic failure of the structure. For that reason, I'd suggest either writing each clause as a separate throw
with a clear message or using old-fashioned assert
which is likely to be the better choice in this case.
Move error checking to compile time where practical
The constructor currently looks like this:
public: explicit DisjointSet(S numElems) :
numSets(numElems) {
if (numElems < 0)
throw std::domain_error("Number of elements must be non-negative");
if (!safeLessEquals(numElems, SIZE_MAX))
throw std::length_error("Number of elements too large");
nodes.reserve(static_cast<std::size_t>(numElems));
for (S i = 0; i < numElems; i++)
nodes.push_back(Node{i, 0, 1});
}
However, if we look carefully at this, both of the checks could actually be done at compile-time instead. That suggests that the use of C++20 requires
or C++11 enable_if
. Here I'm using the C++14 enable_if_t
which is just a convenience function:
template <typename S,
typename = std::enable_if_t<std::is_integral<S>::value>,
typename = std::enable_if_t<std::is_unsigned<S>::value>
>
class DisjointSet final {
Now if we attempt to create something invalid like DisjoinSet<float> ds(3);
we get a much clearer error versus a relatively obscure and unhelpful error pointing to safeLessEquals
or checkStructure
.
Provide sensible default values where practical
The Node
structure is only used internally to the DisjointSet
class and is only created in the constructor of DisjointSet
. For that reason, I'd suggest declaring it like this:
struct Node final {
mutable S parent;
signed char rank = 0;
S size = 1;
Node& operator++() { ++parent; return *this; }
};
If you're wondering about the operator, that's part of the next suggestion.
Use standard library functions where practical
I would suggest rewriting the constructor for DisjointSet
like this:
explicit DisjointSet(S numElems)
: numSets(numElems)
, nodes(numElems)
{
std::iota(nodes.begin(), nodes.end(), Node{0});
}
Note that this also assumes that we declare numSets
before nodes
so as not to confuse the reader. (Elements are initialized in declaration order.) In C++20, one could likely use a range
and make this even more efficient.
Don't hide a loop return condition
The getRepr()
function has a while(true)
, but actually returns when the parent and grandparent are the same. I'd suggest rewriting that so that the looping exit condition is part of the loop rather than hidden within the body. For example, one way to rewrite would be this:
S getRepr(S elemIndex) const {
while (nodes.at(elemIndex).parent != nodes.at(nodes.at(elemIndex).parent).parent) {
auto parent = nodes.at(elemIndex).parent;
// set parent = grandparent
nodes.at(elemIndex).parent = nodes.at(parent).parent;
elemIndex = parent;
}
return nodes.at(elemIndex).parent;
}