dcsimg
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 4 of 4

Thread: Why would modifying a vector member of self-type cause this program to run infinitely

  1. #1
    Join Date
    Jun 2018
    Posts
    9

    Why would modifying a vector member of self-type cause this program to run infinitely

    So, I have this struct called store:

    Code:
    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; }
    };
    Struct store contains a vector of sets that contain objects of the same type of the struct the data member was defined in (i.e. Store):

    Code:
    vector<set<Store, Store_Compare>> fish_types_to_stores_with_type_stocked;
    The issue arises when the program is populating this vector which corresponds to a particular store that lies within another vector of stores that is defined within a function: "synchronous_shop()". The program compiles, and there is not a particular runtime error that is triggered, however, the program doesn't seem to halt or rather takes a very long time to terminate and this is only with specific input, for some reason; with some input (even with input of the same size), the program does terminate and does so rather quickly, and I do not know the reason why. But I have narrowed the issue down to one line of code which is the probable culprit:

    Code:
    stocked_stores[i].fish_types_to_stores_with_type_stocked[fish].insert(inserted);
    It is contained within the following loop block, which when I tried to debug the code, found that the program couldn't progress past:

    Code:
    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, and Store_Compare are defined as follows:

    Code:
        //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 entries 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.
        }
    };
    I've read from a post on class definitions and self types that it is valid to declare a container of self type, but I also read within the same post that an object that that contains a member of self type in its definition is invalid because the class is of "incomplete type." Creating a member in this way would result in "creating an endless chain of objects which would require infinite memory."

    I'm not sure if this is exactly what is happening in my case, but I think it may be. How do I go about fixing this issue? Based on the confines of the problem, which is from a Hackerrank exercise titled "Synchronous Shopping", the store objects that exist within the vector> data structure have to be comparable to the store objects that exist outside of the Store struct. That is why the data member contains objects of self type because it has to store objects that are created outside the class within its own class instance and those stores have to be compared against other class instances that contain different sets of stores. I've thought about creating a separate or child class for defining the stores within the fish_types_to_stores_with_type_stocked data member as a possible workaround. But I might try redesigning the data member altogether. It just seemed like an intuitive solution at the time.

    If anything needs further explanation, let me know. I apologize in advance for not utilizing typedefs for more succinct naming schemes. I hope everything isn't too confusing. I can also include the full program if anyone feels that would be helpful. I just thought it was unnecessary for addressing this problem. I also apologize if anything seems largely inefficient. I'm still a novice programmer but am trying to learn. Suggestions are welcome. Thank you.
    Last edited by Kingdominth4; February 6th, 2020 at 07:11 PM.

  2. #2
    Arjay's Avatar
    Arjay is offline Moderator / EX MS MVP Power Poster
    Join Date
    Aug 2004
    Posts
    13,227

    Re: Why would modifying a vector member of self-type cause this program to run infini

    Did you look in task manager to see if the memory increases?

  3. #3
    VictorN's Avatar
    VictorN is offline Super Moderator Power Poster
    Join Date
    Jan 2003
    Location
    Hanover Germany
    Posts
    19,593

    Re: Why would modifying a vector member of self-type cause this program to run infini

    I am sorry for not helping you with your man problem, but I'd like to express some opinions about your coding manner.
    1. It is very hard to read/understand so long identifiers:
    Code:
    unordered_map<int, set<int>> required_fish_types_to_stocked_stores;
    unordered_map<int, set<Store, Store_Compare>> current_store_to_closest_neighboring_stores;
    ...
    2. you avoid using curly braces could help to better understand your code, like here:
    Code:
            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);
                    }
    
        }
    Better would be:
    Code:
            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);
                    }
                }
            }
        }
    3. It is very hard to read/understand and debug such an expression:
    Code:
            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];
    Last edited by Arjay; February 7th, 2020 at 04:07 AM. Reason: parentheses -> curly braces
    Victor Nijegorodov

  4. #4
    2kaud's Avatar
    2kaud is online now Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    6,997

    Re: Why would modifying a vector member of self-type cause this program to run infini

    I agree with Victor's post #3 re names. Even formatted, this code is very hard to read and understand.

    If within a struct/class type you want to use that type then there are issues around self-types. One way around this is to store a pointer to the type. So the vector definitions becomes:

    Code:
    vector<set<Store*, Store_Compare>> fish_types_to_stores_with_type_stocked;
    ie a set of pointers to Store objects, not the objects themselves.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++17 Compiler: Microsoft VS2019 (16.4.5)

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)