Как эффективно заменить элементы в unordered_set, перебирая его?
Предположим, у вас есть
std::unordered_set<std::shared_ptr<A>> as;
// (there is an std::hash<std::shared_ptr<A>> specialisation)
и вы хотите заменить некоторые из его элементов во время итерации по нему:
for (auto it = as.begin(); it != as.end(); ++it) {
if ((*it)->condition()) {
as.erase(it);
as.insert(std::make_shared<A>(**it));
}
}
Это могло, это может аннулировать итератор в erase а также insert (если происходит перефразировка), то этот цикл будет демонстрировать неопределенное поведение и, скорее всего, будет ужасно падать.
Одно решение, которое я могу придумать, — это использование двух отдельных vectors для буферизации insert а также erase операции, а затем использовать перегрузки, которые принимают пары итераторов для стирания и вставки (это, вероятно, более удобно для перефразирования).
Даже если я использую буферный подход, он все еще выглядит раздутым кодом и может привести к двум перефразам, которые могут быть ненужными.
Так есть ли лучший способ сделать это?
Решение
Я просто подумал о возможном подходе (только после того, как спросил), но, возможно, есть и лучшие.
Копирование всего в вектор, а затем восстановление набора из вектора должно быть быстрее:
std::vector<std::shared_ptr> buffer;
buffer.reserve(as.size());
for (auto it = as.begin(); it != as.end(); ++it) {
if ((*it)->condition()) {
buffer.push_back(std::make_shared<A>(**it));
} else {
buffer.push_back(*it);
}
}
as = std::unordered_set<std::shared_ptr<A>>(buffer.begin(),buffer.end());
Другие решения
Когда вы звоните as.erase(it) итератор it стать недействительным. Вставка в неупорядоченные ассоциативные контейнеры делает недействительными все итераторы. Таким образом, вставка должна быть отделена от итератора. Избегать вставок также необходимо, чтобы избежать обработки вновь вставленных объектов:
std::vector<std::shared_ptr<A>> replaced;
for (auto it = as.begin(); it != as.end(); ) {
if ((*it)->condition()) {
replaced.push_back(std::make_shared<A>(**it));
as.erase(it++);
}
else {
++it;
}
}
std::copy(replaced.begin(), replaced.end(), std::inserter(as, as.begin());
Я бы добавил это как комментарий к ответу @ bitmask. Почему бы просто не использовать вектор для замененных элементов?
std::vector<decltype(as)::value_type> buffer;
buffer.reserve(as.size());
for (auto it = as.begin(); it != as.end(); )
{
if ((*it)->condition())
{
buffer.push_back(*it);
it = as.erase(it);
}
else
{
++it;
}
}
as.insert(buffer.begin(),buffer.end());
И если *it уже shared_ptr<A>Я не вижу причин для make_shared() снова. Просто присвойте и позвольте операторам конструктора / присваивания скопировать свое волшебство.
В вашем случае вы можете просто поменять местами на мой взгляд:
for(auto iter = as.begin(); iter != as.end(); ++iter)
{
if(/*Check deletion condition here*/)
{
auto newItem = std::make_shared<A>(/*...*/);
swap(*iter, newItem);
}
}