Re: [C++] Vectors & Dynamic allocation

From: Robert W Hand (rwhand_at_NOSPAMoperamail.com)
Date: 04/30/04 

Date: Fri, 30 Apr 2004 05:15:54 -0400

On 29 Apr 2004 16:59:30 -0700, desh_bakth@yahoo.com (Anand Hariharan)
wrote:

>Robert W Hand <rwhand@NOSPAMoperamail.com> wrote in message news:<iovt80phf4fkdq2dtikc0e8e82abju544n@4ax.com>...
>
>> I agree that complexity requirements for
>> std::vector::erase clearly prohibit deallocation of the elements.
>>
>
>Am unsure what the complexity requirements might have to do with the
>deallocation of elements.

In the section of the Standard devoted to std::vector<T>::erase, there
is a paragraph labeled "Complexity". It states that the destructor of
T is called the number of times equal to the number of elements
erased, but the assignment operator for T is called the number of
times equal to the number of elements after the erased elements.
There is no provision for deallocation. Furthermore, since iterators
before the erasure remain valid, an allocation/deallocation step seems
impossible. Deallocation/allocation would invalidate all the
iterators.

>AFAICS, getting vector's erase to check if the elements need
>deallocation etc mimics Garbage collection - a price a developer might
>not be willing to pay. However, even if this were to be included, its
>complexity would still be O(n), isn't it?

The complexity of erase depends upon the type of container. For
vector, it seems to me that we are mixing different lengths of two
different operations. Erasing the last element of a vector should be
different than erasing the first element. In the case of the last
element, only one element is erased and none copied. In the case of
the first element, one element is erased and size()-1 are copied.
Doesn't seem to fit into a neat O(0) complexity. Perhaps someone has
a different idea? 

-- 
Best wishes,
Bob

Relevant Pages

  • Re: [C++] Vectors & Dynamic allocation
    ... >>Am unsure what the complexity requirements might have to do with the ... > There is no provision for deallocation. ... pointed to by the pointers contained in the vector (the example was ...
    (alt.comp.lang.learn.c-cpp)
  • Re: STL - Vector - Normalization ?
    ... >> your single path, you will have to do more on every iteration, which ... After the first element, an element can be either the ... else // This reduces the complexity per element. ... the net saving of the 'else' will be 0 anyway. ...
    (comp.lang.cpp)
  • Re: Linking Password Length to Write-down probability
    ... and mixing caps.other characters ... I continually read papers which advertise increased password lenghts ( ... and outrageous complexity requirements) as The Solution. ... character passwords with moderate complexity requirements are VERY ...
    (Security-Basics)
  • RE: Password complexity - improvement
    ... complexity requirements" or not. ... But the actual "complexity requirement" ... push out your custom passfilt.dll to all controllers, ... The default will enforce 3 of the following 4 properties - Uppercase, ...
    (Focus-Microsoft)
  • Re: Setting password complexity
    ... I wasn't specific enough when I wrote my posting. ... need is a way to alter the complexity requirements that exist in the ... > Associate Expert - WindowsXP Expert Zone ...
    (microsoft.public.windowsxp.basics)