Qual è la migliore pratica per l'associazione di oggetti di un vettore ordinato?

Se vuoi condividere la proprietà degli oggetti, facendo riferimento a essi sia dal vettore che da un'altra raccolta di coppie, probabilmente vorrai qualcosa come std::vector<std::shared_ptr<T>> . In questo modo il vettore può spostare / riordinare i puntatori per quanto desidera e gli oggetti puntati saranno ancora nella stessa posizione e le copie di std::shared_ptr<T> continueranno ad essere valide.

Se desideri una proprietà condivisa vera, puoi avere std::vector<std::shared_ptr<T>> e quindi memorizzare std::shared_ptr<T> nell'altro contenitore. Oppure puoi avere un std::vector<std::shared_ptr<T>> ma memorizzare std::weak_ptr<T> nell'altra raccolta, nel qual caso l'oggetto verrà liberato quando il vettore ne rilascerà la proprietà. Infine, potresti avere un std::vector<std::unique_ptr<T>> quindi memorizzare un T& nell'altro contenitore, se puoi essere assolutamente certo che i riferimenti non sopravviveranno a unique_ptrs.

Rinunciando al tentativo di attuare la soluzione complicata che ho mostrato nella mia domanda, sono riuscito a risolvere il problema in un modo molto più semplice.

Ho costruito una classe Mesh che memorizza coppie di indici (degli oggetti memorizzati in vec ). Dopo aver ordinato vec , è necessario fornire l'ordine di ordinamento alla mesh, che individua i nuovi indici in ciascuna coppia nell'elenco e sovrascrive lo stato precedente. Le coppie possono essere aggiunte, cancellate e acquisite attraverso le funzioni dei membri pubblici. L'ordine delle coppie non viene mai modificato nella lista (la coppia rimarrà l'ith, tranne per il caso di delezioni).

Questo è il codice della classe Mesh e alcune funzioni richieste per l'ordinamento. Potrebbero esserci potenziali per l'ottimizzazione (i suggerimenti sono benvenuti e apprezzati).

#include <vector>
#include <array>
#include <algorithm>
#include <numeric>
#include <iostream>

template <typename T> bool ascending(std::pair<T,int> const& a, std::pair<T,int> const& b) {
    return a.second < b.second;
}

template <typename T> bool descending(std::pair<T,int> const& a, std::pair<T,int> const& b) {
    return a.second > b.second;
}

/////////////////////////////////////////////////////////////////////////////////////////
/// Pairs the givan a and b vectors and stores the result in the packed vector.
/////////////////////////////////////////////////////////////////////////////////////////
template <typename T> void pack(std::vector<T> const& a, std::vector<int> const& b, std::vector<std::pair<T,int>>& packed) {
    for(size_t i=0; i<a.size(); ++i) {
        packed.push_back(std::make_pair(a[i], b[i]));
    }
}

/////////////////////////////////////////////////////////////////////////////////////////
/// Separates the vectors stored in the given vector of pairs and stores them in the a and b vectors.
/////////////////////////////////////////////////////////////////////////////////////////
template <typename T> void unpack(std::vector<std::pair<T,int>>& packed, std::vector<T>& a, std::vector<int>& b) {
    for(size_t i=0; i<a.size(); ++i) {
        a[i] = packed[i].first;
        b[i] = packed[i].second;
    }
}

/////////////////////////////////////////////////////////////////////////////////////////
/// Sorts a vector based on another. The third parameter governs the order.
/////////////////////////////////////////////////////////////////////////////////////////
template <typename T> void sort_by_vector(std::vector<T>& to_sort, std::vector<int>& sort_by, bool(*compare)(std::pair<T,int> const&, std::pair<T,int> const&)) {
    using Pair = std::pair<T,int>;
    std::vector<Pair> packed;
    pack<T>(to_sort, sort_by, packed);
    std::sort(std::begin(packed), std::end(packed), compare);
    unpack<T>(packed, to_sort, sort_by);
}


class Mesh {
    std::vector<int> first;
    std::vector<int> second;

    std::vector<int> sorted_first;
    std::vector<int> sorted_second;

    std::vector<int> start_first;
    std::vector<int> end_first;
    std::vector<int> start_second;
    std::vector<int> end_second;
private:
    void sort_lists(std::vector<int>& sorted_pair_idx, std::vector<int> const& pair_vec) {
        sorted_pair_idx.resize(pair_vec.size());
        std::iota(sorted_pair_idx.begin(), sorted_pair_idx.end(), 0);
        std::vector<int> copy = pair_vec;
        sort_by_vector(sorted_pair_idx, copy, ascending);
    }
    void update_helper_vectors(std::vector<int>& start, std::vector<int>& end, std::vector<int> const& sorted_pair_idx, std::vector<int> const& pair_vec, int const& N) {
        start.resize(N);
        end.resize(N);
        std::fill(start.begin(),start.end(),0xFFFFFFFF);
        std::fill(end.begin(),end.end(),0xFFFFFFFF);
        int count = 0;
        for(int i=0; i<N; i++) {
            int count_start = count;
            for(int j=count; j<sorted_pair_idx.size(); j++) {
                if(pair_vec[sorted_pair_idx[j]]==i) {
                    count++;
                }
            }
            int count_end = count-1;
            if(count_start<=count_end) {
                start[i] = count_start;
                end[i] = count_end;
            }
        }
    }

    void update_pairs(std::vector<int>& pair_vec, std::vector<int> const& sorted_pair_idx, std::vector<int> const& start, std::vector<int> const& end, std::vector<int> const& sorted_particle_idx) {
        for(int i=0; i<sorted_particle_idx.size(); i++) {
            int old_id = sorted_particle_idx[i];
            int new_id = i;
            int start_id = start[old_id];
            int end_id = end[old_id];
            if(start_id!=0xFFFFFFFF) {
                for(int j=start_id; j<=end_id; j++) {
                    pair_vec[sorted_pair_idx[j]] = new_id;
                }
            }
        }
    }
public:
    // Adds a pair of indices to the list
    void add_link(int const& i1, int const& i2) {
        first.push_back(i1);
        second.push_back(i2);
    }
    // Returns the ith pair (link)
    std::pair<int,int> get_link(int const& i) const {
        return std::pair<int,int>{first[i], second[i]};
    }
    // Removes the ith pair (link)
    void delete_link(int const& i) {
        first.erase(first.begin()+i);
        second.erase(second.begin()+i);
    }
    // Updates indices in the list according to the given array
    void sort_mesh(std::vector<int> const& sorted_particle_idx) {
        sort_lists(sorted_first, first);
        sort_lists(sorted_second, second);
        update_helper_vectors(start_first, end_first, sorted_first, first, sorted_particle_idx.size());
        update_helper_vectors(start_second, end_second, sorted_second, second, sorted_particle_idx.size());
        update_pairs(first, sorted_first, start_first, end_first, sorted_particle_idx);
        update_pairs(second, sorted_second, start_second, end_second, sorted_particle_idx);
    }
};

E un semplice test:

int main() {
    Mesh mesh;
    mesh.add_link(3, 0);
    mesh.add_link(3, 4);
    mesh.add_link(0, 4);
    mesh.add_link(0, 2);
    mesh.add_link(1, 0);
    mesh.add_link(2, 1);
    mesh.add_link(4, 5);
    mesh.add_link(3, 2);

    std::vector<int> particles{63, 109, 20, 17, 54, 106};
    std::vector<int> sorted_particle_idx{0,1,2,3,4,5};
    sort_by_vector(sorted_particle_idx, particles, ascending);
    mesh.sort_mesh(sorted_particle_idx);

    for(auto const& it:sorted_particle_idx) {
        std::cout << it << std::endl;
    }
    std::cout << std::endl;
    for(int i=0; i<8; i++) {
        std::pair<int,int> par = mesh.get_link(i);
        std::cout << par.first << " " << par.second << std::endl;
    }

    return 0;
}

Compilation:

g++ -std=c++11 main.cpp -o main