Home > Back-end >  Can you truncate std::vector<int> in constant time?
Can you truncate std::vector<int> in constant time?

Time:02-19

There are several ways to make a vector empty, including

std::vector<int> example = makeMyReallyBigVector();
example.clear();
example.resize(0);
example.erase(example::being(), example::end());
// any other method which would be relevant

Are there any guarantees in the C standard about which is most efficient, time-wise? The contents are a primitive data type without destructor. What I am especially concerned about is, I don't want the vector capacity to change, I just want it's internal "used size" set to 0 without touching the now-erased contents.

What I want is to set the int vector size to 0 in constant time, without freeing any memory. Is this possible with C standard?

If the C standard gives no guarantees, I'm using GNU C standard library, so if standard doesn't, does that give any guarantees? For sake of portability, in this case also information about the Clang and Microsoft standard libraries would of interest, of course.

CodePudding user response:

example.clear();

clear is :

Linear in the size of the container, i.e., the number of elements.

example.resize(0);

resize is

Linear in the difference between the current size and count. Additional complexity possible due to reallocation if capacity is less than count

example.erase(example::being(), example::end());

erase is

Linear: the number of calls to the destructor of T is the same as the number of elements erased, the assignment operator of T is called the number of times equal to the number of elements in the vector after the erased elements

I am not sure why neither clear nor resize mention the dependence on the destructor. int has only a pseudo-destructor (something that makes calling the destructor on an int valid, but it doesn't do anything).

If the elements do have a destructor the complexitiy is linear. For int the compiler may be clever enough to do it in constant time. When you are not sure about runtime the only way to be sure is to measure.

CodePudding user response:

example.clear(); may be faster. All of the above examples take arguments, which means that additional code will be generated to pass them to the function, which will need to be executed.

However, it's important to remember that the C compiler is pretty smart and might be able to turn example.resize(0); into example.clear();. But it is not exactly. So it's better to help the compiler, if not difficult.

  • Related