How to efficiently insert multiple copy-constructible but not copy-assignable elements in a vector?

user_1453047 0
Viewed 72

I have a type X, which is copy-constructible but not copy assignable

struct X {
    X();
    X(const X&);
    X& operator=(const X&) = delete; // !!
    X(X&&) noexcept;
    X& operator=(X&&) noexcept;
    int data = 54;
};

I have two vectors of 'X': a and b and I want to insert all the contents of b at the front of a:

void add_to_front(std::vector<X>& a, const std::vector<X>& b) {
    a.insert(a.begin(), b.begin(), b.end());
}

This compiles and works as expected on msvc but fails to compile on clang and gcc. I'm guessing due to poor implementations of libc++ and libstdc++ which need something to compile even though it will never get called (or, worse yet, it will get called!?).

I could write a manual loop to emplace elements of b into a which will produce a correct result, but the complexity of this is a*b instead of a+b, as each call to emplace will shift all elements of a over and over again.

So is there an efficient way to do it?

Live demo can be found here

stdvector c++
1 Answers

I must admit that I'm not quite sure whether the poor implementations of libc++ and libstdc++ are the issue. Though, I found a quite simple way to circumvent OPs issue:

#include <vector>

struct X {
    X() = default;
    X(const X&) = default;
    X& operator=(const X&) = delete; // !!
    X(X&&) noexcept = default;
    X& operator=(X&&) noexcept = default;
    int data = 54;
};

void add_to_front(std::vector<X>& a, const std::vector<X>& b) {
    std::vector<X> b_(b);
    a.insert(a.begin(), std::make_move_iterator(b_.begin()), std::make_move_iterator(b_.end()));
}

int main()
{
  std::vector<X> a, b;
  add_to_front(a, b);
}

This is accepted by

  • clang 11.0.0 -std=c++11 -O2
  • gcc 9.2 -std=c++11 -O2
  • msvc 19.28 /std:c++14 /O2

Live Demo on Compiler Explorer

@Evg had a look into the
Type requirements for std::vector::insert()

In OPs case it's this overload:

template< class InputIt >
iterator insert( const_iterator pos, InputIt first, InputIt last );

with

  • T must meet the requirements of EmplaceConstructible in order to use overload (4,5).
  • T must meet the requirements of MoveAssignable and MoveInsertable in order to use overload (4). required only if InputIt satisfies LegacyInputIterator but not LegacyForwardIterator.

This should be granted by OPs struct X.

So, to me, it looks like OP is right with the complaints.

user_74785970
Related