How to find common value [closed]

I have an area struct where i store upper_area. The struct is in map with AreaID as a key. Area can have direct upper_Area or indirect upper_area

struct Area
{
    AreaID area_id_;
    Name name_;
    std::vector<Coord> coords_;
    std::vector<Area*> lower_areas_;
    Area* upper_area_ = nullptr;
    bool check_area_ = false;
};

The null pointer will be change to point into area in another function.

I need to find the common upper area between two areas. Indirect areas must be taken into account. The common area closest to the two area in area hierarchy must be choose.

I have made this code beforehand

AreaID Datastructures::common_area_of_subareas(AreaID id1, AreaID id2)
{
    std::unordered_map<AreaID, Area>::iterator area1 = areas_.find(id1);
    if (area1 == areas_.end()) {
        return NO_AREA;
    }

   std::unordered_map<AreaID, Area>::iterator area2 = areas_.find(id2);
   if (area2 == areas_.end()) {
       return NO_AREA;
   }
   bool check = true;
   while (check) {
      AreaID area_id1 = area1->second.upper_area_->area_id_;
      AreaID area_id2 = area2->second.upper_area_->area_id_;
      if () {
        
    }
}

return common_id;
}

Is there faster way to find the common area without double for loop where you compare all of the items two time? Anyt help would be appreciated.

Answer

I don’t think that you can avoid having two loops.

starting from here, you could do

AreaID Datastructures::common_area_of_subareas(AreaID id1, AreaID id2)
{
    std::unordered_map<AreaID, Area>::iterator areaIt1 = areas_.find(id1);
    if (areaIt1 == areas_.end()) {
        return NO_AREA;
    }

    std::unordered_map<AreaID, Area>::iterator areaIt2 = areas_.find(id2);
    if (areaIt2 == areas_.end()) {
        return NO_AREA;
    }

    const Area& area1 = areaIt1->second;
    const Area& area2 = areaIt2->second;

    // get list of all parent ids from first area
    // use set for easier lookup
    std::set<AreaID> upper_area_ids;
    Area* upper_area_ptr = area1.upper_area_
    while(upper_area_ptr != nullptr) {
        const AreaID &parent_id = upper_area_ptr->area_id_;
        upper_area_ids.insert(parent_id);

        upper_area_ptr = upper_area_ptr->upper_area_;
    }

    // move upward from second area and return on first common parent
    upper_area_ptr = area2.upper_area_;
    while(upper_area_ptr != nullptr) {
        const AreaID &parent_id = upper_area_ptr->area_id_;
        if (upper_area_ids.find(parent_id) != upper_area_ids.end()) {
            // success-case
            return parent_id;
        }

        upper_area_ptr = upper_area_ptr->upper_area_;
    }

    return NO_COMMON_PARENT;
}

Because the two while loops are not nested, the execution time is linear with the tree depth and thus hard to optimize any further.

One last advice from my side: Please try to stick to a consistent naming convention for variables and style formatting of your code. This simplifies collaboration with others, such as responders on Stack Overflow.