Thread: renew

  1. #16
    Kiss the monkey. CodeMonkey's Avatar
    Join Date
    Sep 2001
    Posts
    937
    Isn't std::vector usually implemented to avoid copying whenever possible? Judging by what I am reading -- no. Yet the overhead involved in the checks necessary seems like it would be trivial.
    "If you tell the truth, you don't have to remember anything"
    -Mark Twain

  2. #17
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    Yes and no. I doubt it is so low level that it is able to do the equivalent of a realloc when it needs more space. However, it attempts to minimize reallocations and is generally pretty efficient at it.

    In addition, the new standard will allow move semantics which would have the potential to make reallocations even less expensive.

  3. #18
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Quote Originally Posted by iMalc View Post
    I assume you mean that multiplying the size by some constant > 1, as resizing to 1.5x the size is also acceptable afaik.
    Peculiarly enough, I've just scoured both the C++98 and the C++09 drafts and cannot find any mention of the allocation complexity of repeated inserts or push_backs for vectors. In other words, as far as I can see it's legal for a vector to just reallocate for a single additional element every time push_back is called. The only place where a reallocation complexity is specified is for the range constructor (two iterators), which says that, if the iterators are input iterators, the operation will take at most order of log(N) reallocations, where N is distance(first, last). In other words, this constructor requires increments of a constant factor > 1.

    I must be wrong about this. I'm absolutely sure this is required for other operations, too, but I just can't find the place.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  4. #19
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    >> I'm absolutely sure this is required for other operations, too
    I've never heard that. I've always been under the impression that a naive "always increase capacity by one" implementation was perfectly standard.

  5. #20
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Quote Originally Posted by Daved View Post
    >> I'm absolutely sure this is required for other operations, too
    I've never heard that. I've always been under the impression that a naive "always increase capacity by one" implementation was perfectly standard.
    The standard says that push_back would be an equivalent of insert(end(), x). It also says:
    In addition, it supports (amortized) constant time insert and erase operations at the end; insert and erase in the middle take linear time.
    Now, if you were to copy things around for each push_back, that wouldn't be constant time insert at the end. It would be linear time.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  6. #21
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by anon View Post
    The standard says that push_back would be an equivalent of insert(end(), x). It also says:

    Now, if you were to copy things around for each push_back, that wouldn't be constant time insert at the end. It would be linear time.
    That's it exactly. It wouldn't state the method used to achieve amortised constant time push_back, as they tend to like to leave that to the implementation details. But then there's probably only one way to achieve it anyway. So I guess growing by size multiplication instead of addition is implied.

    Well, back to the original topic, one can easily write their own container that uses VirtualAlloc and Placement new etc, but why bother! Profile first!
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed