Why is it impossible to assign to a vector of objects that themselves lack copy operator?

Question

I have a vector of structures that are copy-constructible, but non-assignable:

struct Struct
{
    inline Struct(const std::string& text, int n) : _text(text), _n(n) {}
    inline Struct(const Struct& other) : _text(other._text), _n(other._n) {}

    const std::string _text;
    const int _n;

    Struct& operator=(const Struct&) = delete;
};

It all worked fine. In fact, I could even pass the std::vector<Struct> around by value as a return value of a function. And yet, this fails:

std::vector<TextFragment> v1, v2;
v2 = v1;

The error, of course, is:

error: C2280: 'Struct &Struct ::operator =(const Struct &)' : attempting to reference a deleted function

I don't understand why it tries to invoke that. Is that some kind of an optimization to avoid re-allocating the vector's memory block?..

I don't see your copy constructor. It should be `Struct(const Struct &other)`. — Fozi, May 18 '16 at 20:11
@Fozi: Good point. I assume I'd get the default one, but it was before I added my 2 arguments constructor. Let me check. — Violet Giraffe, May 18 '16 at 20:12
Deleting a function doesn't remove it from overload resolution. So naturally calling a deleted function results in an error. Or is your question why you can't copy something that isn't copyable? — uh oh somebody needs a pupper, May 18 '16 at 20:51
@sleeptightpupper: the question must be clear enough since the others get it. — Violet Giraffe, May 18 '16 at 20:54
It doesn't make a whole lot of sense to have a class that is copy-constructable but not copy-assignable (is it copyable or not?)... — Chris Dodd, May 18 '16 at 22:12
@ChrisDodd: Seems perfectly reasonable to me. Copy-construction just means "I will copy the other thing and then exist", copy-assignment is "I will become the other thing". Consider an immutable property-bag class. — GManNickG, May 18 '16 at 22:15
@GManNickG: No, copy-assignment is "I will copy this other thing, replacing my previous state". An immutable object is just `const` -- independent of any constructors or assignment operators. Of course, C++ has no good way of expressing "all instances of this class should be const", but it's not that clear to me that makes a lot of sense either. "I will become this other thing" is move construction/assignment, — Chris Dodd, May 18 '16 at 22:39
@ChrisDodd You just classified all lambdas as making no sense :) — T.C., May 18 '16 at 22:48
@M.M Assuming that you mean destroy + recreate in place, that doesn't work with `const`-qualified things (see [basic.life]/8). — T.C., May 18 '16 at 22:50
@T.C.: well yes, the way lambdas are defined in the C++ standard is fairly non-sensical, and the deleted copy assignment operator is just one part of that. — Chris Dodd, May 18 '16 at 22:58
@T.C. OK. So the workaround has to be not using `const` members in the first place then. — M.M, May 19 '16 at 02:06

Howard Hinnant · Accepted Answer · 2016-05-19T14:18:54.463

5

Is that some kind of an optimization to avoid re-allocating the vector's memory block?..

Almost. It is an optimization to avoid re-allocating whatever memory blocks might be present in vector's value_type. That is, it is a global assumption that assignment can be more efficient than destruction followed by copy construction.

For example consider vector<string> assignment, for two equal sized vectors, and a bunch of equal sized strings in each spot in the vector:

v2 = v1;

All this operation has to do is memcpy each string. No allocations at all. Reducing allocations/deallocations is one of the most important optimizations that exist today.

However, all is not lost for your Struct. What you want to do is instruct the vector that you do not wish to assign your Structs, but instead destruct them, and then copy construct them from v1. The syntax for doing this is:

v2.clear();
for (const auto& x : v1)
    v2.push_back(x);

As noted in the comments below, you can also copy construct v1, and then swap with the copy. You either need to create a temporary local copy of v1, or you need to use v1 on the "lhs" of member swap:

std::vector<Struct>(v1).swap(v2);

I personally find this hard to read. In C++11/14 I prefer this alternative which involves move assignment:

v2 = std::vector<Struct>(v1);

These alternatives are easier on the eyes. But the first alternative, using clear() and push_back is going to be the most efficient on average. This is because the first alternative is the only one that has a chance of reusing capacity() in v2. The other two always recreate new capacity() in the copy of v1 and throw away v2's existing capacity().

edited May 19 '16 at 14:18

answered May 19 '16 at 02:29

Howard Hinnant

206,506
52
449
577

The first answer that actually answers my question, and makes sense. Thank you! "Reducing allocations/deallocations is one of the most important optimizations that exist today." - I shall remember that. – Violet Giraffe May 19 '16 at 05:21
Somehow I did not think of copying it the way you suggested. But I did think about this, though, and it works: `v2.swap(std::vector(v1));` – Violet Giraffe May 19 '16 at 05:23
why not `v2.clear(); v2.insert(v2.begin(), v1.begin(), v1.end());` to safe on the conditional logic inside `push_back()`? – TemplateRex May 19 '16 at 15:21
2

@TemplateRex: `vector::insert` requires `T` to be MoveAssignable (and in this particular example, CopyAssignable as well), which `Struct` is not. – Howard Hinnant May 19 '16 at 15:53
Hm, that seems like a gap in the vector interface. I find it surprising that there is no ranged in-place construct member (apart from the constructor). Do you know of any proposals on this? – TemplateRex May 19 '16 at 16:51
@TemplateRex: I am not aware of any proposals in this area at the moment. I question that such a proposal would be successful. In the no-reallocation case, `vector::insert` must "make a hole" to put the new element in. This "hole" is a constructed but moved from `value_type`. In the process of making this hole, `value_type` will be move assigned (say from the "hole" to v[hole+1]). This is true before we even start to talk about how to fill in the hole with the newly inserted element(s). – Howard Hinnant May 19 '16 at 17:32
I was thinking of bypasing `insert` altogether with a member `construct(first, last)`, similar to the ranged `assign` member. It would simply call the allocator::construct in a loop, with a single capacity check upfront. – TemplateRex May 19 '16 at 17:46
@TemplateRex: This would also be easy to write yourself as a namespace scope function (using `clear`, `distance`, `reserve`, and `push_back`). – Howard Hinnant May 19 '16 at 19:44
Sure, but `push_back` will still have per-element conditional logic to check for within-capacity (branch prediction has its limits). A class-member could bypass that and do `clear`, `distance` and then a loop doing in-place construction (through the allocator's `construct`). I think it would be nice if every `vector` member that works on single elements (such as `push_back`) had a ranged-counterpart with the same type requirements that could amortize all the allocation overhead and eliminate duplicated conditional logic. AFAICS, there is no such member for `push_back`. – TemplateRex May 19 '16 at 20:18
A paper with timing comparisons would be interesting to read. – Howard Hinnant May 19 '16 at 20:37

NathanOliver · Answer 2 · 2016-05-18T20:53:52.557

3

A std::vector is a allocator-aware container. If we look at the spec for that(table 99) we have a = t where a is a non-const lvalue and t is a lvalue or const rvalue and it requires

T is CopyInsertable into X and CopyAssignable. post: a == t

^{Emphasis mine}

Where T is the value_type of X(the container). It also states that the operation is linear. Since T needs to be CopyAssignable and Struct is not CopyAssignable it is not required to work.

This implies that the assignment operation would look something like:

std::vector<T>& operator=(const std::vector<T>& rhs)
{
    // allocate enough room for data if needed
    for (std::size_t i = 0; i < rhs.size(); ++i)
        data[i] = rhs.data[i];
    return *this;
}

edited May 18 '16 at 20:53

answered May 18 '16 at 20:21

NathanOliver

171,901
28
288
402

more likely to take `rhs` by const reference (and have separate move-assignment operator) – M.M May 18 '16 at 20:31
I don't think "allocate" and "room" are the correct words here. It's more like "construct enough targets". – user3528438 May 18 '16 at 20:34
This example is overly simplified and doesn't even use the allocator, making it a non-sequitor. – uh oh somebody needs a pupper May 18 '16 at 20:43
1

Moot point. Re-allocating the memory and using placement new for items would also be linear complexity, and would not rely on assignment. In fact, I'm not even sure re-allocation would be strictly necessary. – Violet Giraffe May 18 '16 at 20:53
@VioletGiraffe I updated the answer a little. The point is the standard mandates that `T` must be copyAssignable. – NathanOliver May 18 '16 at 20:58
So does it specifically say that `T` must only be CopyAssignable for vector assignment to work, but not in order to construct the vector and insert elements? – Violet Giraffe May 18 '16 at 21:37
@VioletGiraffe It says it has to be CopyInsertable and CopyAssignable. – NathanOliver May 18 '16 at 21:52

score 0 · Answer 3 · answered May 18 '16 at 22:22

You may find this function informative, from libc++. In particular, note the call to std::copy.

template <class _Tp, class _Allocator>
template <class _ForwardIterator>
typename enable_if
<
    __is_forward_iterator<_ForwardIterator>::value &&
    is_constructible<
       _Tp,
       typename iterator_traits<_ForwardIterator>::reference>::value,
    void
>::type
vector<_Tp, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last)
{
    size_type __new_size = static_cast<size_type>(_VSTD::distance(__first, __last));
    if (__new_size <= capacity())
    {
        _ForwardIterator __mid = __last;
        bool __growing = false;
        if (__new_size > size())
        {
            __growing = true;
            __mid =  __first;
            _VSTD::advance(__mid, size());
        }
        pointer __m = _VSTD::copy(__first, __mid, this->__begin_);
        if (__growing)
            __construct_at_end(__mid, __last, __new_size - size());
        else
            this->__destruct_at_end(__m);
    }
    else
    {
        deallocate();
        allocate(__recommend(__new_size));
        __construct_at_end(__first, __last, __new_size);
    }
}

operator = just calls assign(r.begin(), r.end()) after fixing up the allocator if they differ.

Why is it impossible to assign to a vector of objects that themselves lack copy operator?

3 Answers3