2

I'm studying Floyd's Tortoise and Hare algorithm, and trying to model the problem using an std::forward_list. Specifically, I'd like to intentionally create a cycle using an std::forward_list, and detect it with said algo.

(Per comments below, without hacking the interface; that is, use the std::forward_list interface to create the cycle.)

The "problem" is that this doesn't seem to be possible. I've looked at the constructors and mutator methods. As far as I can tell, the interface to std::forward_list prevents such cycles from occurring. This is typically be a good thing, unless you're prepping for an interview, and would like to purposely implement a forward_list with a cycle :^)

Is it possible to create a cycle in an std::forward_list?

References:

How to detect a loop in a linked list?
http://en.cppreference.com/w/cpp/container/forward_list
http://codingfreak.blogspot.com/2012/09/detecting-loop-in-singly-linked-list_22.html

Community
  • 1
  • 1
kmiklas
  • 13,085
  • 22
  • 67
  • 103
  • 1
    Since std::forward_list is usually a template, you could create code or a template that directly manipulates the implementation specific internal node pointers, but there's no way to do this using the std::forward_list member functions. Depending on how std::forward_list is implemented, you might have to make a copy of it then edit that copy in order to access the internal node pointers. – rcgldr Jan 26 '17 at 21:59
  • @rcgldr thx. My question is unclear, but I mean create a cycle through the provided interface for std::forward_list. – kmiklas Jan 26 '17 at 22:58
  • 1
    Since you don't have an access to the underlying node type and the iterator is just a ForwardIterator (of some kind) I don't see how this would be possible. – Kevin Jan 26 '17 at 23:07

1 Answers1

4

The interface of forward_list (and list, for that matter) is designed specifically to hide the details of nodes and node pointers from the user. They are free from cycles by design and abstraction.

So no, they do not give you the freedom to create a malformed list. Even using splice doesn't let you do it, as it will remove the items from the old list before putting them in the new one.

If you want to test a cycle detection algorithm, you'll have to write your own linked list type that allows people to make cycles in it.

Nicol Bolas
  • 449,505
  • 63
  • 781
  • 982