Как цепочки удалять пары из вектора в C ++?

У меня есть этот текстовый файл, где я читаю каждую строку в std::vector<std::pair>,

handgun bullets
bullets ore
bombs ore
turret bullets

Первый элемент зависит от второго элемента. И я пишу функцию удаления, где, когда пользователь вводит имя элемента, он удаляет пару, содержащую элемент, как второй элемент. Поскольку существует отношение зависимости, элемент, зависящий от удаленного элемента, также должен быть удален, поскольку он больше не может использоваться. Например, если я удалю ore, bullets а также bombs больше не может быть использован, потому что ore недоступен. Как следствие, handgun а также turret также должны быть удалены, так как эти пары зависят от bullets который зависит от ore то есть косвенная зависимость от ore, Эта цепочка должна продолжаться, пока все зависимые пары не будут удалены.

Я попытался сделать это для текущего примера и пришел со следующим псевдокодом,

for vector_iterator_1 = vector.begin to vector.end
{
if user_input == vector_iterator_1->second
{
for vector_iterator_2 = vector.begin to vector.end
{
if vector_iterator_1->first == vector_iterator_2->second
{
delete pair_of_vector_iterator_2
}
}

delete pair_of_vector_iterator_1
}
}

Не очень хороший алгоритм, но он объясняет, что я собираюсь сделать. В примере, если я удаляю ore, затем bullets а также bombs удаляется тоже. Впоследствии пары в зависимости от ore а также bullets также будут удалены (bombs не имеют никакой зависимости). Поскольку существует только одна цепочка одной длины (ore-->bullets), есть только одно вложенное for цикл, чтобы проверить это. Однако в одной цепочке может быть ноль или большое количество зависимостей, что приводит к множеству или отсутствию вложенности. for петли. Так что это не очень практичное решение. Как бы я сделал это с цепочкой зависимостей переменной длины? Пожалуйста, скажите мне. Спасибо за терпеливость.

П. С.: Если вы не поняли мой вопрос, пожалуйста, дайте мне знать.

2

Решение

Одно (наивное) решение:

  • Создать очередь элементов для удаления
  • Добавьте в свой первый элемент (введенный пользователем)
  • Пока (! Empty (items-to-delete)) перебирает ваш вектор
  • Каждый раз, когда вы найдете свой текущий элемент в качестве второго элемента в своем списке, добавьте первый элемент в свою очередь, а затем удалите эту пару

Простые оптимизации:

  • Убедитесь, что вы никогда не добавляете элемент в очередь дважды (хеш-таблица и т. Д.)
3

Другие решения

лично я бы просто использовал стандартную библиотеку для удаления:

vector.erase(remove_if(vector.begin(), vector.end(), [](pair<string,string> pair){ return pair.second == "ore"; }));

remove_if () даст вам итератор для элементов, соответствующих критериям, чтобы вы могли иметь функцию, которая принимает .second значение для удаления, и стирает совпадающие пары при сохранении .first ценности в тех, которые стираются. Оттуда вы можете зацикливаться, пока ничего не будет удалено.

Для вашего решения может быть проще использовать find_if внутри цикла, но в любом случае в стандартной библиотеке есть несколько полезных вещей, которые вы можете использовать здесь.

1

Я не мог не написать решение, используя стандартные алгоритмы и структуры данных из стандартной библиотеки C ++. Я использую std::set помнить, какие объекты мы удаляем (я предпочитаю, так как он имеет доступ к журналу и не содержит дубликатов). Алгоритм в основном такой же, как предложенный @Beth Crane.

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <string>
#include <set>

int main()
{
std::vector<std::pair<std::string, std::string>> v
{   {"handgun", "bullets"},
{"bullets", "ore"},
{"bombs", "ore"},
{"turret", "bullets"}};

std::cout << "Initially: " << std::endl << std::endl;
for (auto && elem : v)
std::cout << elem.first << " " << elem.second << std::endl;

// let's remove "ore", this is our "queue"std::set<std::string> to_remove{"bullets"}; // unique elements

while (!to_remove.empty()) // loop as long we still have elements to remove
{
// "pop" an element, then remove it via erase-remove idiom
//  and a bit of lambdas
std::string obj = *to_remove.begin();
v.erase(
std::remove_if(v.begin(), v.end(),
[&to_remove](const std::pair<const std::string,
const std::string>& elem)->bool
{
// is it on the first position?
if (to_remove.find(elem.first) != to_remove.end())
{
return true;
}
// is it in the queue?
if (to_remove.find(elem.second) != to_remove.end())
{
// add the first element in the queue
to_remove.insert(elem.first);
return true;
}
return false;
}
),
v.end()
);
to_remove.erase(obj); // delete it from the queue once we're done with it
}

std::cout << std::endl << "Finally: " << std::endl << std::endl;
for (auto && elem : v)
std::cout << elem.first << " " << elem.second << std::endl;
}
1

@vsoftco Я посмотрел на ответ Бет и пошел искать решение. Я не видел твой код, пока не вернулся. При ближайшем рассмотрении вашего кода я вижу, что мы сделали почти то же самое. Вот что я сделал,

std::string Node;

std::cout << "Enter Node to delete: ";

std::cin >> Node;

std::queue<std::string> Deleted_Nodes;

Deleted_Nodes.push(Node);

while(!Deleted_Nodes.empty())
{
std::vector<std::pair<std::string, std::string>>::iterator Current_Iterator = Pair_Vector.begin(), Temporary_Iterator;

while(Current_Iterator != Pair_Vector.end())
{
Temporary_Iterator = Current_Iterator;

Temporary_Iterator++;

if(Deleted_Nodes.front() == Current_Iterator->second)
{
Deleted_Nodes.push(Current_Iterator->first);

Pair_Vector.erase(Current_Iterator);
}

else if(Deleted_Nodes.front() == Current_Iterator->first)
{
Pair_Vector.erase(Current_Iterator);
}

Current_Iterator = Temporary_Iterator;
}

Deleted_Nodes.pop();
}

Чтобы ответить на ваш вопрос в комментарии к моему вопросу, вот что else if заявление для. Предполагается, что это ориентированный граф, поэтому он удаляет только элементы следующего уровня в цепочке. Элементы более высокого уровня не затрагиваются.

1 --> 2 --> 3 --> 4 --> 5

Удалить 5: 1 --> 2 --> 3 --> 4

Удалить 3: 1 --> 2 4 5

Удалить 1: 2 3 4 5

Хотя мой код похож на ваш, я не эксперт в C ++ (пока). Скажите, если я сделал какие-либо ошибки или что-то упустил. Благодарю. 🙂

0