0

コピーを作成したい市の地図があるとします。問題は、クラス内の と がその特定のオブジェクトのメモリ内のポインターであるfromことです。コピーされるオブジェクトとは独立した新しいオブジェクトを作成するということは、各都市が異なるポインター値を持つことを意味します。コピーされる道路とメソッドで作成された新しい道路との間の対応を作成するインテリジェントな方法は何ですか?toroadcityMapcityMapcityMapcopy

アイデア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 は恐ろしいことに同意します。mapただし、古い道路から新しい道路へのマッピングだけでなく、古い都市から新しい都市へのマッピングも必要になると思いますが、 a を使用して元の道路から新しい道路へのマッピングを表すアイデア 1 には多くの間違いはありません。 . を持っている場合map、それは一時的なマップであり、メソッド中にのみ必要でcopyあり、新しい都市マップでの操作はおそらくコピーよりも時間がかかります. さらに、 amapはライブラリ クラスであるため、かなり最適化されます。C++11 を使用している (またはブーストにアクセスできる) 場合は、ハッシュ マップを の形で使用できます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 に答える