Add two functions into vector class?

N

Nephi Immortal

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.
 
I

Ian Collins

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.
 
M

Marc

Nephi said:
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.
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,902
Latest member
Elena68X5

Latest Threads

Top