CODEWITHSUNDEEP
c++c++11pointersvectorset
Yeo
Yeo

Reputation: 11784

How to construct a new vector/set of pointer from another vector/set of object?

Background

I wanted to manipulate the copy of a vector, however doing a vector copy operation on each of its element is normally expensive operation.

There are concept called shallow copy which I read somewhere is the default copy constructor behavior. However I'm not sure why it doesn't work or at least I tried to do the copy of vector object and the result looks like a deep copy.

struct Vertex{
    int label;
    Vertex(int label):label(label){ }
};

int main(){
    vector<Vertex> vertices { Vertex(0), Vertex(1) };

    // I Couldn't force this to be vector<Vertex*>      
    vector<Vertex> myvertices(vertices); 

    myvertices[1].label = 123;

    std::cout << vertices[1].label << endl; 
    // OUTPUT: 1 (meaning object is deeply copied)

    return 0;
}

Naive Solution: for pointer copy.

int main(){
    vector<Vertex> vertices { Vertex(0), Vertex(1) };

    vector<Vertex*> myvertices;
    for (auto it = vertices.begin(); it != vertices.end(); ++it){
        myvertices.push_back(&*it);
    }

    myvertices[1].label = 123;

    std::cout << vertices[1].label << endl;
    // OUTPUT: 123 (meaning object is not copied, just the pointer)

    return 0;
}

Improvement

Is there any other better approach or std::vector API to construct a new vector containing just the pointer of each of the elements in the original vector?

Upvotes: 0

Views: 142

Answers (2)

Yeo
Yeo

Reputation: 11784

Thanks for @kfsone for noticing on the main problem that it is very uncommon people wanted to keep track of pointer from another vector of object without utilizing the core idea behind it. He provided an alternative approach that solve similar problem by using bit masking. It may not be obvious for me at first until he mentioned that.

When we are trying to store just the pointers of another vector, we are most probably wanted to do some tracking, house keeping (keeping track) of another object. Which later to be performed on the pointer itself without touching the original data. For my case, I'm solving a minimum vertex cover problem via bruteforce approach. Whereby I will need to generate all permutation of vertices (e.g. 20 vertices will generate 2**20=1million++ permutation), then I trim down all irrelevant permutation by slowly iterating each of the vertices in the vertex cover and remove edges that are covered by the vertices. In doing so, my first intuition is to copy all pointers to ensure efficiency and later i could just remove the pointer one by one.

However, another way of looking into this problem is not to use vector/set at all, but rather just keep track each of those pointer as a bit pattern. I won't go in the detail but feel free to learn from others.

The performance difference is very significant such that in bitwise, you can achieve O(1) constant time without much problem, whereas using a specific container, you tend to have to iterate each of the elements which bound your algorithm to O(n). To make it worst, if you are bruteforcing NP hard problem, you need to keep the constant factor as low as possible, and from O(1) to O(N) is a huge difference in such scenario.

Upvotes: 0

Dimitrios Bouzas
Dimitrios Bouzas

Reputation: 42889

One way you could transform a vector of elements to a vector of pointers that point to the elements of the original vector that is better in terms of efficiency compared to your example, due to the fact that it preallocates the buffer of the vector of pointers, and IMHO more elegant is via using std::transform as follows:

std::vector<Vertex*> myvertices(vertices.size());
std::transform(vertices.begin(), vertices.end(), myvertices.begin(), [](Vertex &v) { return &v; });

Live Demo

Or if you don't want to use a lambda for the unary operator:

std::vector<Vertex*> myvertices(vertices.size());
std::transform(vertices.begin(), vertices.end(), myvertices.begin(), std::addressof<Vertex>);

Live Demo

Caution: If you alter the original vector then you invalidate the pointers in the pointers' vector.

Upvotes: 2

Related Questions