0

假设我有一张想要复制的城市地图。问题是from和to在road类中是该特定cityMap对象的内存指针。使一个新对象独立于被复制的对象将意味着每个城市将具有不同的指针值。在要复制的道路和我在方法中创建cityMap的新道路之间建立对应关系的智能方法是什么？cityMapcopy

想法 1（更慢，我认为它很丑）是使map<road *, road *>.

想法 2（我觉得这很丑陋，因为它向较低的类添加了一个成员，该成员不需要作为一个概念来实现该类，但在 O(N) 构造时间之后是 O(1) 查找时间）是有一个成员road那就是road *correspondingRoad。那么，我只能说newRoad->to = oldRoad->to->correspondingRoad。

有没有一个很好的方法来设置这一切？我想要 O(1) 查找时间（不是地图），没有太多的施工时间（不是地图），并且让道路类不受无关类想要的东西的影响。也就是说，与完全相同的道路对应的新创建的道路不是道路概念的一部分，它只是复制城市地图的概念的一部分。

class cityMap
{
public:
    vector<roads *> allRoads    // all raods in the area
    vector<city *> cities;      // all the cities in the area
    cityMap *copy();            // makes a copy of the entire map
};

class roads
{
public:
    city *from, *to;
}

class city
{
public:
    vector<raod *> roads;       // roads from this city to another city
}
4

1 回答 1

1

如果我理解正确，我认为您想要执行城市地图的深层复制，并且正在寻找一种可以有效确保新对象之间的关系与旧对象之间的关系相同的方法。

我同意想法 2，在道路上有一个额外的成员来表示从旧到新的映射，这是可怕的。但是我看不出想法 1 有什么问题，使用 amap来表示从原始道路到新道路的映射，尽管我认为您还需要从旧城市到新城市以及从旧道路到新道路的映射. 如果你有map，它只是一张临时地图，只在你的copy方法中需要，你在新城市地图上的操作可能比复制花费更多的时间。此外，amap是一个库类，因此将得到很好的优化。如果您使用 C++11（或可以访问 boost），则可以使用形状为 的哈希映射，unordered_map它为您提供平均 O(1) 而不是对数查找。这种方法给出：

using std::vector;
using std::unordered_map;

class road;
class city;

class cityMap
{
public:
    vector<road *> allRoads;    // all raods in the area
    vector<city *> cities;      // all the cities in the area
    cityMap *copy()             // makes a copy of the entire map
    {
        cityMap* pNewCityMap = new cityMap;
        // create new cities, building up old city to new city map
        unordered_map<city*, city*> city2city;
        for(city* pOldCity: cities) {
            city* pNewCity = new city(*pOldCity);
            pNewCityMap->cities.push_back(pNewCity);
            city2city[pOldCity] = pNewCity;
        }
        // create new roads, building up old road to new road map
        unordered_map<road*, road*> road2road;
        for(road* pOldRoad: allRoads) {
            road* pNewRoad = new road(city2city[pOldRoad->from], city2city[pOldRoad->to]);
            pNewCityMap->allRoads.push_back(pNewRoad);
            road2road[pOldRoad] = pNewRoad;
        }
        // fix up roads in new cities
        for(city* pNewCity: pNewCityMap->cities) {
            for(road*& pNewRoad: pNewCity->roads) {
                pNewRoad = road2road[pNewRoad];
            }
        }
        return pNewCityMap;
    }
};

class road
{
public:
    city *from, *to;
    road(city* _from, city* _to) : from(_from), to(_to) {}
};

class city
{
public:
    vector<road *> roads;       // roads from this city to another city
};

另一种方法是受 celtschk 的评论启发，使用索引来表示道路。在这种情况下，城市地图仍然可以返回一个road类，但必须根据索引在内部存储其道路。下面是一个草图实现。

using std::pair;
typedef size_t roadnum;

class city2
{
public:
    vector<roadnum> roads;       // roads from this city to another city
};

class road2
{
public:
    city2 *from, *to;
    road2(city2* _from, city2* _to) : from(_from), to(_to) {}
};

class cityMap2
{
    vector<pair<size_t, size_t>> allRoads;    // all raods in the area, pairs of city indices
public:
    vector<city2 *> cities;      // all the cities in the area
    cityMap2 *copy();             // makes a copy of the entire map

    size_t GetNumberRoads() const { return allRoads.size(); }
    road2 GetRoad(size_t which) const
    {
        const pair<size_t, size_t>& citycity = allRoads[which];
        return road2(cities[citycity.first], cities[citycity.second]);
    }
};
于 2013-06-09T23:23:03.683 回答