0

Lets say we have 1 million elements stored in our std::vector<T>, its capacity is full. Now I just want to add 1 element in it. According to concept of vector, now vector's capacity will be doubled in the new memory in heap and all 1 million elements will be copied to new memory location. This seems to be a huge task. Is here there any way that I can avoid this copying and add this new element in the next location only?

Nothing. I cant think of any method to avoid. Most developers suggested me use another container.

Benjamin Buch
  • 4,752
  • 7
  • 28
  • 51
Vvj
  • 19
  • 1
    There are no rules that say that the reallocation have to double. It's up to the individual implementations. – Some programmer dude Mar 28 '23 at 15:37
  • Also, if the elements are movable, that saves the copying. – Some programmer dude Mar 28 '23 at 15:37
  • What requirements do you have of this container? Your requirements should dictate whether "use another container" is correct. If you need elements to be contiguous in memory, `std::vector` is probably correct and `std::vector::reserve()` can avoid the problem you describe. – Drew Dormann Mar 28 '23 at 15:42
  • This is not possible - "add this new element in the next location only" makes absolutely no sense. If this is not okay for you then use a different type of container. – user253751 Mar 28 '23 at 15:43

1 Answers1

5

According to concept of vector, now vector's capacity will be doubled in the new memory in heap and all 1 million elements will be copied to new memory location.

This is not quite correct. Most implementations of std::vector have a growth factor of about 1.5 instead of 2.0. See this question for further information:

What is the ideal growth rate for a dynamically allocated array?

You can control the capacity and its growth using std::vector::reserve. That way, it may be possible for you to prevent the need for the entire content of the container to be copied.

Andreas Wenzel
  • 22,760
  • 4
  • 24
  • 39