Является ли std :: list лучше, чем std :: vector, если хранить указатели?

Question

Я обычно избегаю std :: list, но в случае, когда я храню указатели, было бы более выгодно использовать std :: list, поскольку тогда я мог бы произвольно вставлять указатели, не перемещая все остальные мои указатели?Какие преимущества и недостатки это может представлять по std::vector<Some*>

Спасибо

Answer 1

Поскольку создание указателя при копировании тривиально, здесь принимается решение не о том, лучше или нет лучше хранить указатели, а о том, что лучше для ваших нужд.

Если вам действительно нужно сделать много случайных вставок (и удалить?), Тогда list может работать лучше, хотя это не простое решение - возможно, даже vector с зарезервированным пространством будет предпочтительнее, даже тогда. Вы хотите, чтобы издержки на узел list просто сохраняли указатель? В 32-битной Windows это 12 байт на запись в list, плюс накладные расходы на управление кучей, в общей сложности 20+ байт на запись. Это также не помогает локализации данных с течением времени. Между тем, vector использует четыре байта на запись (опять же на 32-битной) и гарантированно хранит свои элементы в непрерывном блоке.

Вам придется иметь дело с очисткой памяти при erase / clear / уничтожении контейнера в любом случае, если только вы не заключите элемент указателя в какой-то умный указатель. Альтернативой для упрощения управления памятью ваших Some* является один из контейнеров Boost pointer .

См. Также здесь для некоторого анализа list, vector и deque. Лично я все чаще придерживаюсь мнения, что list не очень полезен в мейнстриме.

Answer 2

Я думаю, что это , особенно указатели , где использование std::vector вместо std::list должно рассматриваться даже при большом количестве вставок / удалений в случайных позициях. Указатели очень дешевы для копирования (на самом деле, я ожидаю, что моя стандартная реализация библиотеки использует для этого встроенные функции процессора ), так что более высокая локальность std::vector данные могут значительно перевесить теоретически лучшую пригодность std::list для случайных вставок / удалений.

В любом случае, вам придется измерить вашу заявку (и , а не искусственный тестовый случай), чтобы точно знать.

Answer 3

В общем, ваш первый выбор должен быть vector - также, когда вы храните указатели.

Сравните решение с этим вопросом на C (-ish): Когда я выберу

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

над

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

Есть случаи, но сначала проверьте, можете ли вы применить «более простую» структуру данных, то есть vector.

Answer 4

Я полагаю, что вы спросите о [std::list<Foo*> будет очень медленно из-за множества косвенных указаний]

std::vector<Foo*> objects

Vs

std::list<Foo> objects

std::vector:

• Быстрый переход
• Случайный доступ к различным Foo объектам
• Foo может быть абстрактным
• Вам необходимо delete ваших объектов вручную
• Медленная вставка, если не в конце

std::list:

• Нет необходимости вручную delete объекты
• Быстрая вставка
• Медленный обход
• Нет произвольного доступа к различным Foo объектам
• Foo не может быть абстрактным

РЕДАКТИРОВАТЬ:

Iпонял, что есть одна ситуация, когда 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;
    };

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

Обычно, когда вам нужен контейнер, который хранит что-то, а затем случайным образом удаляет его, тогда лучшим будет set. Чтобы удалить что-то, вам нужно сначала найти это, то есть O(n) для вектора и списка и O(log(n)) для набора. Если найдено, то удаление происходит мгновенно для списка, но O(n) для вектора и снова O (log (n)) для набора.

Итак:

• рассмотрите vector, если вы очень редко искать или удалять из этого контейнер;
• рассмотрите list, если вы очень редко выполняете поиск в контейнере;
• рассмотрите set иначе.

A vector наиболее эффективно использует память и кэш. Если вы знаете количество элементов, то, используя reserve(), вы можете сделать его эффективным на 100%.