Thread: Copies made of object during push_back()

  1. #1
    Registered User Sharke's Avatar
    Join Date
    Jun 2008
    Location
    NYC
    Posts
    303

    Copies made of object during push_back()

    I have some code where I'm pushing objects onto a vector using push_back(). The class is counting how many times the object is being copied and I'm displaying the copy total after each push_back(). Not knowing anything about how push_back() is implemented I was just curious as to why the copy totals amass like this: 1, 3, 6, 7, 12, 13, 14, 15, 24, 25? I'm especially curious about the jump from 1 to 3 after the second push_back().

    The code in question is simply:

    Code:
    while (read(in, record))
     {
        students.push_back(record);
        Student_info::show_info(); // prints copy total
        cout << endl;
    }
    The read() function doesn't make any copies.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Sharke
    Not knowing anything about how push_back() is implemented I was just curious as to why the copy totals amass like this: 1, 3, 6, 7, 12, 13, 14, 15, 24, 25? I'm especially curious about the jump from 1 to 3 after the second push_back().
    In order to conform to the requirement that push_back() take amortised constant time, the vector has to increase its capacity by a factor whenever the size is equal to the capacity and a new element is to be pushed back. This may require creating a new dynamic array and copying over the existing elements.
    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

  3. #3
    Registered User Sharke's Avatar
    Join Date
    Jun 2008
    Location
    NYC
    Posts
    303
    Interesting! I would never have guessed there was a timing requirement....

  4. #4
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Quote Originally Posted by Sharke View Post
    Interesting! I would never have guessed there was a timing requirement....
    It's more of an worst-case average timing requirement. There's no guarantee that any particular call of push_back() will occur within a particular time.

    Amortised constant time means there is an asymptotic upper bound for the worst-case average time to perform an operation. It is not guaranteed that one operation will occur within constant time, but it is guaranteed (for large enough n) that the time for n operations will approach time O(n).

    The philosophy is that expensive operations (eg reallocating the storage and copying elements) only execute occasionally and less expensive operations (initialising an unused element of an already-allocated array to a particular value) are executed more often. When averaged across a reasonably large number of operations, this is less expensive, computationally, than requiring every call of push_back() reallocating new memory, copying existing elements to that memory, and releasing the old memory.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Telling a shared_ptr not to delete object?
    By TriKri in forum C++ Programming
    Replies: 5
    Last Post: 08-16-2008, 04:26 AM
  2. Set Classes
    By Nicknameguy in forum C++ Programming
    Replies: 13
    Last Post: 10-31-2002, 02:56 PM
  3. Set Classes
    By Nicknameguy in forum C++ Programming
    Replies: 3
    Last Post: 10-21-2002, 07:40 PM
  4. Object Arrays and Inheritance
    By AceHigh in forum C++ Programming
    Replies: 7
    Last Post: 07-28-2002, 04:08 AM