Add two functions into vector class?

Discussion in 'C++' started by Nephi Immortal, Jan 5, 2013.

  1. I wonder why vector class does not have two functions. Two functions are push_front and pop_front, but list has both of them. I am aware of the right shift issue. I have my thought to figure out another way. I consider toimplement and add push_front and pop_front into vector class. After either push_front or pop_front is invoked, no right shift operation is needed.

    Let’s consider to define one extra data member since vector class alreadyhas three data members.

    type* base_address;
    type* start_address; // new data member
    size_t size;
    size_t capacity;

    When you declare and define vector< char > v, the 16 bytes are allocated into heap and memory address is stored in base_address. Store 16 into capacity. Divide the capacity from 16 into 8, add base_address to 8, and store into start_address.

    start_address = base_address + (capacity / 2);

    You are ready to call push_back function once before the data is stored into element 8 instead of element 0 and size is incrememted to 1. Call push_back functions several times until more data are stored from element 9 through 15 or higher.

    The push_back does only two operations: reads start_address and increments size. The push_front and push_back functions are almost identical performance, but push_front does three operations: decrements start_address by 1, read start_address, and increments size. All the elements are not shifted in the right direction.

    Let’s say for example if you want to call insert function. The data is stored in element 4 through 12. You want to insert data into element 5. The 4 elements are smaller than 8 elements before 4 elements are shifted in the left direction, data is stored in element 5, and then start_address and size are updated.

    In either left or right position in the buffer is full before more memory is allocated to resize the buffer and copy all the elements.

    Add two functiosn and reduce shift operation will do a big improved performance. I prefer vector over list because I want direct memory. Please comment what you think.
    Nephi Immortal, Jan 5, 2013
    #1
    1. Advertising

  2. Nephi Immortal

    Ian Collins Guest

    Nephi Immortal wrote:

    ** Please wrap your lines!

    > I wonder why vector class does not have two functions. Two functions
    > are push_front and pop_front, but list has both of them. I am aware
    > of the right shift issue. I have my thought to figure out another
    > way. I consider to implement and add push_front and pop_front into
    > vector class. After either push_front or pop_front is invoked, no
    > right shift operation is needed.


    std::vector and std::list have a different set of design constraints.
    If you require a container which supports adding and removing elements
    from either end, use std::list. You would have to check the standard to
    ensure your modifications to std::vector do not violate any of the
    container's design constraints.

    --
    Ian Collins
    Ian Collins, Jan 5, 2013
    #2
    1. Advertising

  3. Nephi Immortal

    Marc Guest

    Nephi Immortal wrote:

    > I wonder why vector class does not have two functions. Two functions
    > are push_front and pop_front, but list has both of them. I am aware
    > of the right shift issue. I have my thought to figure out another
    > way. I consider to implement and add push_front and pop_front into
    > vector class. After either push_front or pop_front is invoked, no
    > right shift operation is needed.
    >
    > Let’s consider to define one extra data member since vector class
    > already has three data members.
    >
    > type* base_address;
    > type* start_address; // new data member
    > size_t size;
    > size_t capacity;


    For symmetry, you could have used 4 pointers: alloc_start, data_start,
    data_end, alloc_end.

    This is a design that makes sense, and people use several variants of
    vector for different applications. It just isn't vector. One reason
    people use vector is because of its low overhead. If you start adding
    functionality with a non-zero cost, many users will drop it.

    In the implementation, do make sure that the behavior is sensible when
    you keep pushing on one side and popping from the other. See also
    circular buffers.
    Marc, Jan 5, 2013
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. pmatos
    Replies:
    6
    Views:
    23,723
  2. Replies:
    8
    Views:
    1,889
    Csaba
    Feb 18, 2006
  3. Javier
    Replies:
    2
    Views:
    541
    James Kanze
    Sep 4, 2007
  4. Immortal Nephi
    Replies:
    3
    Views:
    365
    James Kanze
    Sep 15, 2010
  5. Rushikesh Joshi
    Replies:
    0
    Views:
    343
    Rushikesh Joshi
    Jul 10, 2004
Loading...

Share This Page