C ++ Маркировка объектов для удаления в списке STD через nullptrs
Мне было интересно, если это приемлемая практика:
struct Item { };
std::list<std::shared_ptr<Item>> Items;
std::list<std::shared_ptr<Item>> RemovedItems;
void Update()
{
Items.push_back(std::make_shared<Item>()); // sample item
for (auto ItemIterator=Items.begin();ItemIterator!=Items.end();ItemIterator++)
{
if (true) { // a complex condition, (true) is for demo purposes
RemovedItems.push_back(std::move(*ItemIterator)); // move ownership
*ItemIterator=nullptr; // set current item to nullptr
}
// One of the downsides, is that we have to always check if
// the current iterator value is not a nullptr
if (*ItemIterator!=nullptr) {
// A complex loop where Items collection could be modified
}
}
// After the loop is done, we can now safely remove our objects
RemovedItems.clear(); // calls destructors on objects
//finally clear the items that are nullptr
Items.erase( std::remove_if( Items.begin(), Items.end(),
[](const std::shared_ptr<Item>& ItemToCheck){
return ItemToCheck==nullptr;
}), Items.end() );
}
Идея заключается в том, что мы отмечаем, что контейнер Items может быть произведен из внешних источников. Когда элемент удаляется из контейнера, ему просто присваивается значение nullptr, но перед этим он перемещается в RemovedItems.
Что-то вроде событие может повлиять на Items и добавить / удалить элементы, поэтому мне пришлось придумать это решение.
Кажется ли это хорошей идеей?
Решение
Я думаю, что вы слишком усложняете вещи. Если вы находитесь в многопоточной ситуации (вы не упомянули об этом в своем вопросе), вам, безусловно, потребуются некоторые блокировки, защищающие чтения из других потоков, которые получают доступ к вашим измененным спискам. Поскольку в стандартной библиотеке нет параллельных структур данных, вам нужно будет добавить такие вещи самостоятельно.
Для однопоточного кода вы можете просто вызвать std:list член remove_if с вашим предикатом. Нет необходимости устанавливать указатели в null, хранить их и делать несколько проходов над вашими данными.
#include <algorithm>
#include <list>
#include <memory>
#include <iostream>
using Item = int;
int main()
{
auto lst = std::list< std::shared_ptr<Item> >
{
std::make_shared<int>(0),
std::make_shared<int>(1),
std::make_shared<int>(2),
std::make_shared<int>(3),
};
// shared_ptrs to even elements
auto x0 = *std::next(begin(lst), 0);
auto x2 = *std::next(begin(lst), 2);
// erase even numbers
lst.remove_if([](std::shared_ptr<int> p){
return *p % 2 == 0;
});
// even numbers have been erased
for (auto it = begin(lst); it != end(lst); ++it)
std::cout << **it << ",";
std::cout << "\n";
// shared pointers to even members are still valid
std::cout << *x0 << "," << *x2;
}
Обратите внимание, что элементы действительно были удалены из списка, а не просто помещены в конец списка. Последний эффект является то, что стандартный алгоритм std::remove_if будет делать, и после чего вам придется позвонить std::list функция-член erase, Это двухступенчатый стереть-удалить идиома выглядит так
// move even numbers to the end of the list in an unspecified state
auto res = std::remove_if(begin(lst), end(lst), [](std::shared_ptr<int> p){
return *p % 2 == 0;
});
// erase even numbers
lst.erase(res, end(lst));
Однако в обоих случаях Item элементы не были удалены, так как каждый из них все еще имеет общий указатель, связанный с ними. Только если количество рефенсов упадет до нуля, эти прежние элементы списка будут фактически удалены.
Другие решения
Если бы я просматривал этот код, я бы сказал, что он неприемлем.
Какова цель двухэтапного удаления? Такое необычное решение требует комментариев, объясняющих его цель. Несмотря на неоднократные запросы, вы не смогли объяснить суть.
Идея в том, что мы размечаем
ItemsКонтейнер может быть произведен из внешних источников.
Вы имеете в виду «Идея в том, что в то время как мы отмечаем, что контейнер Items может быть произведен из внешних источников. «? В противном случае это предложение не имеет смысла.
Как это может повлиять? Ваше объяснение не ясно:
Думать о
Root -> Parent -> Childотношения. Событие может сработать вChildчто может удалитьParentотRoot, Таким образом, цикл может оборваться посередине и итератор будет недействительным.
Это ничего не объясняет, это слишком расплывчато, используя очень широкие термины. Объясните, что вы имеете в виду.
«Отношения родитель-ребенок» могут означать много разных вещей. Вы имеете в виду, что типы связаны наследованием? Объекты связаны, по собственности? Какие?
Что за «событие»? Событие может означать много вещей, я хотел бы, чтобы люди в StackOverflow перестали использовать слово «событие» для обозначения конкретных вещей, и предполагая, что все остальные знают, какое значение они намерены. Вы имеете в виду асинхронное событие, например в другой теме? Или вы имеете в виду уничтожение Item может привести к удалению других элементов из Items список?
Если вы имеете в виду асинхронное событие, ваше решение полностью не решит проблему. Вы не можете безопасно перебирать любой стандартный контейнер, если этот контейнер можно модифицировать одновременно. Чтобы сделать это безопасным, вы должны что-то сделать (например, заблокировать мьютекс), чтобы обеспечить монопольный доступ к контейнеру при его изменении.
На основании этого комментария:
// A complex loop where Items collection could be modified
Я предполагаю, что вы не имеете в виду асинхронное событие (но почему вы говорите, что «внешние источники» могут изменить контейнер), и в этом случае ваше решение гарантирует, что итераторы остаются действительными, пока «сложный цикл» выполняет итерации по списку, но почему нужен фактический Item объекты остаются действительными, а не просто сохраняют действительность итераторов? Не могли бы вы просто установить элемент nullptr не помещая это в RemovedItemsтогда делай Items.remove_if([](shared_ptr<Item> const& p) { return !p; } в конце? Вы должны объяснить немного больше о том, что ваш «сложный цикл» может сделать с контейнером или с элементами.
Почему RemovedItems не локальная переменная в Update() функционировать? Кажется, это не нужно вне этой функции. Почему бы не использовать новый C ++ 11 на основе диапазона for цикл для перебора списка?
Наконец, почему все назван с большой буквы ?! Назвать локальные переменные и функции с заглавной буквы просто странно, и если все именуется таким образом, тогда это бессмысленно, потому что использование заглавных букв не помогает различать разные типы имен (например, использование заглавной буквы только для типов дает понять, какие имена являются типами, а какие нет … использование их для всего бесполезно).
Я чувствую, что это только усложняет ситуацию, поскольку везде нужно проверять nullptr. Кроме того, перемещение shared_ptr немного глупо.
редактировать:
Я думаю, что я понимаю проблему сейчас, и вот как бы я решил ее:
struct Item {
std::list<std::shared_ptr<Item>> Children;
std::set < std::shared_ptr<Item>, std::owner_less < std::shared_ptr<Item >> > RemovedItems;
void Update();
void Remove(std::shared_ptr<Item>);
};
void Item::Update()
{
for (auto child : Children){
if (true) { // a complex condition, (true) is for demo purposes
RemovedItems.insert(child);
}
// A complex loop where children collection could be modified but
// only by calling Item::remove, Item::add or similar
}
auto oless = std::owner_less < std::shared_ptr < Item >>();
std::sort(Children.begin(), Children.end(), oless ); //to avoid use a set
auto newEnd = std::set_difference(Children.begin(),
Children.end(),
RemovedItems.begin(),
RemovedItems.end(),
Children.begin(),
oless);
Children.erase(newEnd, Children.end());
RemovedItems.clear(); // may call destructors on objects
}
void Item::Remove(std::shared_ptr<Item> element){
RemovedItems.insert(element);
}