order of STL functions

[vsgdp]

Hi,

Is there a place on the web that specifies the guaranteed order of STL
functions? In particular, I want to know if std::vector::resize(x) is
guaranteed to be constant running time. Obviously std::vector::resize(x, y)
is O(n).

 

[AnonMail2005]

In the worst case scenario, resize may have to copy all of the elements
of a vector due to a vector's guarentee that all of it's elements are
contiguous.

I don't see how any such guarentee can be given.

 

[AnonMail2005]

In the worst case scenario, resize may have to copy all of the elements
of a vector due to a vector's guarentee that all of it's elements are
contiguous.

I don't see how any such guarentee can be given.

Any such running time order guarentee that is.

 

[vsgdp]

In the worst case scenario, resize may have to copy all of the elements

of a vector due to a vector's guarentee that all of it's elements are
contiguous.

I don't see how any such guarentee can be given.

Ah I forgot to mention a detail: in the beginning, I resize the vector to
the maximum elements that will ever be allocated. But I may resize down to
a smaller size at a later time, and then back up--but never past the
originally specified max size.

 

[Mike Wahler]

Ah I forgot to mention a detail: in the beginning, I resize the vector to
the maximum elements that will ever be allocated. But I may resize down
to a smaller size at a later time, and then back up--but never past the
originally specified max size.

So you know the largest possible size. If you want
best performance, create the vector with that size
from the start, and leave it that size.

std::vector<int>(max_size);

/* do your stuff */

-Mike

 

[vsgdp]

So you know the largest possible size. If you want
best performance, create the vector with that size
from the start, and leave it that size.

std::vector<int>(max_size);

/* do your stuff */

Yes, but I would like the "size" to change but not the capacity. I still
want to use push_back and pop_back to increment/decrement the size. I just
don't want any memory allocations to occur other than the first one.

Does anyone know if there are rules defined for when the capacity can
change? Obviously it must change if you need _more_ memory, but would
std::vector actally delete an array and allocate a smaller sized array if
the size was small relative to the capacity?

 

[Kai-Uwe Bux]

Yes, but I would like the "size" to change but not the capacity. I still
want to use push_back and pop_back to increment/decrement the size. I
just don't want any memory allocations to occur other than the first one.

Does anyone know if there are rules defined for when the capacity can
change? Obviously it must change if you need _more_ memory, but would
std::vector actally delete an array and allocate a smaller sized array if
the size was small relative to the capacity?

The effect of resize() is defined by the standard to be the same as:

if (sz > size())
insert(end(), sz-size(), c);
else if (sz < size())
erase(begin()+sz, end());
else
;

You are in the case of sz < size(). The complexity of erase is linear in the
length of the range that is erased. The way I understand the standard, the
complexity of resize() is therefore bounded by the amount of elements you
erase. (You cannot do better since you are calling the destructors for
these elements.)

Circumstantial evidence that nothing unexpected will happen is the
following: reallocation should not be triggered by erase() since it is not
allowed to invalidate iterators before the first erased elements.


Best

Kai-Uwe Bux

 

[red floyd]

Yes, but I would like the "size" to change but not the capacity. I still
want to use push_back and pop_back to increment/decrement the size. I just
don't want any memory allocations to occur other than the first one.

Look at std::vector::reserve.

e.g.

// calculate maximum size
std::vector<int>::size_t max_size = calculate_max();
std::vector<int> myvec;
myvec.reserve(max_size);

After this, myvec.size() == 0, but it has capacity of max_size.

 

[Marcus Kwok]

Hi,

Is there a place on the web that specifies the guaranteed order of STL
functions? In particular, I want to know if std::vector::resize(x) is
guaranteed to be constant running time. Obviously std::vector::resize(x, y)
is O(n).

In section 17.1.2 of TC++PL:SE, there is this table (see the book for
explanations:

Standard Container Operations
+----------------+-----------+------------+------------+--------------+-----------+
| | [] | List | Front | Back (Stack) | Iterators |
| | | Operations | Operations | Operations | |
+----------------+-----------+------------+------------+--------------+-----------+
| vector | const | O(n)+ | | const+ | Ran |
| list | | const | const | const | Bi |
| deque | const | O(n) | const | const | Ran |
+----------------+-----------+------------+------------+--------------+-----------+
| stack | | | | const | |
| queue | | | const | const | |
| priority_queue | | | O(log(n)) | O(log(n)) | |
+----------------+-----------+------------+------------+--------------+-----------+
| map | O(log(n)) | O(log(n))+ | | | Bi |
| multipmap | | O(log(n))+ | | | Bi |
| set | | O(log(n))+ | | | Bi |
| multiset | | O(log(n))+ | | | Bi |
+----------------+-----------+------------+------------+--------------+-----------+
| string | const | O(n)+ | O(n)+ | const+ | Ran |
| array | const | | | | Ran |
| valarray | const | | | | Ran |
| bitset | const | | | | |
+----------------+-----------+------------+------------+--------------+-----------+

 

[Marcus Kwok]

Hi,

Is there a place on the web that specifies the guaranteed order of STL
functions? In particular, I want to know if std::vector::resize(x) is
guaranteed to be constant running time. Obviously std::vector::resize(x, y)
is O(n).

In section 17.1.2 of TC++PL:SE, there is this table (see the book for
explanations):

Standard Container Operations
+----------------+-----------+------------+------------+--------------+-----------+
| | [] | List | Front | Back (Stack) | Iterators |
| | | Operations | Operations | Operations | |
+----------------+-----------+------------+------------+--------------+-----------+
| vector | const | O(n)+ | | const+ | Ran |
| list | | const | const | const | Bi |
| deque | const | O(n) | const | const | Ran |
+----------------+-----------+------------+------------+--------------+-----------+
| stack | | | | const | |
| queue | | | const | const | |
| priority_queue | | | O(log(n)) | O(log(n)) | |
+----------------+-----------+------------+------------+--------------+-----------+
| map | O(log(n)) | O(log(n))+ | | | Bi |
| multipmap | | O(log(n))+ | | | Bi |
| set | | O(log(n))+ | | | Bi |
| multiset | | O(log(n))+ | | | Bi |
+----------------+-----------+------------+------------+--------------+-----------+
| string | const | O(n)+ | O(n)+ | const+ | Ran |
| array | const | | | | Ran |
| valarray | const | | | | Ran |
| bitset | const | | | | |
+----------------+-----------+------------+------------+--------------+-----------+