Different name for same function makes it harder to write templating code.

[Paul]

When implementing Depth First Search and Breadth First Search,
it's extremely common to make the code for these algorithms the
same, but to use a stack for DFS and a queue for BFS.
Because the code is the same with only the data structures different,
a templating approach seems natural.
Doesn't the fact that queues have a front() but stacks have a top() make
this templating unnecessarily difficult? And what is the standard workaround?

I suppose a Top() function and template specializations where stack objects
return top() and queue objects return front().

I don't know why these have different names but I'm sure there's a good reason
for it.

Paul

[Jorgen Grahn]

On Sun, 2018-10-14, Paul wrote:
> When implementing Depth First Search and Breadth First Search,
> it's extremely common to make the code for these algorithms the
> same, but to use a stack for DFS and a queue for BFS.
> Because the code is the same with only the data structures different,
> a templating approach seems natural.
> Doesn't the fact that queues have a front() but stacks have a top() make
> this templating unnecessarily difficult? And what is the standard workaround?

I think the basic idea is, if two containers have different names for
similar functions, it's because they are different enough to be
non-interchangeable. You can, I believe, see the same thing in
e.g. Python.

> I suppose a Top() function and template specializations where stack objects
> return top() and queue objects return front().
>
> I don't know why these have different names but I'm sure there's a good reason
> for it.

I think it's simply because a queue isn't a stack.

/Jorgen

--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .

[Öö Tiib]

On Sunday, 14 October 2018 12:11:23 UTC+3, Paul wrote:
> When implementing Depth First Search and Breadth First Search,
> it's extremely common to make the code for these algorithms the
> same, but to use a stack for DFS and a queue for BFS.

Generic implementations of those algorithms are only part of true
monsters like Boost.Graph. AFAIK non-recursive DFS of it uses vector,
and BFS uses coloring with specially made visitor). Usually the
algorithms are hand-tailored exactly for specific problem.

Direct usage of std::vector, std::array, std::deque or
boost::circular_buffer is frequent for actual implementations of
those algorithms. Several of DFS that I've seen used
std::priority_queue too.

The reason is likely that interface of std::stack and std::queue
makes it tricky to apply problem-specific heuristics, constraints
and/or optimizations to these (usually performance critical)
algorithms. The handiness for naive implementation matters less.

> Because the code is the same with only the data structures different,
> a templating approach seems natural.
> Doesn't the fact that queues have a front() but stacks have a top() make
> this templating unnecessarily difficult?

No. The stack has only one end "top", queue has two ends: "back" and
"front".

> And what is the standard workaround?

It is not so standard problem at all like you claim and the whole idea is
generally not good. Not Good(TM). Trying to conflate two very different
in actual implementations algorithms because rather naive implementations
of those happen to be similar is actually rather confusing.

> I suppose a Top() function and template specializations where stack objects
> return top() and queue objects return front().

Ugh. Function templates can't be partially specialized, only fully.
It is because functions have to overload. Class templates can be
partially specialized. Otherwise such overloads are rather simple
to write:

template<class T, class C>
std::queue<T, C>::reference pop_element(std::queue<T, C>&& queue)
{
return queue.front();
}

template<class T, class C>
std::queue<T, C>::const_reference pop_element(std::queue<T, C> const& queue)
{
return queue.front();
}

template<class T, class C>
std::stack<T, C>::reference pop_element(std::stack<T, C>&& stack)
{
return stack.top();
}

template<class T, class C>
std::stack<T, C>::const_reference pop_element(std::stack<T, C> const& stack)
{
return stack.top();
}

Disclaimer: Did not bother to test so there can be typos.

> I don't know why these have different names but I'm sure there's a good reason
> for it.

It is because programmers imagine queues as horizontal but stacks as vertical
things. Therefore naming anything in queue as "top" or in stack as "front"
would not make any sense and would just confuse people.

It is also may be worth to note that all standard library std::stack
implementations that I've seen use "back" of underlying container
as "top" of stack.

[Ben Bacarisse]

I think it's just history and convention.

In practical terms, you could use a deque in both cases and parameterise
the search function with the member function to use to queue items. You
can do this either as an actual function parameter or using a template.

--
Ben.