如果存储指针，std::list 是否比 std::vector 更好？

Question

我通常避免使用 std::list，但在存储指针的情况下，使用 std::list 会更有利吗，因为我可以随机插入指针而不必移动所有其他指针？与 std::vector 相比，这有哪些优点和缺点

谢谢

Answer 1

由于指针的复制构造很简单，因此这里的决定不是关于哪个更适合存储指针，而是哪个更适合您的需求。

如果您确实需要进行大量随机插入（和删除？），那么 list 可以工作得更好，尽管这不是一个简单的决定 - 也许带有保留空间的 vector 会更好，即使如此。您是否希望列表的每个节点开销只是为了存储指针？在 32 位 Windows 上，列表中的每个条目 12 个字节，加上堆管理开销，每个条目总共 20 多个字节。随着时间的推移，这也无助于数据局部性。同时，vector 每个条目使用四个字节（同样是 32 位），并保证将其元素存储在连续的块中。

无论哪种方式，您都必须在erase/clear/销毁容器时处理内存清理，除非您将指针元素包装为某种智能指针。简化 Some* 内存管理的另一种方法是 增强指针容器。

另请参阅此处对 list、的一些分析矢量和双端队列。就我个人而言，我越来越认为 list 在主流中没有那么有用。

Answer 2

我认为尤其是指针应该考虑使用std::vector而不是std::list在随机位置进行多次插入/删除。复制指针的成本非常低（事实上，我希望我的标准库实现使用 CPU 内部函数来完成此操作），因此 的局部性更高std::vector 的数据可能远远超过理论上更好的随机插入/删除的 std::list 适应性。

无论如何，您必须测量您的应用程序（而不是人工测试用例）才能确定。

Answer 3

一般来说，您的第一选择应该是vector——同样，当您存储指针时。

将这个决定与 C 中的这个问题（-ish）进行比较：When do I choice

struct linked_items {
  element      *item;
  linked_items *next;
};

over

   element* items[];  /* array of pointers to items */

？

有一些情况，但首先检查是否可以应用“更简单”的数据结构，即向量。

Answer 4

一般来说，当您需要一个存储某些内容然后随机删除它的容器时，最好的选择是set。要删除某些内容，您需要先找到它，向量和列表的复杂度为 O(n)，集合的复杂度为 O(log(n))。如果找到，则删除它对于列表来说是即时的，但对于向量来说是O(n)，对于集合来说又是O(log(n))。

所以：

• 如果你很少使用向量，请考虑向量
  从此搜索或删除
  容器;
• 如果您很少在容器中搜索，请考虑 list；
• 否则请考虑设置。

向量 是内存和缓存效率最高的。如果您知道元素的数量，那么使用 reserve() 可以使其内存效率达到 100%。

Answer 5

根据基准测试研究，我更喜欢使用向量，除非有其他强大的用例来支持链表（带有一些开销信息）。但要以更好的方式解决插入和删除效率低下的问题（平均而言）。

我的想法如下：

vector<SomeObject*> vecSomeObjectPointers;
vector<size_t> vecInvalidPointerIndices;// could be zero size, if no objects are removed

创建/添加新的 SomeObject 元素：

void AddNewObject()
{
    SomeObject* ptrSomeObject = new SomeObject;
    ptrSomeObject->PopulateSomeObject(); // add any extra memory if needed by SomeObject members
    ptrSomeObject->DoAnyOtherWorkOnSomeObjectBeforeStoring();

    size_t TotalInValidIndices = vecInvalidPointerIndices.size();
    if(TotalInValidIndices > 0) 
    {
    //re-use the invalid location/index of vector to hold new object
    vecSomeObjectPointers[vecInvalidPointerIndices[TotalInValidIndices-1]] = ptrSomeObject;
    vecInvalidPointerIndices.pop_back();
    }
    else vecSomeObjectPointers.push_back(ptrSomeObject); // new Object pointer at the end
}

删除现有的 SomeObject 元素：

void DeleteAnExistingObject()
{
    //Find the index of the object to be deleted based on certain input criteria. Ex: value stored etc..
    SomeObject* ptrSomeObject;
    for(auto& itr=vecSomeObjectPointers.begin(); itr != vecSomeObjectPointers.end(); ++itr)
    {
        ptrSomeObject = itr;
        if(ptrSomeObject->SomeObjectDeletionCriteriaSatisfied())
        {
            // make sure to delete any extra memory allocated to SomeObject members
            delete ptrSomeObject; // re-claim allocated memory

            // just invalidate the pointer info rather deleting it from vector to save re-shuffling time
            itr = NULL; 

            //Store the corresponding index to be used for holding a new object to be inserted next time
            vecInvalidPointerIndices.push_back(itr - vecSomeObjectPointers.begin());
        }
    }
}

使用线性搜索时间处理向量的现有 SomeObject 元素：

void DoSomeWorkOnAnExistingObject()
{
    SomeObject* ptrSomeObject;
    for(auto& itr=vecSomeObjectPointers.begin(); itr != vecSomeObjectPointers.end(); ++itr)
    {
        if(itr == NULL) continue;
        //Do some work on object data to maintain it
        ptrSomeObject = itr;
    }
}

欢迎任何其他想法...

Answer 6

我假设您询问 [std::list 由于许多间接而会非常慢]

std::vector<Foo*> objects

Vs

std::list<Foo> objects

std::vector：

• 快速遍历
• 随机访问不同的内容Foo 对象
• Foo 可以是抽象的
• 您需要手动删除您的对象
• 如果不在末尾，插入速度会很慢

std::list：

• 不需要手动删除对象
• 快速插入
• 慢速遍历
• 不能随机访问不同的Foo对象
• Foo不能是抽象的

编辑：

我意识到在一种情况下，除非您的对象由其他人拥有，否则 std::vector 不起作用。考虑这个递归的事情

class Foo
    {
    public:
        ~Foo(); /**<Now this must be recursive, otherwise it would need std::stack, which results in potential exception from dtor!*/
    private:
        std::vector<Foo*> m_children;
    };