2

I have a vector that stores multiple instances of a type T:

std::vector<T> vec;

From time to time, vec is being sorted for different purposes. Now, I need a list of pairs of objects stored in vec, but (because of the reordering of vec) simply storing the indices is not suitable. Using the list of pairs, I would like to obtain actual indices of the paired objects in vec. Additionally, any of the objects could be paired with more than one other objects (or none of them).

Is there any efficient way to build such a list for querying pairs of objects without searching based on for instance object identifiers?

What I have done so far:

I am trying to implement a class Node that manages two-way connections in such a way that the member pointers of two Node objects (pairs) always point to each other. Here is a sketch of the abstraction of two Node objects:

enter image description here

Copy constructors set all pointers once one of the objects is moved or copied to a different location in the vector alongside with vec. The vector of the Nodes could be sorted the same way as vec.

An example of the objects stored in vec:

enter image description here

Finally, the containers of the links, nodes, and vec according to the layout above:

enter image description here

However, this implementation seems to be a bit complicated. So, is there a mesh data structure that allows the sorting of the vector of vertices?

Note: The number of objects in vec could be tens of thousands.

  • Would you give me a feedback after giving a downvote? That could be useful for me to find a solution to the problem. – BalazsToth Apr 6 '18 at 13:06
  • 1
    It sounds like you want some kind of "kitchen sink" collection, perhaps a sorted, indexable dictionary that allows duplicates, but it's hard to tell from your question. See also What is the X Y Problem? – Robert Harvey Apr 6 '18 at 14:46
3

If you want shared ownership of the objects, referencing them from both the vector and another collection of pairs, then you probably want something like a std::vector<std::shared_ptr<T>>. This way the vector can move/reorder the pointers however much it wants, and the actual pointed-to objects will still be in the same place, and copies of the std::shared_ptr<T> will continue to be valid.

If you want true shared ownership you can have a std::vector<std::shared_ptr<T>> then store std::shared_ptr<T> in the other container. Or you can have a std::vector<std::shared_ptr<T>> but store std::weak_ptr<T> in the other collection, in which case the object will be freed when the vector releases its ownership. Lastly, you could have a std::vector<std::unique_ptr<T>> then store a T& in the other container, if you can be absolutely certain that the references will not outlive the unique_ptrs.

  • This could be a solution, but unfortunately, the vector of objects is given, and cannot be changed to store shared_ptr objects. – BalazsToth Apr 6 '18 at 16:43
  • Well, I don't think there's any good way to do what you want without changing it. If you just have a vector of T then the Ts themselves are stored contiguously in memory, and any pointers or references to them will be invalidated when the vector reallocates. If you also can't store indexes, because these will be invalidated when the vector is sorted/reordered, then I don't know what else to suggest. Why can you not change the type of the vector? – Sean Burton Apr 9 '18 at 9:29
  • The vector is a member of a parent class in a larger project in which it is simply not possible to make changes to the extension I am working on. On the other hand, storing every single one of the tens of thousands of small objects in shared pointers seems to be undesirable. Recently, I managed to create a Mesh class that stores object indices in a list of pairs that is updated immediately after sorting the vector. It simply updates the indices of each object to mark new positions. It is probably not the most elegant way, but it works. I will present the solution in the following days. – BalazsToth Apr 10 '18 at 13:33
0

Giving up the attempt to implement the complicated solution I have shown in my question, I managed to solve the problem in a much simpler way.

I've constructed a Mesh class that stores pairs of indices (of the objects stored in vec). After sorting vec, the sorting order needs to be given to the Mesh, which figures out the new indices in each pair in the list and overwrites the previous state. Pairs can be added, deleted and acquired through the public member functions. The order of pairs is never changed in the list (ith pair will remain the ith one, except for the case of deletions).

Here is the code of the Mesh class, and a few functions required for sorting. There could be potentials for optimization (suggestions are welcome and appreciated).

#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);
    }
};

And a simple 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.