Итак, у меня есть эта структура, которая называется store:
struct Store
{
int position = -1; //graph position of that store node. Since all stores that are given as input have required fish_types
//it would be useless to try to reduce the number using some id field.
int destination; //where the cat shopper is headed from the current position -> used to calculate relative and
//absolute distances.
//this field will be utilized by stores_to_closest_neighboring_stores
set<int> required_fish_types; //fish types that are contained at the store
vector<int> path; //The path to all nodes from the current position represented by the previous array that was derived
//from Dijkstra's algorithm
vector<int> relative_distances; //best distances between all nodes (derived through dijkstra's algorithm)
vector<int> absolute_distances; //the distance between a node (at index i) and the end node + the distances of the
//current node --> an attempt to evaluate the true cost of advancing to a node since all shoppers must end on the
//end node. Ideally, each time a shopper advances to another node they should be getting closer to the end node and
//not further away (if possible). This solution addresses traveling along branches and backtracking with the same
//approach --> if these actions would bring you further from the end node, first check if it possible for little cat
//to advance to that node with a cheaper cost, and then only if it is found that big cat is still in the best position]
//to advance to that node, it should advance to it.
vector<set<Store, Store_Compare>> fish_types_to_stores_with_type_stocked;
//sorted on absolute distances
//to make comparisons between shoppers easier, we include a mapping
//of fish_type to absolute distances so we can determine if little cat is in a better position to advance to a node
//over big cat. We look through the fish types of big cats closest and determine if little cat has a better distance
//to a node with that fish_type or (also a case to consider) to a node with the same distance but with more fish_types.
Store() {}
Store(int position, int fish_type_amount)
{
this->position = position;
fish_types_to_stores_with_type_stocked.resize(fish_type_amount);
}
Store(set<int>& required_fish_types) { this->required_fish_types = required_fish_types; }
bool operator==(const Store& store) const { return this->position == store.position &&
this->destination == store.destination; }
};
Хранилище структур содержит вектор наборов, которые содержат объекты того же типа структуры, в которой был определен член данных (т.е. Store):
vector<set<Store, Store_Compare>> fish_types_to_stores_with_type_stocked;
Проблема возникает, когда программа заполняет этот вектор, который соответствует определенному хранилищу, которое находится в другом векторе хранилищ, который определен в функции: «synchronous_shop ()». Программа компилируется, и не возникает какой-либо конкретной ошибки времени выполнения, однако программа, похоже, не останавливается или, скорее, занимает очень много времени для завершения, и это по какой-то причине только с указанным c вводом; при некотором вводе (даже при вводе того же размера) программа завершает работу и делает это довольно быстро, и я не знаю причину этого. Но я сузил проблему до одной строки кода, которая является вероятным виновником:
stocked_stores[i].fish_types_to_stores_with_type_stocked[fish].insert(inserted);
Она содержится в следующем блоке l oop, который при попытке отладки кода обнаружил, что программа не может пройти дальше:
for (int i = 0; i < stocked_stores.size(); i++)
{
current_store_to_closest_neighboring_stores.insert(pair<int, set<Store, Store_Compare>>
(i, set<Store, Store_Compare>()));
for (int j = 0; j < graph.size(); j++) //populating the fish_types_to_store_with_typed_stocked map, the
//required_fish_types_to_stocked_stores map, and the current_store_to_closest_neighboring_stores map
//i is the destination of a stocked store
if (j != 0 && j != i && j != graph.size() - 1)
for (int fish : stocked_stores[j].required_fish_types)
{
Store inserted = stocked_stores[i];
inserted.destination = j;
stocked_stores[i].fish_types_to_stores_with_type_stocked[fish].insert(inserted);
required_fish_types_to_stocked_stores.at(fish).insert(j);
current_store_to_closest_neighboring_stores.at(i).insert(inserted);
}
}
current_store_to_closest_neighboring_stores, stocked_stores, required_fish_types_to_stocked_stores и Store_Compare определены следующим образом:
//When the fish_list is empty, just add in the cost from the current position to the end node for each shopper
//to its minimum_shopping_cost
vector<bool> stores_out_of_stock(graph.size());
//in addition to a shopping list of which BC and LC reference for determining required fish types the game
//should also retain a list of shopping centers that are no longer in stock of required fish types. When a
//shopper visits a store it will clear the closest stores set of the out of stock stores that are in that list.
//Then it will advance to the nearest store from there. This is more efficient than simply iterating through all of
//the in-stock stores within the closest stores map because of that approach wastes time in updating stores that we may
//never actually visit.
//for assistance in iterating over fish_types_to_absolute_distances, if a store is
//out of stock skip over it (might need to be passed in because it is the same from store to store)-> this can be
//used actually in lieu of the other store out of stock vector<int> -> to save even more time deleting out of stock
//stores in the set -> we only need to delete up to the first node/store in the set that is not out of stock.
//An improvement for efficiency. Instead of deleting all the stores that have been cleared out from the
//game from the sets of every single store within the map, we are only deleting the topmost element of the
//store we are actually advancing to until we reach a store that is in stock -- don't have to clear every
//single invalidated store in the set and don't have to update the set of every single store because
//we may not end up advancing to those stores as the game progresses.
unordered_map<int, set<Store, Store_Compare>> current_store_to_closest_neighboring_stores;
//maps store position to a set of stocked stores
unordered_map<int, set<int>> required_fish_types_to_stocked_stores;
//this probably should be passed into synchronous_shop from init
//only for deleting enties out of current_store_to_closest_neighboring_stores
//contains the only set in the program where the order of its entries doesn't matter--could have just as easily been
//a vector, and since we only iterate through this set and never reference a specific element, a hashing scheme
//would not improve its performance
struct Store_Compare
{
bool operator() (const Store& s1, const Store& s2) const //should s1 and s2 be ids graph positions?
{
return s1.absolute_distances[s1.destination] == s2.absolute_distances[s2.destination] ?
s1.relative_distances[s1.destination] == s2.relative_distances[s2.destination] ?
s1.required_fish_types.size() == s2.required_fish_types.size() ? s1.destination < s2.destination :
s1.required_fish_types.size() > s2.required_fish_types.size()
: s1.relative_distances[s1.destination] < s1.relative_distances[s2.destination] :
s1.absolute_distances[s1.destination] < s2.absolute_distances[s2.destination];
//since the number of fish types at each store is constantly changing, we can't rely on the initially sorting
//that of store compare for the data structures that use it
//The purpose of the algorithm is to progress closer to the end node with every move. You don't want to make a
//move that is going to take you farther than you were from the start node if you can advance to a store that
//is closer. You have two shoppers available to minimize the distance between you, the store, and the end node.
}
};
Я читал из этого поста Определения классов и собственные типы , что можно объявить контейнер собственного типа, но я также прочитал в том же посте, что объект, который содержит член собственного типа в своем определении, недопустим, потому что класс имеет " неполный тип. " Создание члена таким способом приведет к «созданию бесконечной цепочки объектов, которая потребует бесконечной памяти».
Я не уверен, что это именно то, что происходит в моем случае, но я думаю, что это может быть. Как мне go решить эту проблему? Исходя из границ проблемы, взятой из упражнения Hackerrank под названием « Synchronous Shopping », объекты хранилища, которые существуют в структуре данных vector>, должны быть сопоставимы с объектами хранилища, которые существуют вне Хранить структуру. Вот почему член данных содержит объекты собственного типа, поскольку он должен хранить объекты, созданные вне класса, в своем собственном экземпляре класса, и эти хранилища должны сравниваться с другими экземплярами класса, которые содержат разные наборы хранилищ. Я подумал о создании отдельного или дочернего класса для определения магазинов в элементе данных fish_types_to_stores_with_type_stocked в качестве возможного обходного пути. Но я мог бы попытаться изменить дизайн элемента данных в целом. В то время это казалось интуитивным решением.
Если что-то требует дальнейших объяснений, дайте мне знать. Я заранее прошу прощения за то, что не использовал typedefs для более кратких схем именования. Я надеюсь, что все не слишком запутанно. Я также могу включить полную программу, если кто-то считает, что это будет полезно. Я просто подумал, что это не нужно для решения этой проблемы. Я также прошу прощения, если что-то кажется в значительной степени неэффективным. Я все еще начинающий программист, но пытаюсь учиться. Предложения приветствуются. Спасибо.