1

I need to centrally accumulate certain entity creations in my program into a container and I want to use the efficiency of std::move with a move constructor to aggregate all entities created anwhere in the program into one container witout extra copying or instance allocations. Unfortunately using the most popular std::vector container brings with it vector internal management overhead ( or is that compiler implementation dependent??)

For example

class Item {
public :
  static int Count;
  int ID;

  Item() : ID(Count++)
  { cout<<"   Item CREATED - ID:"<<ID<<endl; }

  Item(const Item &itm) : ID(Count++)
  { cout<<"   Item COPY CREATED - (ID:"<<ID<<") <= (ID:"<<itm.ID<<")\n"; }

  Item(const Item &&itm) : ID(Count++)
  { cout<<"   Item MOVE CREATED - (ID:"<<ID<<") <= (ID:"<<itm.ID<<")\n"; }

  ~Item() { cout<<" Item DELETED - (ID:"<<ID<<") \n\n"; }
};

int Item::Count = 0;

void VectorOfItemTest() {
  std::vector<Item> ItemVec;

  for(int idx=0; idx<3; idx++) {
    std::cout<<" { loop "<<idx<<std::endl;
    Item itemInst;
    ItemVec.push_back(std::move(itemInst));
    std::cout<<" } "<<idx<<std::endl;
  }
}

produces output :

-----------------------------
 { loop 0
   Item CREATED - ID:0
   Item MOVE CREATED - (ID:1) <= (ID:0)
 } 0

   Item DELETED - (ID:0)
 { loop 1
   Item CREATED - ID:2
   Item MOVE CREATED - (ID:3) <= (ID:2)
   Item COPY CREATED - (ID:4) <= (ID:1)
   Item DELETED - (ID:1)
 } 1

   Item DELETED - (ID:2)
 { loop 2
   Item CREATED - ID:5
   Item MOVE CREATED - (ID:6) <= (ID:5)
   Item COPY CREATED - (ID:7) <= (ID:4)
   Item COPY CREATED - (ID:8) <= (ID:3)
   Item DELETED - (ID:4)
   Item DELETED - (ID:3)
 } 2

   Item DELETED - (ID:5)
   Item DELETED - (ID:7)
   Item DELETED - (ID:8)
   Item DELETED - (ID:6)

Is it possible to avoid the extra copy-s that causes matching delete-s inside the for loop?

Is there a container (or can we use std::vector in any way) where we get all loop outputs looking as follows ?

 { loop X
   Item CREATED - ID:X
   Item MOVE CREATED - (ID:X+1) <= (ID:X)
 } X
 Item DELETED - (ID:X)

I have looked at Why std::move is required to invoke move assign operator of std::vector Why does std::move copy contents for a rvalue or const lvalue function argument? and a few others here but its still not clear how I can use std::vector (or other containers) efficiently using std::move.

I found a rejected question Hard time understanding object lifetime, copy, move constructor asking close to what I am referring to here I guess.

[UPDATE 1] Using pointers : My existing code uses pointers which avoid extra allocation and copy. I am trying to eliminate pointer usage through out my code moving forward - hence this question. I will revert to pointers if this change doubles the memory allocations and copy-s.

[UPDATE 2] @MooingDuck suggestion of using std::deque solved this issue without the need for reserve() or noexcept move constructor. I was actually in the process of designing an array of std::vector wrapper to avoid std::vector resizing as I also need pointers to the entities remain valid to support legacy code. std::deque seems to do precisely that

"The storage of a deque is automatically expanded and contracted
as needed. Expansion of a deque is cheaper than the expansion of
a std::vector because it does not involve copying of the existing
elements to a new memory location. On the other hand, deques 
typically have large minimal memory cost; a deque holding just one 
element has to allocate its full internal array (e.g. 8 times the 
object size on 64-bit libstdc++; 16 times the object size or 4096 
bytes, whichever is larger, on 64-bit libc++)."

The deque test

void DequeOfItemTest() {
  std::deque<Item> ItemDQ;
  for(int idx=0; idx<3; idx++) {
    std::cout<<" { deque loop "<<idx<<std::endl;
    Item itemInst;
    ItemDQ.push_back(std::move(itemInst));
    Item &refToItem = ItemDQ[ItemDQ.size()-1];
    Item *ptrToItem = &refToItem;
    std::cout<<" } "<<idx<<std::endl;
  }
}

This produces the same output now as I wanted - a single entity allocation on the stack followed by a single move into a container and a single delete of the stack allocation

-----------------------------
 { deque loop 0
   Item CREATED - ID:0
   Item MOVE CREATED - (ID:1) <= (ID:0)
 } 0
   Item DELETED - (ID:0)

 { deque loop 1
   Item CREATED - ID:2
   Item MOVE CREATED - (ID:3) <= (ID:2)
 } 1
   Item DELETED - (ID:2)

 { deque loop 2
   Item CREATED - ID:4
   Item MOVE CREATED - (ID:5) <= (ID:4)
 } 2
   Item DELETED - (ID:4)

   Item DELETED - (ID:5)

   Item DELETED - (ID:3)

   Item DELETED - (ID:1)

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

[Note] as suggested in the comments and answer below (and by VS2022) declaring move constructor and move assignment operators as noexcept is good practice as it lets containers like std::vector use the more efficient move operation instead of a copy operation.

17
  • 1
    std::vector::reserve Commented Dec 27, 2022 at 21:27
  • 1
    After reading your question and comments again, you might be interested in std::deque. It's rarely used, but allows you to add or remove items from both ends of a list without ever doing the copy of all elements. It's very slightly slower than a vector in almost every other case though Commented Dec 28, 2022 at 16:54
  • 1
    Sidenote: You should make your move constructor/assignment noexcept regardless. It makes a lot of things better Commented Dec 28, 2022 at 18:34
  • 1
    Also note: if you can avoid having the local in the first place, and use ItemDQ.emplace_back(...) to construct your class, then you can also eliminate the moves. Commented Dec 28, 2022 at 18:36
  • 1
    Yes, even if you don't use exceptions, marking move constructors and assignment as noexcept will tell other code that the move operators are safe to use. In many cases, std::vector will use move constructors and assignment if they're noexcept, but will use copy constructors and assignment otherwise. Commented Dec 28, 2022 at 18:55

1 Answer 1

3

There are two things required to get your stated ideal:

First, you'll have to mark your move constructor as noexcept. And if it then throws an exception, std::terminate is called, so it really must be designed so that it never throws.

Item(const Item &&itm) noexcept : ID(Count++)
{ cout<<"   Item MOVE CREATED - (ID:"<<ID<<") <= (ID:"<<itm.ID<<")\n"; }

This gets you down to:

{ loop 0
   Item CREATED - ID:0
   Item MOVE CREATED - (ID:1) <= (ID:0)
 } 0

 Item DELETED - (ID:0) 
 { loop 1
   Item CREATED - ID:2
   Item MOVE CREATED - (ID:3) <= (ID:2)
   Item MOVE CREATED - (ID:4) <= (ID:1)
 Item DELETED - (ID:1) 
 } 1

 Item DELETED - (ID:2) 
 { loop 2
   Item CREATED - ID:5
   Item MOVE CREATED - (ID:6) <= (ID:5)
   Item MOVE CREATED - (ID:7) <= (ID:3)
   Item MOVE CREATED - (ID:8) <= (ID:4)
 Item DELETED - (ID:3) 
 Item DELETED - (ID:4) 
 } 2

 Item DELETED - (ID:5) 
 Item DELETED - (ID:6) 
 Item DELETED - (ID:7) 
 Item DELETED - (ID:8) 

The only thing that has changed above is that your copies from before are turned into moves.

The reason this is needed is so that vector::push_back can maintain the strong exception guarantee from C++98/03. This means that if any exception is thrown during the push_back, there are no changes to the value of the vector.

Second, you need to reserve sufficient space in the vector so that push_back never needs to allocate a bigger buffer:

std::vector<Item> ItemVec;
ItemVec.reserve(3);

This gets you down to the ideal:

 { loop 0
   Item CREATED - ID:0
   Item MOVE CREATED - (ID:1) <= (ID:0)
 } 0

 Item DELETED - (ID:0) 
 { loop 1
   Item CREATED - ID:2
   Item MOVE CREATED - (ID:3) <= (ID:2)
 } 1

 Item DELETED - (ID:2) 
 { loop 2
   Item CREATED - ID:4
   Item MOVE CREATED - (ID:5) <= (ID:4)
 } 2

 Item DELETED - (ID:4) 
 Item DELETED - (ID:5) 
 Item DELETED - (ID:3) 
 Item DELETED - (ID:1) 

When push_back is called with ItemVec.size() == ItemVec.capacity(), a new buffer is allocated, and all of the existing elements are moved to the new buffer ... unless your move constructor is not noexcept, in which case all of the existing elements are copied to the new buffer.

Sign up to request clarification or add additional context in comments.

4 Comments

Well, there's also the possibility of emplace_back, which gets rid of 3 destructors and 3 moves, depending on his real code. coliru.stacked-crooked.com/a/98852352c4b35f2b
emplace_back did not change the logging output for me (once the first two steps were done).
Right. I was able to use emplace_back to eliminate the logging by eliminating the local that we move from, which is why I noted "depending on his real code".
thanks @HowardHinnant for your quick responses. the noexcept did make the extra copy-s into extra move-s. When the vector size is in the thousands, I guess each vector resize will lead to thousands of extra move-s overhead due to std::vector design. This does eliminate copy-s though assuming move-s are minimal overhead.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.