c++ - 使指向同一类的两个不同指针之间建立对应关系

Question

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

想法 1(较慢，我认为它很难看)是制作 map<road *, road *> .

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

有什么好的方法可以设置所有这些吗？我想要 O(1) 的查找时间(不是 map )，没有太多的构建时间(不是 map )，并且让道路类不受无关类的要求影响。也就是说，新建一条路对应同一条路，不属于路的概念，只是复制城市 map 的概念的一部分。

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
}

Answer 1

如果我没理解错的话，我想你想对你的城市 map 执行一个深拷贝，并且正在寻找一种方法来有效地确保你的新对象之间的关系是正确的和旧的关系一样。

我同意想法 2，在道路上增加一个成员来表示从旧到新的映射，这是可怕的。但是我看不出想法 1 有什么问题，使用 map 来表示从原始道路到新道路的映射，尽管我认为您还需要从旧城市映射到新城市以及从旧路到新路。如果你有一张 map，它只是一张临时 map ，只在你的 copy 方法中需要，你对新城市 map 的操作可能会比复制。此外，map 是一个库类，因此将得到很好的优化。如果您使用的是 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 的评论启发，使用索引来表示道路。在这种情况下，城市 map 仍然可以返回 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]);
    }
};