Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C++ (http://www.velocityreviews.com/forums/f39-c.html)
-   -   Add two functions into vector class? (http://www.velocityreviews.com/forums/t956142-add-two-functions-into-vector-class.html)

Nephi Immortal 01-05-2013 01:40 AM

Add two functions into vector class?
 
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.

Ian Collins 01-05-2013 02:21 AM

Re: Add two functions into vector class?
 
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

Marc 01-05-2013 12:36 PM

Re: Add two functions into vector class?
 
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.


All times are GMT. The time now is 07:55 PM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.