如何访问 std::list<string> 中的特定元素？

Question

   list<string>&  whichList = theLists[ myhash( x, theLists.size( ) ) ];

我在想如何访问某个位置（比如“i”），并查看该位置是否为空。

我是这样做的：

if(whichList[i] == 0)

但它似乎没有起作用。

我意识到这是错误的。有什么建议吗？

- user1074798

---

你不能将一个 string 与 0 进行比较。你想要达到什么目的？ - Kerrek SB

你不能对 std::list 进行索引，你需要使用迭代器。 - wkl

Answer 1

您可以尝试类似以下的代码：

list<string> iterator it = whichList.begin();
std::advance(it, i);
if(*it == "") { /* ... */ }

但我认为你需要清楚地定义在这里所谓的“空”-你不能将字符串与0进行比较。

关键点是，由于其实现方式（双向链表），list不支持随机访问，支持随机访问会是一种O(n)操作，即在最坏情况下与列表长度成线性关系。这是低效的，因此接口中故意不支持它。

正如其他人指出的，如果您想要随机访问，那么最好使用像vector或deque这样的东西。一般而言，如果您只需要在容器末尾快速插入/删除，请使用vector；如果您还需要在容器前面快速插入/删除，请使用deque；如果您只需要在容器中间快速插入/删除，请使用list。为了支持后一种类型的操作，list最终牺牲了对元素的随机访问。

顺便说一下，这里是advance的定义：

http://www.sgi.com/tech/stl/advance.html

编辑：正如Alf所指出的，您可以使用间隙缓冲区技术（请参见http://en.wikipedia.org/wiki/Gap_buffer）在向量中部分地进行快速插入/删除，尽管如果您填充间隙，则单个操作可能会很昂贵（思路是将成本摊销到大量操作上，使操作序列相对便宜）。

- Stuart Golodetz

---

嗯，不完全正确。list 支持（或曾经支持）高效切割。你可以通过比移动元素更智能的方式，也就是游标间隙技术，在连续数组中进行 O(1) 时间插入和删除，但你无法在 O(1) 时间内拼接数组。可惜，据我回忆，C++03 标准让每个编译器决定 list 的拼接复杂度，然后，如果我没记错的话，在 C++11 中被限制为线性时间。这就消除了唯一的原则上的效率优势。糟糕。剩下的优点是 list 不会使很多东西过期。 - Cheers and hth. - Alf

@Alf：谢谢，说实话我还没有接触过光标间隙技术，我会去查一下的！不过我以前用过列表进行拼接，因为它可以是常数时间，并且保证不会比线性时间更差。遗憾的是，在C++11中它现在是线性时间。 - Stuart Golodetz

他们同时到达了。谢谢，不过很有趣。 - Stuart Golodetz

如果您成功填充了空隙，那么缓冲区就已经满了，需要一个更大的新缓冲区。类似于vector的间隙缓冲区可以像vector一样通过某个因子增加缓冲区大小并将其移动或复制到新缓冲区中来实现。这不是间隙缓冲区的额外成本，而是当缓冲区完全填满时通常发生的事情（或者人们希望发生的事情）。干杯！ - Cheers and hth. - Alf

Answer 2

在C++中，std::list不支持通过operator []进行随机访问查找。如果您仍然要使用列表，应该查看std::advance函数。

list<string>::iterator itr = whichList.begin();
std::advance(itr, i);
if (itr->empty())
{
 /* ... assuming that you're testing for an empty string */
}

如果可能的话，您可以考虑其他标准容器，比如std::vector或std::deque，它们都通过operator []提供随机访问查找。

- Dave S

Answer 3

查找第一个值为空字符串的列表元素的标准方法是使用std::find：

std::list<std::string>::iterator it = std::find(whichList.begin(), whichlist.end(), "");

它的位置可以计算出来（代价高昂）std::distance(whichList.begin(), it)，但是假设您已经有意识地决定使用std::list作为应用程序的正确容器类型，那么您不太可能需要实际的数字索引。

- Kerrek SB

Answer 4

我认为你应该使用向量来解决这个问题。

- user977154

---

我认为你应该提出一个理由。 - James Clark

因为他正在读取一个字符串文本文件。为什么你要使用列表，James？？？ - user977154

使用向量会更容易吗？ - user1074798