CODEWITHSUNDEEP
c++liststl
Kevin Hu
Kevin Hu

Reputation: 67

How to create a loop using STL list in C++

This is an interview question: How to create a loop using the STL list container?

I am a newbie. I searched this question and did not find any. If this is an old question please give me the link and delete this post.

Thank you all!

Upvotes: 0

Views: 428

Answers (2)

jxh
jxh

Reputation: 70402

One possible answer is: It can happen when more than one thread is manipulating the list structure at the same time. Suppose two threads want to push_back into an already formed list. If the list already has b and a, the circular list could look like:

  .--------------------------.
 (                            )
  `-> a <-> SENTINEL <-> b <-'

And one thread inserts c at the same time another inserts d. They each want to attach to the back of the SENTINEL like this:

a <-> c <-> SENTINEL
a <-> d <-> SENTINEL

However, the could end up making a loop:

   .------------.
a. `-.           )
  `-> c <-> d <-'
             <--> SENTINEL <-> b (<-> a)

The forward links are fine: b -> a -> c -> d
But the reverse links will loop: d -> c -> d ...

This can happen because the pointers of the SENTINEL is being read, dereferenced, and modified without mutual exclusion.

Upvotes: 1

Robᵩ
Robᵩ

Reputation: 168626

How to create a loop using the STL list container?

You can't.

std::list has a beginning and an end. All access to the data structure is carefully controlled so that a standard-compliant program simply cannot produce a non-terminating list.

P.s. I'm assuming that the interviewer actually meant to say "std::list" instead of "STL list."

Upvotes: 2

Related Questions