vsgdp <sp**@void.com> wrote:
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