ベクトルの要素を削除する

Question

私はクラスのすべてのオブジェクト（newによって作成された）のポインタを格納するためのベクトルを持っています。 私はオブジェクトのアドレスが格納されているベクトル要素のインデックスを格納するオブジェクトごとに、intメンバ変数（id）を持っています。 このメソッドは、idの助けを借りてオブジェクトを呼び出すのに役立ちます。 は、オブジェクトが作成されるたびにインクリメントされる静的変数の助けを借りて、コンストラクタ内で割り当てられます。 私の問題は、オブジェクトを削除すると、ベクター要素を削除することができないということです（ベクトルを動的に作成するので、その要素がとるメモリを解放することはできません）（削除すると次の要素のインデックスが減少する1）。 私はベクトルからメモリを解放することができますが、他の要素のインデックスの変更を引き起こさない方法を知りたいと思います。 多くの時間を消費しない方法を教えてください。 （&の並べ替えのような方法の場合、各オブジェクトのidを変更すると多くの時間がかかります） 上記のように1番目の要素&を削除すると、多くの時間がかかることがあります。 ありがとうございました

Answer 1

vector<your_object_type*>の代わりにmap<int,your_object_type*>を使用することをおすすめします。次に、アイテムを削除するときに「再インデックスする」必要はなく、（もっと重要なことには）IDを再割り当てする必要はありません。

Answer 2

エレメントを新規に作成するたびに最初に確認する再利用可能なスロット/ IDのリストがあります。あなたは、再利用可能なIDのリストに要素のidを追加する要素を削除する場合：

//Somewhere in the code 
vector<Object*> s_objects; 
vector<int> s_freeIds; 

//On new: 
if (s_freeIds.empty()) 
{ 
    s_objects.push_back(new Object()); 
    s_objects.back().id = s_objects.size() - 1; 
} 
else 
{ 
    int id = s_freeIds.back(); 
    s_freeIds.pop_back(); 
    s_objects[id] = new Object(); 
    s_objects[id].id = id; 
} 

//On delete 
s_freeIds.push_back(this->id); 

Answer 3

あなただけ要素再配置する必要がありますへの要素の位置にswapベクトルの最後の要素を削除し、最後の要素を削除します。

int to_delete = …; 
swap(my_vec[to_delete], my_vec[my_vec.end() - 1]); 
my_vec[to_delete].index = to_delete; 
delete my_vec.back(); 

Answer 4

あなたのデザインは非常に珍しいです。オブジェクトの位置を置いておきたい場合は、ベクトルを使うのが最善の選択肢ではありません。オブジェクトをリストに格納したり、設定したり、マップしたりすることができます。これらはすべて、オブジェクトが削除されたときにオブジェクトの位置を保持します。あなたはidの代わりにポインタを使ってオブジェクトにアクセスすることができます（マップでは両方を使用できます）

何らかの理由でベクターを絶対に使用する必要がある場合は、「スワップアンドポップ」トリックを使用してオブジェクトを削除できます。オブジェクトが削除されると、それをベクトルの最後の要素と交換し、最後の要素を削除するためにpop_back（）を呼び出します。移動したばかりの要素を新しいIDで更新する必要があります。しかし、操作は一定の時間内に実行されます。

Answer 5

最も簡単な解決策は、ベクトル から要素を削除しないことですが、単純にnullポインタで置き換えてください。これは、完全なベクトルを反復処理するときに があることを意味します。null ポインタをチェックする必要がありますが、それは通常大きな問題ではありません。 ベクターが無限に拡大するのを防ぐには、スロットを再利用できるようにする必要があります。 にヌルポインタ（std::find）が挿入されているベクトルをスキャンするか、空きスロットのリストを何らかの形で保持します。

idをベクターのインデックスとして使用する場合は、 は独立して生成しないことに注意してください。 push_back（ベクトルにヌルポインタがないため）を挿入すると、ID はpush_backの後にv.size() - 1、または前には単にv.size()になります。 std::findが返すイテレータを使用して特定の場所に挿入すると、識別子はイテレータ - v.begin()になります。あなただけ（1000の 要素と小さくベクターで、これはおそらく十分である）、線形検索を使用している 場合は、次の ようなものが動作するはずです：

//  returns index of inserted element 
int 
insertIntoVector(std::vector<MyType*>& index, MyType* newObject) 
{ 
    std::vector<MyType*>::iterator position 
      = std::find(index.begin(), index.end(), NULL); 
    int results = position - index.begin(); 
    if (position == index.end()) { 
     index.push_back(newObject); 
    } else { 
     *position = newObject; 
    } 
    return results; 
} 

をあなたは自由をキャッシュしている場合スロットの場合は、std::findを 相当のコードに置き換えて空きスロットを見つけます。

Answer 6

実際の質問：なぜあなたはvectorを使用していますか？

まず、IDの生成について：

typedef size_t ID; 

static ID& accessID() { static ID id = 0; return id; } 

ID currentID() { return accessID(); } 
ID newID() { return ++accessID(); } 

第二に、これは典型的な工場の状況なので、私たちはFactory実装を提供しましょう。

class ObjectFactory { 
    typedef std::unordered_map<ID, Object> Register; 

public: 
    Object& create() { 
    ID const id = newID(); 
    return register.insert(std::make_pair(id, Object(id))).first->second; 
    } 

    Object* access(ID id) { 
    Register::iterator it = register.find(id); 
    return it == register.end() ? nullptr : &it->second; 
    } 

    Object const* get(ID id) const { 
    Register::const_iterator it = register.find(id); 
    return it == register.end() ? nullptr : &it->second; 
    } 

    bool remove(ID id) { 
    return register.erase(id); 
    } 

private: 
    Register register; 
}; 

現在のID工場のメンバーを作成することを選択するか、別の工場をしたいとIDをアップミキシングを恐れている場合にはそれを離れて保つことがあります。