c++ - 如何在 C++ 中使用 STL 列表创建循环

Question

这是一道面试题：如何使用 STL 列表容器创建循环？

我是新手。我搜索了这个问题并没有找到任何问题。如果这是一个老问题，请给我链接并删除此帖子。

谢谢你们！

score 2 · Accepted Answer

如何使用 STL 列表容器创建循环？

你不能。

std::list有开始也有结束。对数据结构的所有访问都受到严格控制，因此符合标准的程序根本无法生成非终止列表。

Ps 我假设面试官实际上是想说“ std::list”而不是“STL 列表”。

score 1 · Accepted Answer

一个可能的答案是：当多个线程同时操作该list结构时，可能会发生这种情况。假设两个线程想要push_back进入一个已经形成的list. 如果列表已经有band a，则循环列表可能如下所示：

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

一个螺纹c同时插入另一个螺纹d。他们每个人都想像这样附加到后面SENTINEL：

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

但是，最终可能会形成一个循环：

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

前向链接很好：b -> a -> c -> d
但反向链接会循环：d -> c -> d...

发生这种情况是因为 SENTINEL 的指针在没有互斥的情况下被读取、取消引用和修改。

2 回答 2