Thread: Operator new[] vs. Array

  1. #16
    The larch
    Join Date
    May 2006
    I don't think the standard specifies the factor. I think VC++ implementation uses a smaller factor than GCC, which might actually be 1.5.
    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).

  2. #17
    Registered User
    Join Date
    Apr 2007
    Quote Originally Posted by laserlight View Post
    std::vector's push_back does something like that, though with a factor of 2 instead of 1.5. std::vector's reserve() can be used to expand by a factor of 1.5.
    Factor of 2 expansion is how you see it presented in most algo. textbooks. I like a factor of 1.5 since it requires a little less memory at the expense of a little more resizing. Both algorithms are of course linear complexity. That is the complexity of appending n items is proportional to n , O(n).

    Also a factor of 1.5 is easy to generate via a shift and an add once you take care of end cases.

  3. #18
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Quote Originally Posted by anon
    I don't think the standard specifies the factor.
    I double checked, and I think that you are right, the standard only seems to specify amortised constant time for std::vector's push_back().
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 16
    Last Post: 05-29-2009, 07:25 PM
  2. Replies: 6
    Last Post: 11-09-2006, 03:28 AM
  3. [question]Analyzing data in a two-dimensional array
    By burbose in forum C Programming
    Replies: 2
    Last Post: 06-13-2005, 07:31 AM
  4. Unknown Memory Leak in Init() Function
    By CodeHacker in forum Windows Programming
    Replies: 3
    Last Post: 07-09-2004, 09:54 AM
  5. Quick question about SIGSEGV
    By Cikotic in forum C Programming
    Replies: 30
    Last Post: 07-01-2004, 07:48 PM