C++

Forum

 
Vector Copying Objects?

calioranged (67)
This program calls the 'standard constructor' twice and the copy constructor three times, but I really don't understand why. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
struct Vertex
{
	int x, y;

	Vertex(int x, int y) // standard constructor
		: x(x),y(y) 
	{
		std::cout << "Constructed" << std::endl;
	}

	Vertex(const Vertex& vertex) // copy constructor
		: x(vertex.x),y(vertex.y)
	{
		std::cout << "Copied" << std::endl;
	}
};

std::ostream& operator<<(std::ostream& stream, const Vertex& vertex)
{
	stream << vertex.x << ", " << vertex.y << std::endl;
	return(stream);
}

int main()
{
	std::vector<Vertex> vertices;
	vertices.push_back(Vertex(10,11));
	vertices.push_back(Vertex(20,21));


	std::cout << std::endl;

	for (unsigned int i = 0; i < vertices.size(); i++)
	{
		std::cout << vertices[i];
	}
}

Output:

Constructed
Copied
Constructed
Copied
Copied

10,11
20,21

------------------

I can see that from these two lines:

1
2
 
vertices.push_back(Vertex(10,11));
vertices.push_back(Vertex(20,21));

The standard constructor should be called twice, once on Vertex(10,11) and again on Vertex(20,21), but why are the objects being copied three times?
Last edited on
salem c (3700)
If you output the xy values as well, things might be clearer.
Peter87 (11239)
The vector stores its elements in an array, and when it runs out of space it allocates a new larger array and copies the elements over.

https://en.wikipedia.org/wiki/Dynamic_array
Grime (651)
Actually the vector tries to call the move constructor first, since you don't have one it used the copy constructor.

It has to do with how vectors work. Yes the constructor should have ideally called the copy constructor only twice, and that's what you'll notice if you try reserving memory for the two push_backs beforehand. 
1
2
3
4
 
	std::vector<Vertex> vertices;
	vertices.reserve(2);
	vertices.push_back(Vertex(10, 11));
	vertices.push_back(Vertex(20, 21));

output:
Constructed
Copied
Constructed
Copied

10, 11
20, 21


But since vectors are dynamic, they might have to move to a different location in memory. And when that happens, all elements previously in the vector call their move constructor to be moved to the new location.
calioranged (67)
But how can there be three copies if the vector has only been pushed back twice?

If I add another element, then there are six copies...

1
2
3
4
 
std::vector<Vertex> vertices;
vertices.push_back(Vertex(10,11));
vertices.push_back(Vertex(20,21));
vertices.push_back(Vertex(30,31));

Output:

Constructed
Copied
Constructed
Copied
Copied
Constructed
Copied
Copied
Copied

10,11
20,21
30,31

-----------------------

So just by adding one extra element, the 'standard' constructor was called once more and three more copies were made...
Grime (651)
1
2
3
 
Vertex(10,11)
Vertex(20,21)
Vertex(30,31)

These are calling your (int, int) constructor. The vector will only call your move/copy constructor and destructor.

The copy constructor is being called by the vector:

Vector{}
-> push A1
Move(A1) -> Vector{} -> Vector{A1}

Vector{}
->push A2
Move(A2) -> Vector{} -> Vector{A2}
Move(A1) from Vector{A1} to Vector{A2} -> Vector{A1, A2}

-------------

But can't the vector resize instead of reallocate? In that case there wouldn't be need to relocate the present elements when a new element is pushed in.
Peter87 (11239)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
std::vector<Vertex> vertices;
// The vector has room for no elements.
//  []
 
vertices.push_back(Vertex(10,11));
// The vector allocates an array of size 1 and copies Vertex(10,11)
// into the array (+1).
//  [Vertex(10,11)]

vertices.push_back(Vertex(20,21));
// The vector doesn't have any empty space in the array so it first
// has to allocate a new array and copy Vertex(10,11) over from 
// the old array (+1).
//  [Vertex(10,11), _]
// And finally it can copy Vertex(20,21) into the array (+1).
//  [Vertex(10,11), Vertex(20,21)]

vertices.push_back(Vertex(30,31));
// The vector again has to create a new array, and copy the the old 
// elements over (+2) ...
//  [Vertex(10,11), Vertex(20,21), _, _]
// ... before it can copy Vertex(30,31) into the array (+1).
//  [Vertex(10,11), Vertex(20,21), Vertex(30,31), _]

// Total number of copied: 1 + 1 + 1 + 2 + 1 = 6


Normally the size of the array grows exponentially (often doubling the size each time) so as you continue to add more elements it has to happen less and less frequently. If you had inserted a fourth element you might have seen that it only called the copy constructor one more time because it already had some space for a forth element.

std::vector is generally considered to be a fast for insertions at the end, but if you know beforehand how many elements you are going to insert you can avoid all the extra copying by using reserve as Grime mentioned.
Last edited on
Grime (651)
Peter, can't the vector expand instead of relocate? (sorry for shifting the topic)
(question is for any noble man (or woman), I said Peter because he was online + he's awesome)
Last edited on
calioranged (67)
The copy constructor is being called by the vector:

But why is it being called six times?

On the third push_back:

vertices.push_back(Vertex(30,31));

The (int,int) constructor is called (which is understandable), then the copy constructor is called three times, just on this one line. I could understand the copy/move constructor being called once for each push back, since from my understanding at least, the vector has to allocate a new vector, 1 element larger than the previous vector, and then copy all of those elements over from the previous vector to the newly allocated one. But why does it need to do this three times on one line?

If I re-write it slightly by reserving space for three elements:

1
2
3
4
5
6
 
	
std::vector<Vertex> vertices;
vertices.reserve(3);
vertices.push_back(Vertex(10,11));
vertices.push_back(Vertex(20,21));
vertices.push_back(Vertex(30,31));

Output:

Constructed
Copied
Constructed
Copied
Constructed
Copied

-----------------------

The copy/move constructor is called three times instead of six. Which is great, but I want gain a fundamental understanding of how this works behind the scenes and why the object is being copied so many times.
Last edited on
Peter87 (11239)
Grime wrote:
can't the vector expand instead of relocate?

You mean like realloc in C? No, my understanding is that it's not possible because of how allocators are specified to work.

calioranged wrote:
But why is it being called six times?

See my reply above.
Last edited on
JLBorges (13770)
> But how can there be three copies if the vector has only been pushed back twice?

first push back:
copy the anonymous temporary object into the vector's storage (copy #1)

second push_back:
allocate more memory, copy the old object in the vector into the newly allocated memory (copy #2)
copy the anonymous temporary object being pushed back into the vector's (new) storage (copy #3)


Run this program and study its output:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
 
#include <iostream>
#include <vector>

struct Vertex
{
	int x, y;

	Vertex(int x, int y) // standard constructor
		: x(x),y(y)
	{
		std::cout << "Constructed at " << this << '\n' ;
	}

	Vertex(const Vertex& vertex) // copy constructor
		: x(vertex.x),y(vertex.y)
	{
		std::cout << "copied from " << std::addressof(vertex)  << " to " << this << '\n' ;
	}

    /*
    Vertex( Vertex&& vertex) noexcept // move constructor
		: x(vertex.x),y(vertex.y)
	{
		std::cout << "moved from " << std::addressof(vertex)  << " to " << this << '\n' ;
	}
	*/

	~Vertex() = default ;
};

void debug_dump( const std::vector<Vertex>& vec )
{
    std::cout << "capacity: " << vec.capacity()
              << "  size: " << vec.size() ;
    if( !vec.empty() )
    {
        std::cout << "  storage starting at address: "
                  << std::addressof( vec.front() )
                  << "  elements are at [ " ;
        for( const Vertex& v : vec ) std::cout << std::addressof(v) << ' ' ;
        std::cout << ']' ;
    }

    std::cout << '\n' ;
}

int main()
{
    std::cout << "----------- original --------------\n" ;
    {
        std::vector<Vertex> vertices;
        debug_dump(vertices) ;
        vertices.push_back(Vertex(10,11));
        debug_dump(vertices) ;
        vertices.push_back(Vertex(20,21));
        debug_dump(vertices) ;
    }


    std::cout << "\n----------- reserve --------------\n" ;
    {
        std::vector<Vertex> vertices;
        vertices.reserve(10) ;
        debug_dump(vertices) ;
        vertices.push_back(Vertex(10,11));
        debug_dump(vertices) ;
        vertices.push_back(Vertex(20,21));
        debug_dump(vertices) ;
    }

    std::cout << "\n----------- emplace --------------\n" ;
    {
        std::vector<Vertex> vertices;
        debug_dump(vertices) ;
        vertices.emplace_back(10,11);
        debug_dump(vertices) ;
        vertices.emplace_back(20,21);
        debug_dump(vertices) ;
    }

    std::cout << "\n----------- reserve + emplace --------------\n" ;
    {
        std::vector<Vertex> vertices;
        vertices.reserve(10) ;
        debug_dump(vertices) ;
        vertices.emplace_back(10,11);
        debug_dump(vertices) ;
        vertices.emplace_back(20,21);
        debug_dump(vertices) ;
    }
}

http://coliru.stacked-crooked.com/a/f2bc22ced238f3cd

The un-comment the (non-throwing) move constructor and look at the output again:
http://coliru.stacked-crooked.com/a/9e8e36a8a57d821b
Last edited on
coder777 (8444)
can't the vector expand instead of relocate?
It can only expand if there are more elements allocated than used. When the preallocated memory is exhausted a reallocate is required.
calioranged (67)
Okay I am beginning to get a grasp of this now. Thanks for all the helpful replies above.

There are six copies because each individual element must be copied to the newly allocated vector each time the capacity of the vector is increased. By using reserve(required#of_elements), the capacity of the vector needn't be increased each time so only the new elements need to be copied over, rather than all existing elements plus the new elements.

Just two more questions:

1). Is there any difference between the following snippets (apart from that in the second snippet the objects are given a name):

1
2
3
4
 
std::vector<Vertex> vertices;
vertices.push_back(Vertex(10,11)); 
vertices.push_back(Vertex(20,21)); 
vertices.push_back(Vertex(30,31));
vs.
1
2
3
4
5
6
7
8
9
10
 
std::vector<Vertex> vertices;

Vertex v1(10, 11);
vertices.push_back(v1);
	
Vertex v2(20, 21);
vertices.push_back(v2);

Vertex v3(30, 31);
vertices.push_back(v3);

2). 'vertices' is an object belonging to the 'std::vector' class. Is 'vertices' also an object belonging to the 'Vertex' class? If not, how does it call the Vertex copy constructor? And if so, can anyone shed some light on this particular syntax:

vertices.push_back(v1);

The '.' after 'vertices' opens up access to 'std::vector' members/methods, but not to 'Vertex' members/methods. By specifying an index:

vertices[1].x = 11;

The members/methods of 'Vertex' can also be accessed. So if a particular index needs to be specified in order for us to access the 'Vertex' members/methods, then how is it that the 'Vertex' copy constructor is called without this index being specified?

If it was written something like:

vertices[1].push_back(v1);

Then it would kind of make more sense (or would it..? feel free to correct).

This question was rather difficult for me to articulate, so I apologise if my attempted explanation is confusing, but hopefully someone manages to grasp what I am saying and can shed some light on how the 'Vertex' copy constructor is called without an index being specified, whilst other members/methods belonging to 'Vertex' can only be called when a particular index is specified.
Last edited on
Grime (651)
(1) In the first snippet: Objects are created with the (int, int) constructor and moved into the vector. The scope of the objects created is within the parenthesis.

In the second snippet: v1, v2, v3 are static objects who have scope like any other static object. They are 'copied' into the vector.

(2) vertices is an object of type vector<Vertex> which happens to contain an array of Vertex objects.
You can use indexes [] to access a Vertex object within the array.

So vertices[0] is translated as the first Vertex object of the array.

When you write: vertices[1].x = 11;, [] is an operator. You're using the operator to return the second Vertex object. Now like a regular vertex object you can access its members by using the (.) operator.

Hope that makes sense? .-.
keskiverto (10402)
Is 'vertices' also an object belonging to the 'Vertex' class? If not, how does it call the Vertex copy constructor?
vertices.push_back(v1);
The '.' after 'vertices' opens up access to 'std::vector' members/methods, but not to 'Vertex' members/methods.


The vertices is a vector: std::vector<Vertex> vertices;
It has Vertex elements.

vector::push_back(): http://www.cplusplus.com/reference/vector/vector/push_back/
Adds a new element at the end of the vector, after its current last element. The content of val is copied (or moved) to the new element.


Pseudo for push_back(val):
1
2
3
4
 
auto index = vertices.size();
make sure that index < vertices.capacity() (realloc, if necessary)
vertices[index] = val; // copy (or move) construct the Vertex
vector::size += 1;


In other words, the vector::push_back has access to the (Vertex) elements that the vector owns.
Just like you have access via the [] operator (and then some).


JLBorges did use vector::emplace_back. Did you look at its features?
calioranged (67)
vertices is an object of type vector<Vertex> which happens to contain an array of Vertex objects.
You can use indexes [] to access a Vertex object within the array.

So vertices[0] is translated as the first Vertex object of the array.

When you write: vertices[1].x = 11;, [] is an operator. You're using the operator to return the second Vertex object. Now like a regular vertex object you can access its members by using the (.) operator.

Yes, I understand this. My question is how can 'vertices' call the 'Vertex' copy constructor without specifying a particular index.

It's the way the line:

vertices.push_back(Vertex(10,11));

is written that is confusing me. 'vertices' is calling push_back which is an 'std::vector' member function. How can it ALSO call the 'Vertex' copy constructor in the same line, seeing as though the '.' after 'vertices' only opens up access to the 'std::vector' members/methods and not 'Vector' members methods?

If you type 'vertices' and then place a dot (.) directly after to access the 'vertices' object, you can only access the 'std::vertex' members/methods. You CANNOT access the members/methods of 'Vertex' this way. So how is it that the copy constructor (member of 'Vertex', not 'std::vector') is called this way?

As I mentioned, you can access 'Vertex' members/methods if you specify a particular index, but this is not present in the line:

vertices.push_back(Vertex(10,11));

No index was specified, so theoretically only 'std::vector' members/methods can be called, NOT 'Vector' members/methods, but the copy constructor WAS called without specifying the index, so how did this happen?

Last edited on
Grime (651)
First Vertex(10, 11) is created using the (int, int) constructor. As it is the argument of push_back, the vector needs to make a new Vertex object that resembles the passed argument. So it creates a Vertex object, but since it needs to resemble the passed argument, it calls the copy/move constructor for the to be created Vertex object by using Vertex(10, 11) which was passed to push_back().

I say don't bother about this if it's confusing, and it is confusing at first. You'll eventually learn it so don't stress this small little detail.
calioranged (67)
Yeah I can't get my head around it still, but think maybe I am focusing too much on this small detail. Like you say I will probably get used to it eventually anyway. Thanks a lot for everyone's help.
Last edited on
Peter87 (11239)
The call to the copy constructor is made inside the push_back function.
Last edited on
calioranged (67)
The call to the copy constructor is made inside the push_back function.

Okay that makes a lot of sense. I feel as though I have a decent understanding of how this works now. Thanks again to everyone who helped.
Last edited on
Topic archived. No new replies allowed.