Re: [C++] Vectors & Dynamic allocation

From: Anand Hariharan (desh_bakth_at_yahoo.com)
Date: 05/01/04 

Date: 30 Apr 2004 16:52:51 -0700

Robert W Hand <rwhand@NOSPAMoperamail.com> wrote in message news:<bm44909io91ceu7kt4kjhforg3nmvjp8m8@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.
>

Bob - It was only from the above para, it became clear to me that you
are talking about allocation/deallocation of vector (i.e.,
reallocation/resizing).

>From the context of your statement in your earlier post (at the top of
this post), I thought we were talking about deallocation of the memory
pointed to by the pointers contained in the vector (the example was
talking about vector<int *>). That was what I meant when I said ...

> >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?
>

>From my above para, I wonder if it is clear that I was talking about
the memory held by the pointers to int (the elements of the vector)
rather than the vector itself.

> 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?

(Very) loosely put, Complexity refers to the number of operations
required to perform an operation, expressed as a function of the input
size. Specifics / border-line/base cases are not separately accounted
for. E.g., "Complexity of sorting is O(n lg n)" does not account for
the characteristics of a specific instance of input. Of course, if
the input set is already sorted, a sorting algorithm could "sort" its
input in linear time.

wondering if this thread could sustain much longer,
- Anand

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. ... the first element, one element is erased and size-1 are copied. ...
    (alt.comp.lang.learn.c-cpp)
  • Re: Not a very good Idea!
    ... IMO Pascal's with statement is one of the truely nasty parts of that ... pointers to structures or unions. ... Making modules too small is ... it creates complexity in the interfaces and call tree. ...
    (comp.lang.c)
  • Re: [C++] Vectors & Dynamic allocation
    ... >pointed to by the pointers contained in the vector (the example was ... erasing an element off the front of the vector. ... complexity of vector::eraseis, well, complex. ... Anand, after making such a basic error in communication, there is ...
    (alt.comp.lang.learn.c-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)