std::vector: contiguous data and copy/move

Question

I have two questions for the following code: 1) Will the elements of faces be contiguous? 2) Does std::vector copy or move Face f when inserting it?

#include <vector>    
int main()
{
    struct Face {};
    std::vector<Face> faces;

    for (int i=0; i<10; ++i)
    {
        Face f;

        faces.push_back (f);
    }

    return 0;
}

If you're worried about it copying or moving it (it's a move in this particular case) - why not use `.emplace`? — Benjamin Gruenbaum, Jun 21 '14 at 22:04
@BenjaminGruenbaum: Both `push_back` and `emplace_back` will use the copy constructor to create the object within the `std::vector` (in this example). — nosid, Jun 21 '14 at 22:14
@nosid I meant - rather than create it outside the loop, emplace it in the loop. I'd love to hear why that would not be able to utilize move semantics though. I was under the impression gcc and clang would trivially do this (assuming a struct that isn't "empty") — Benjamin Gruenbaum, Jun 21 '14 at 22:16
FYI the existance of default move assignment operator & move constructor might [depend on your environment](http://stackoverflow.com/questions/4819936/why-no-default-move-assignment-move-constructor) — Scis, Jun 21 '14 at 22:21
If Face is a small, simple struct (easy to copy) don't worry about the extra copies. — Neil Kirk, Jun 21 '14 at 22:24
@Scis I assumed since this is tagged C++11 then C++11 semantics apply. — Benjamin Gruenbaum, Jun 21 '14 at 22:29
@BenjaminGruenbaum: I do not understand what you mean by _outside the loop_ and _in the loop_. Regardless, `f` is an lvalue reference, and there the compiler can't use the move constructor for lvalue references -- neither for `push_back` nor for `emplace_back`. The only exception to this rule is the `return` statement. — nosid, Jun 21 '14 at 22:39
@chris Not really. They were always supposed to be contiguous, and when it was discovered that the C++98 standard didn't say so explicitly, they added a paragraph to C++03 to ensure it was so. I don't think there was ever an implementation of std::vector that wasn't contiguous. — Rick Yorgason, Jul 02 '14 at 02:48

101010 · Accepted Answer · 2014-06-21T22:36:08.967

18

According to the standard § 23.3.6.1 Class template vector overview [vector.overview] :

The elements of a vector are stored contiguously, meaning that if v is a vector<T, Allocator> where T is some type other than bool, then it obeys the identity &v[n] == &v[0] + n for all 0 <= n < v.size().

As far as it concerns your second question in prior C++11 compilers push_back would copy the object you push back.

After C++11 it depends because push_back has two overloads, one that takes an lvalue reference and another one that takes an rvalue reference.

In your case It will be copied because you are passing the object as an lvalue. To ensure movement of the object you could use std::move().

faces.push_back(std::move(f));

edited Jun 21 '14 at 22:36

answered Jun 21 '14 at 22:13

101010

41,839
11
94
168

Are you sure that it's _it will be copied_ and not _it might be copied_ here? Is a compiler performing a move in this particular case violating the spec? – Benjamin Gruenbaum Jun 21 '14 at 22:30
1

@BenjaminGruenbaum If you are referring to copy elision, If I remember correctly, this is not one of the cases that could be applied. http://coliru.stacked-crooked.com/a/ca6136f941af40eb – 101010 Jun 21 '14 at 23:09
1

@BenjaminGruenbaum: There can be no move because it is neither cast to an rvalue reference, nor returned as an lvalue nor starts out as an unnamed unbound object. There can be no copy ellision either, 40two is right about that. – Deduplicator Jun 22 '14 at 00:40
Uhm, has the "as if" rule been removed from recent versions of the standard? – Nicola Musatti Jun 30 '14 at 17:23
1

@NicolaMusatti No the "as if" rule still holds (please see § 1.9/5 Program execution [intro.execution]). Overload resolution rules are the ones to blame :). – 101010 Jun 30 '14 at 17:42
@40two So in this case moving instead of copying is a valid optimization, as it can be easily proved that f is not used after the push_back(). There aren't any guarantees that your compiler will do it, though. – Nicola Musatti Jul 04 '14 at 13:43
`There aren't any guarantees that your compiler will do it, though.`: In statement `faces.push_back(std::move(f));` `f` will be effectively moved. `f` after being moved is going to be placed in a valid but unspecified state (please see *17.6.5.15 Moved-from state of library types [lib.types.movedfrom]*). Also please read this answer http://stackoverflow.com/a/12095473/2352671 – 101010 Jul 05 '14 at 02:06

std::vector: contiguous data and copy/move

1 Answers1