Let’s continue our journey towards creating a general library from several algorithms, but today, let’s take a step back from Hacker Rank (since it doesn’t support C++20 yet) and see what we can do to improve our code using the Concept feature
Let’s continue our scenario where I’m a software engineer who has already developed a library of searching algorithms. Suppose we will go through a sprint or two without any new feature requests, and we have now taken on the task of refactoring and improving the quality of our code. To prevent bugs that might arise from improper usage of the library, we’ll be using “concepts,” a feature introduced in the C++20 standard
Express semantic requirements
Let see pacman_bfs_dfs_example1.cpp.
In namespace example_1, the user has been using std::pair<int,int> as the type for their search algorithm, and it seems to be working flawlessly so far.
using example_state_t = std::pair<int,int>;
using example_node_t = a_star_search::Node<example_state_t>::node_ptr_type;
void example_solve ( example_state_t const& start, example_state_t const& goal ) {
auto example_get_neighbors =
[]( example_state_t const& s ) -> std::vector<example_state_t> {return {
{s.first-1, s.second},
{s.first, s.second-1},
{s.first+1, s.second},
{s.first, s.second+1},
{s.first+1, s.second+1},
{s.first-1, s.second-1}
};};
std::vector<example_state_t> result_path, explored_nodes;
auto is_solved = a_star_search::bfs_search<example_state_t, decltype(example_get_neighbors)>
(start, goal, std::move(example_get_neighbors), std::back_inserter(result_path), std::back_inserter(explored_nodes) );
std::cout << std::boolalpha << "Task is solved: " << is_solved << "(" << result_path.size() << ")" << std::endl;
for (const auto& p : result_path )
std::cout << '[' << p.first << ',' << p.second << ']' << " ";
std::cout << std::endl << "Nodes visited " << explored_nodes.size() << std::endl;
}
Output:
Task is solved: true(5)
[5,5] [4,4] [3,3] [2,2] [1,1]
Nodes visited 60
However, if some pointer is used as type for state like in namespace example_2
using example_state_t = std::shared_ptr<std::pair<int,int>>;
using example_node_t = a_star_search::Node<example_state_t>::node_ptr_type;
void example_solve ( example_state_t const& start, example_state_t const& goal ) {
auto example_get_neighbors =
[]( example_state_t const& s ) -> std::vector<example_state_t> {return {
std::make_shared<std::pair<int,int>>( std::make_pair(s->first-1, s->second) ),
std::make_shared<std::pair<int,int>>( std::make_pair(s->first, s->second-1) ),
std::make_shared<std::pair<int,int>>( std::make_pair(s->first+1, s->second) ),
std::make_shared<std::pair<int,int>>( std::make_pair(s->first, s->second+1) ),
std::make_shared<std::pair<int,int>>( std::make_pair(s->first+1, s->second+1) ),
std::make_shared<std::pair<int,int>>( std::make_pair(s->first-1, s->second-1) )
};
};
std::vector<example_state_t> result_path, explored_nodes;
auto is_solved = a_star_search::bfs_search<example_state_t, decltype(example_get_neighbors)>
(start, goal, std::move(example_get_neighbors), std::back_inserter(result_path), std::back_inserter(explored_nodes) );
std::cout << std::boolalpha << "Task is solved: " << is_solved << "(" << result_path.size() << ")" << std::endl;
for (const auto& p : result_path )
std::cout << '[' << p->first << ',' << p->second << ']' << " ";
std::cout << std::endl << "Nodes visited " << explored_nodes.size() << std::endl;
}
The program will never finish due to an obvious reason - example_get_neighbors cannot create the same shared pointer that was set as goal.
So, we decided to create a concept that describes the intentions of the algorithm (See here).
Since the standard library doesn’t have one, we created a type_trait called NotSmartPointer and used it in a concept StateSpaceEl
namespace a_star_helper {
template <typename T> struct is_shared_ptr : std::false_type {};
template <typename T> struct is_shared_ptr<std::shared_ptr<T>> : std::true_type {};
template <typename T> concept NotSharedPtr = !is_shared_ptr<T>::value;
template <typename T> struct is_weak_ptr : std::false_type {};
template <typename T> struct is_weak_ptr<std::weak_ptr<T>> : std::true_type {};
template <typename T> concept NotWeakPtr = !is_weak_ptr<T>::value;
template <typename T> struct is_unique_ptr : std::false_type {};
template <typename T> struct is_unique_ptr<std::unique_ptr<T>> : std::true_type {};
template <typename T> concept NotUniquePtr = !is_unique_ptr<T>::value;
template <typename T> concept NotSmartPointer = NotSharedPtr<T> && NotWeakPtr<T> && NotUniquePtr<T>;
}
template<typename T>
concept StateSpaceEl = std::totally_ordered<T> && NotSmartPointer<T> && !std::is_pointer_v<T>;
As a result, any attempt to use a pointer type as the state for the algorithm is prevented with an elegant compilation error.
<source>:208:59: error: template constraint failure for 'template<class TState> requires StateSpaceEl<TState> class a_star_search::Node'
208 | using example_node_t = a_star_search::Node<example_state_t>::node_ptr_type;
| ^
<source>:208:59: note: constraints not satisfied
<source>: In substitution of 'template<class TState> requires StateSpaceEl<TState> class a_star_search::Node [with TState = std::shared_ptr<std::pair<int, int> >]':
<source>:208:59: required from here
<source>:14:35: required for the satisfaction of 'NotSharedPtr<T>' [with T = std::shared_ptr<std::pair<int, int> >]
<source>:24:35: required for the satisfaction of 'NotSmartPointer<T>' [with T = std::shared_ptr<std::pair<int, int> >]
<source>:32:9: required for the satisfaction of 'StateSpaceEl<TState>' [with TState = std::shared_ptr<std::pair<int, int> >]
<source>:14:50: note: the expression '!(a_star_helper::is_shared_ptr<T>::value) [with T = std::shared_ptr<std::pair<int, int> >]' evaluated to 'false'
14 | template <typename T> concept NotSharedPtr = !is_shared_ptr<T>::value;
| ^~~~~~~~~~~~~~~~~~~~~~~~
Improve compiler error messages
Another great feature of concepts is their ability to generate improved error messages.
For example, the code from namespace example_1 in example2 results in a confusing and unclear error message.
namespace example_1 {
using example_state_t = std::pair<int,int>;
using example_node_t = a_star_search::Node<example_state_t>::node_ptr_type;
void example_solve ( example_state_t const& start, example_state_t const& goal ) {
auto example_get_neighbors =
[]( int const& s ) -> std::vector<int> {return {1,2,3};};
std::vector<example_state_t> result_path, explored_nodes;
auto is_solved = a_star_search::bfs_search<example_state_t, decltype(example_get_neighbors)>
(start, goal, std::move(example_get_neighbors), std::back_inserter(result_path), std::back_inserter(explored_nodes) );
std::cout << std::boolalpha << "Task is solved: " << is_solved << "(" << result_path.size() << ")" << std::endl;
for (const auto& p : result_path )
std::cout << '[' << p.first << ',' << p.second << ']' << " ";
std::cout << std::endl << "Nodes visited " << explored_nodes.size() << std::endl;
}
} //namespace example_1
...
<source>: In instantiation of 'void a_star_search::NodeVisitor<TState, TContainer, FGetNeighbors>::visit_neighbors(const std::shared_ptr<a_star_search::Node<TState> >&) [with TState = std::pair<int, int>; TContainer = std::queue<std::shared_ptr<a_star_search::Node<std::pair<int, int> > >, std::deque<std::shared_ptr<a_star_search::Node<std::pair<int, int> > >, std::allocator<std::shared_ptr<a_star_search::Node<std::pair<int, int> > > > > >; FGetNeighbors = example_3::example_solve(const example_state_t&, const example_state_t&)::<lambda(const int&)>]':
<source>:132:37: required from 'bool a_star_search::a_star(const TState&, const TState&, TNodeVisitor&, TResultPathIterator, TExploredNodeIterator) [with TState = std::pair<int, int>; TNodeVisitor = NodeVisitor<std::pair<int, int>, std::queue<std::shared_ptr<Node<std::pair<int, int> > >, std::deque<std::shared_ptr<Node<std::pair<int, int> > >, std::allocator<std::shared_ptr<Node<std::pair<int, int> > > > > >, example_3::example_solve(const example_state_t&, const example_state_t&)::<lambda(const int&)> >; TResultPathIterator = std::back_insert_iterator<std::vector<std::pair<int, int> > >; TExploredNodeIterator = std::back_insert_iterator<std::vector<std::pair<int, int> > >]'
<source>:152:19: required from 'bool a_star_search::a_star_solve(const TState&, const TState&, const FGetNeighbors&, TResultPathIterator, TExploredNodeIterator) [with TContainer = std::queue<std::shared_ptr<Node<std::pair<int, int> > >, std::deque<std::shared_ptr<Node<std::pair<int, int> > >, std::allocator<std::shared_ptr<Node<std::pair<int, int> > > > > >; TState = std::pair<int, int>; FGetNeighbors = example_3::example_solve(const example_state_t&, const example_state_t&)::<lambda(const int&)>; TResultPathIterator = std::back_insert_iterator<std::vector<std::pair<int, int> > >; TExploredNodeIterator = std::back_insert_iterator<std::vector<std::pair<int, int> > >]'
<source>:170:9: required from 'bool a_star_search::bfs_search(const TState&, const TState&, const FGetNeighbors&, TResultPathIterator, TExploredNodeIterator) [with TState = std::pair<int, int>; FGetNeighbors = example_3::example_solve(const example_state_t&, const example_state_t&)::<lambda(const int&)>; TResultPathIterator = std::back_insert_iterator<std::vector<std::pair<int, int> > >; TExploredNodeIterator = std::back_insert_iterator<std::vector<std::pair<int, int> > >]'
<source>:247:9: required from here
<source>:88:55: error: no match for call to '(example_3::example_solve(const example_state_t&, const example_state_t&)::<lambda(const int&)>) (std::pair<int, int>&)'
88 | std::vector<TState> neighbors = get_neighbors_( current_node->state_ );
| ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
...
<source>:88:55: note: candidate: 'std::vector<int> (*)(const int&)' (conversion)
<source>:88:55: note: candidate expects 2 arguments, 2 provided
<source>:243:9: note: candidate: 'example_3::example_solve(const example_state_t&, const example_state_t&)::<lambda(const int&)>'
243 | []( int const& s ) -> std::vector<int> {return {1,2,3};};
| ^
<source>:243:9: note: no known conversion for argument 1 from 'std::pair<int, int>' to 'const int&'
By defining the concept GetNeighborsFunction for the get_neighbour_function, we can greatly improve the error messages generated by the compiler.
template <typename F, typename TState>
concept GetNeighborsFunction = std::regular_invocable<F, TState> &&
requires (F&& f, TState&& state) { {f(state)} -> std::same_as< std::vector<TState> >; };
...
<source>: In function 'void example_3::example_solve(const example_state_t&, const example_state_t&)':
<source>:251:9: error: no matching function for call to 'bfs_search<example_3::example_state_t, example_3::example_solve(const example_state_t&, const example_state_t&)::<lambda(const int&)> >(const example_3::example_state_t&, const example_3::example_state_t&, std::remove_reference<example_3::example_solve(const example_state_t&, const example_state_t&)::<lambda(const int&)>&>::type, std::back_insert_iterator<std::vector<std::pair<int, int> > >, std::back_insert_iterator<std::vector<std::pair<int, int> > >)'
250 | auto is_solved = a_star_search::bfs_search<example_state_t, decltype(example_get_neighbors)>
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
251 | (start, goal, std::move(example_get_neighbors), std::back_inserter(result_path), std::back_inserter(explored_nodes) );
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
<source>:172:6: note: candidate: 'template<class TState, class FGetNeighbors, class TResultPathIterator, class TExploredNodeIterator> requires GetNeighborsFunction<FGetNeighbors, TState> bool a_star_search::bfs_search(const TState&, const TState&, const FGetNeighbors&, TResultPathIterator, TExploredNodeIterator)'
172 | bool bfs_search ( TState const& start, TState const& goal, FGetNeighbors const& get_neighbors, TResultPathIterator result_path_it, TExploredNodeIterator explored_node_it ) {
| ^~~~~~~~~~
<source>:172:6: note: template argument deduction/substitution failed:
<source>:172:6: note: constraints not satisfied
Let also harden requiments for container used to store nodes that was not been visited yet.
template <typename Container>
concept OrderableContainer = requires (Container c, typename Container::value_type const& el) { c.push(el); c.pop();}
&& (requires (Container c) { {c.front()} -> std::convertible_to <typename Container::value_type>; }
|| requires (Container c) { {c.top()} -> std::convertible_to <typename Container::value_type>; });
Fixing bugs with concepts
We must remember that we are creating code for real-world production, which means that bugs can always appear. And so it happened - our programmers received a bug report stating that the DFS algorithm is unable to find a direct path from 0 to -5 on a line in example_3.
namespace example_1 {
using example_state_t = int;
using example_node_t = a_star_search::Node<example_state_t>::node_ptr_type;
void example_solve ( example_state_t const& start, example_state_t const& goal ) {
auto example_get_neighbors =
[]( example_state_t const& s ) -> std::vector<example_state_t> {return {s-1, s+1};};
std::vector<example_state_t> result_path, explored_nodes;
auto is_solved = a_star_search::dfs_search<example_state_t, decltype(example_get_neighbors)>
(start, goal, std::move(example_get_neighbors), std::back_inserter(result_path), std::back_inserter(explored_nodes) );
std::cout << std::boolalpha << "Task is solved: " << is_solved << "(" << result_path.size() << ")" << std::endl;
for (const auto& p : result_path )
std::cout << p << " ";
std::cout << std::endl << "Nodes visited " << explored_nodes.size() << std::endl;
}
} //namespace example_1
Program never finishes. But was the algorithm implementation really wrong? Surprisingly, no. The behavior of the algorithm was correct - it was exploring the first positive branch before moving on to the negative one. However, for the int data type, this approach was taking too long.
Let look on another example with type signed char that works much better and illustrates exploration process.
namespace example_2 {
using example_state_t = signed char;
using example_node_t = a_star_search::Node<example_state_t>::node_ptr_type;
void example_solve ( example_state_t const& start, example_state_t const& goal ) {
auto example_get_neighbors =
[]( example_state_t const& s ) -> std::vector<example_state_t> {return {s-1, s+1};};
std::vector<example_state_t> result_path, explored_nodes;
auto is_solved = a_star_search::dfs_search<example_state_t, decltype(example_get_neighbors)>
(start, goal, std::move(example_get_neighbors), std::back_inserter(result_path), std::back_inserter(explored_nodes) );
std::cout << std::boolalpha << "Task is solved: " << is_solved << "(" << result_path.size() << ")" << std::endl;
for (const auto& p : result_path )
std::cout << p << " ";
std::cout << std::endl << "Nodes visited " << explored_nodes.size() << std::endl;
}
} //namespace example_2
And program finishes with result
Task is solved: true(251)
-5 -6 -7 -8 -9 -10 -11 -12 -13
...
7 6 5 4 3 2 1
Nodes visited 251
Here we have halting problem and as far as there is no way to define autonomously when to stop function we will ask our user to define it for us (See here). First define concept:
template <typename F>
concept TimeSantinel = requires(F&& f) {
{ std::invoke(std::forward<F>(f)) } -> std::same_as<bool>;
};
And add it to a_star function
template <typename TNodeVisitor,
TimeSantinel Timer,
std::output_iterator<typename TNodeVisitor::TNode::value_type> O>
bool a_star ( typename TNodeVisitor::TNode::value_type const& start,
typename TNodeVisitor::TNode::value_type const& goal,
TNodeVisitor&& node_visitor,
Timer&& timer,
O result_path_it, O explored_node_it) {
...
while ( !node_visitor.empty() && timer()) {
node_it = node_visitor.pop();
*explored_node_it++ = node_it->state_;
if (node_it->state_ == goal) {
solution_found = true;
break;
}
node_visitor.visit_neighbors( node_it );
}
...
return solution_found;
}
And now algorithm finishes in given time
namespace example_1 {
using example_state_t = int;
using example_node_t = a_star_search::Node<example_state_t>::node_ptr_type;
struct MyTimer {
std::chrono::milliseconds duration_;
std::chrono::time_point<std::chrono::steady_clock> start_{std::chrono::steady_clock::now()};
bool operator()() const {
auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(
std::chrono::steady_clock::now() - start_);
return elapsed < duration_;
}
};
void example_solve ( example_state_t const& start, example_state_t const& goal ) {
auto example_get_neighbors =
[]( example_state_t const& s ) -> std::vector<example_state_t> {return {s-1, s+1};};
std::vector<example_state_t> result_path, explored_nodes;
auto is_solved = a_star_search::dfs_search<example_state_t, decltype(example_get_neighbors)>
(start, goal, std::move(example_get_neighbors), MyTimer{std::chrono::milliseconds(30)}, std::back_inserter(result_path), std::back_inserter(explored_nodes) );
std::cout << std::boolalpha << "Task is solved: " << is_solved << "(" << result_path.size() << ")" << std::endl;
for (const auto& p : result_path )
std::cout << p << " ";
std::cout << std::endl << "Nodes visited " << explored_nodes.size() << std::endl;
}
} //namespace example_1
...
Search path from 1 to -5 with DFS algorithm and 30ms timeout
Task is solved: false(0)
Nodes visited 13058
User can set not only time limit, but also amount of steps
namespace example_2 {
using example_state_t = int;
using example_node_t = a_star_search::Node<example_state_t>::node_ptr_type;
struct MyStepper {
int max_steps_;
bool operator()() {
return --max_steps_ >= 0;
}
};
void example_solve ( example_state_t const& start, example_state_t const& goal ) {
auto example_get_neighbors =
[]( example_state_t const& s ) -> std::vector<example_state_t> {return {s-1, s+1};};
std::vector<example_state_t> result_path, explored_nodes;
auto is_solved = a_star_search::dfs_search<example_state_t, decltype(example_get_neighbors)>
(start, goal, std::move(example_get_neighbors), MyStepper{1000}, std::back_inserter(result_path), std::back_inserter(explored_nodes) );
std::cout << std::boolalpha << "Task is solved: " << is_solved << "(" << result_path.size() << ")" << std::endl;
for (const auto& p : result_path )
std::cout << static_cast<int>(p) << " ";
std::cout << std::endl << "Nodes visited " << explored_nodes.size() << std::endl;
}
} //namespace example_2
...
Search path from 1 to -5 with DFS algorithm and 1000 limit to visit nodes
Task is solved: false(0)
Nodes visited 1000