1

Running the following test code

int destroyed[3] = { 0, 0, 0 };

struct Test {
    int a;
    Test() {}
    ~Test() {
        destroyed[a]++;
    }
};

template<class T>
void remove(std::vector<T>& v, size_t i) {
    std::swap(v[i], v.back());
    v.pop_back();
}

main() {
    std::vector<Test> vt(3);
    vt[0].a = 0;
    vt[1].a = 1;
    vt[2].a = 2;
    remove(vt, 0);
}

destroyed counts the number of times an element has been destroyed.

I can see that destroyed = { 2, 0, 0 }.

I want to remove element 0, so I should destroy it. However I don't need to call its destructor twice; so, how can I write the remove function so that I end up with destroyed = { 1, 0, 0 } (destroying it only once)?

Inuart
  • 1,432
  • 3
  • 17
  • 28
  • 3
    Write a move constructor for Test. – Ben Apr 14 '14 at 03:46
  • The Test class is only for testing the `remove` function. `remove` should behave correctly for every class. – Inuart Apr 14 '14 at 03:51
  • 4
    Because `std::swap(v[i], v.back());` doesn't find a move constructor or `swap` specialisation, it falls back on copying `v[i=0]` to a temporary so it can overwrite it with `v.back()` then assign `v.back()` from the temporary. The temporary will have `a == 0` due to the default copy-constructor, so when its destructor runs it increments `destroyed[0]`. Later, `v.back()`'s destructor increments it again. Tell the compiler how to swap `Test` objects without a temporary, or add `move` for `Test` that puts the moved object into special state (e.g. `a = -1`) then `if (a != -1) ++destroyed[a]`. – Tony Delroy Apr 14 '14 at 03:54
  • 3
    Yeah, it is behaving correctly. When you call std::swap on two elements, there's copying going on. When c++ copies an object, it doesn't move it from one place to another, it destroys it in one place and recreates it at another. Now, if your class T had a move constructor, the std::vector could use that to MOVE the object around, rather than copy it. – Ben Apr 14 '14 at 03:55
  • See [here](http://stackoverflow.com/questions/11562/how-to-overload-stdswap) for tips on implementing `Test::swap` (probably simpler than supporting `move`). – Tony Delroy Apr 14 '14 at 04:02
  • 1
    I suggest you count constructors as well as destructors, and don't forget copy construction. You will find that the books do balance. – user207421 Apr 14 '14 at 04:22
  • I think this has undefined behaviour because the `std::vector vt(3);` is allowed to create a temporary and then copy-construct the 3 vector members from it. (well - my test program did that). Suggest changing the constructor to initialize `a`, and you can re-zero the `destroyed` array after the vector has been created and before you `remove`. – M.M Apr 14 '14 at 04:24
  • Ideally I would call `i`s element destructor, copy the last element to `i`s position and decrease the size of the vector, but `pop_back` calls the destructor – Inuart Apr 14 '14 at 14:20

1 Answers1

0

This implementation of remove seems to work

template<class T>
void remove(std::vector<T>& v, size_t i) {
    uint8_t d[sizeof T];
    memcpy(d, &v[i], sizeof T);
    v[i] = v.back();
    memcpy(&v.back(), d, sizeof T);
    v.pop_back();
}

Comments on this code will be very appreciated.

Inuart
  • 1,432
  • 3
  • 17
  • 28