如何有效地访问C++中的列表信息？

我原来是用Python做这个游戏的，然后在一个学校项目中将它转换为C++。如何有效地访问C++中的列表信息？

的问题是，C++的std::list不允许我访问像Python的list项目做（list[1]），更是这样，访问是一个列表（list[2][5]）内列出的项目。我一直无法找到一种有效的方法来做到这一点，或者找到一个可行的列表的替代方案。

来源

2016-01-20 Shadow

列表无法通过索引访问。如果你想随机访问，使用矢量。 –

将C++与Python进行比较时，不要混淆术语* list *。一个'std :: list'是C++中的一个双向链表。这意味着不能随机访问列表中的元素。 – PaulMcKenzie

添加到@PaulMcKenzie中，与Python list最直接等价的是std :: vector（它们都是作为一个动态调整大小的数组实现的，它执行重定位以在序列末尾插入/删除摊销'O（1）'）。 – ShadowRanger

请勿使用std::list。它实现了一个双向链表，它不提供下标运算符，因为链表的随机访问不能以恒定的复杂度实现。

取而代之的是，使用std::vector实现动态增长的数组，其中下标运算符定义。

由于@ShadowRanger已评论，你也许发现std::deque有用。它支持像std::vector这样的恒定时间随机存取功能，另外还可以在删除元素时自动释放存储空间。（对于std::vector，您必须明确地通过调用shrink_to_fit来做到这一点，并且这可能很容易走错方向）。当您需要在开始和结束时追加元素时，它也会更好。但据我所知，你不想改变容器中元素的数量。

另请注意Python和C++之间的另一个区别。在Python中，如果你写

my_things = [1, 2, 3, 4] 
your_things = [5, 6, 7] 
our_things = [my_things, your_things]

然后your_things和our_things[1]指向同一个列表。这是因为Python中的对象是通过引用来引用的。另一方面，在C++中，容器具有价值语义。也就是说，如果你写

std::vector<int> my_things = {1, 2, 3, 4}; 
std::vector<int> your_things = {5, 6, 7}; 
std::vector<std::vector<int>> our_things = {my_things, your_things};

our_things将包含副本my_things和your_things以及在改变不会影响其他。如果这不是你想要的，你可以改为一次定义嵌套列表。

std::vector<std::vector<int>> our_things = { 
    {1, 2, 3, 4}, // my things 
    {5, 6, 7},  // your things 
};

来源

2016-01-20 18:15:30 5gon12eder

如果您需要（有效）恒定的时间插入/移除元素开始和结束时使用'std :: deque' （相对于开始时矢量的“O（n）”成本，最后将“O（1）”分期偿还，但间歇性的高成本重新分配）。 'deque'仍然提供'O（1）'随机访问，（支付的价格是更高的内存开销和碎片感谢从一堆小固定大小的数组，而不是'vector'的单个动态大小的数组）。 'deque'唯一让你失去的是能够在迭代过程中有效地添加和移除序列中间的元素。 – ShadowRanger

@ShadowRanger在理论上'O'的复杂性很好，如果你已经对你的代码进行了剖析以确定瓶颈，但vector应该是默认的顺序访问容器。由于缓存，预取等因素，Moder CPU喜欢连贯的内存访问。 – Angew

我不会考虑'std :: deque'，除非我有一些特定的需求，比如前面的大量插入。即使插入时间不变，常数也比矢量大。如果我们有这样的动物，那么“O（1）”随机存取更像“O（2）”。 –

您可以使用矢量而不是列表。

来源

2016-01-20 18:14:29

在C++中，标准::列表不经由操作符[]支持随机访问查找。如果你要继续使用列表，你应该看看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 ::向量或std :: deque的，两者通过操作[]提供随机存取查找。

来源

2016-01-20 18:17:56 GutiMac

如果您不需要更改列表的大小，你可以使用普通的数组。

这甚至可能是最快的选择。但是，只要不更改大小，std::vector的性能相似。

来源

2016-01-20 18:23:46 woodtluk

不“相似”：“相同”！ –

如何有效地访问C++中的列表信息？

回答

相关问题