Sign in to follow this  

vector fastest access?

This topic is 4729 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

You can look at my code for a vector

I don't know if this is a working version btw =P

#ifndef LOCK_vect_H
#define LOCK_vect_H
#include <cstddef>
#include <memory>
#include <algorithm>
#include <iostream>

namespace bnd
{
template<typename T> class vect
{
public:
typedef T* iterator;
typedef const T* const_iterator;
typedef T& reference;
typedef const T& const_reference;
typedef size_t size_type;
typedef T value_type;
typedef ptrdiff_t difference_type;

vect() { create(); }
explicit vect(size_type n, const T& val = T()) { create(n,val); }
vect(const vect& v) { create(v.begin(), v.end()); }
vect(const T* arr)
{
size_t count = sizeof(arr)/sizeof(*arr);
std::cout << sizeof(arr) << sizeof(*arr) << count;
create(arr, arr + count);
}
vect(const T* b, const T* e) { create(b, e); }
vect& operator=(const vect&);
~vect() { uncreate(); }

void push_back(const T& val);
void pop_back();

iterator erase(iterator);
iterator erase(iterator, iterator);
void clear() { erase(data, limit); }

size_type size() const { return avail - data; }
reference operator[](size_type n) { return data[n]; }
const_reference operator[](size_type n) const { return data[n]; }
iterator begin() { return data; }
const_iterator begin() const { return data; }
iterator end() { return avail; }
const_iterator end() const { return avail; }

T* insert(T*, const T&);

private:
iterator data;
iterator avail;
iterator limit;

std::allocator<T> alloc;
void create();
void create(size_type, const T&);
void create(const_iterator, const_iterator);
void uncreate();

void grow();
void unchecked_append(const T&);
};

template<typename T> vect<T>& vect<T>::operator=(const vect& v)
{
if (this == &v)
return *this;

uncreate();

create(v.begin(), v.end());

return *this;
}

template<typename T> void vect<T>::push_back(const T& val)
{
if (avail == limit)
grow();
unchecked_append(val);
}

template<typename T> void vect<T>::pop_back()
{
if (data == avail)
std::cerr << "Vector is empty\n";
else
alloc.destroy(--avail);
}

template<typename T> void vect<T>::create()
{
data = avail = limit = 0;
}

template<typename T> void vect<T>::create(size_type size, const T& val)
{
data = alloc.allocate(size);
limit = avail = data + size;
std::uninitialized_fill(data, limit, val);
}

template<typename T> void vect<T>::create(const_iterator b, const_iterator e)
{
data = alloc.allocate(e - b);
limit = avail = std::uninitialized_copy(b, e, data);
}

template<typename T> void vect<T>::uncreate()
{
if (data)
{
iterator iter = avail;
while (iter != data)
alloc.destroy(--iter);
alloc.deallocate(data, limit - data);
}

data = avail = limit = 0;
}

template<typename T> void vect<T>::grow()
{
size_type newSize = std::max(2 * (limit - data), difference_type(1));
iterator newData = alloc.allocate(newSize);
iterator newAvail = std::uninitialized_copy(data, avail, newData);

uncreate();

data = newData;
avail = newAvail;
limit = data + newSize;
}

template<typename T> void vect<T>::unchecked_append(const T& val)
{
alloc.construct(avail++, val);
}

template<typename T> T* vect<T>::erase(T* i)
{
alloc.destroy(i);
T* ret = i;

for ( ; i < limit; i++)
*i = *(i + 1);

--avail;
alloc.destroy(--limit);
alloc.deallocate(limit, 1);

return ret;
}

template<typename T> T* vect<T>::erase(T* b, T* e)
{
difference_type diff = e - b;

iterator temp = b;
while (temp++ != e)
alloc.destroy(temp);

temp = b;

for ( ; temp < limit - diff; temp++)
*temp = *(temp + diff);

avail = (avail - diff >= data) ? avail - diff : data;
limit = (limit - diff >= data) ? limit - diff : data;
alloc.destroy(limit);
alloc.deallocate(limit, diff);

return (e - diff);
}

template<typename T> T* vect<T>::insert(T* p, const T& val)
{
if (avail + 1 == limit)
grow();

T* temp = avail++;
*temp = val;

while (temp != p)
swap(*temp, *temp--);

return temp;

}

template<typename T> void swap(T& obj1, T& obj2)
{
T temp = obj1;
obj1 = obj2;
obj2 = temp;
}
}

#endif


You basically alocate sequential memory much like an array, so they are fairly similar, only vector can append objects dynamically.
Also, an Allocator is just an abstraction for anything that allocates memory from the heap (much like an iterator is just an abstraction for anything that has a poiinter like behavior). I could've just asked for memory from the heap the classical way. data = new T[new size].

Notice that because a vecotr behaves like an array you can use a pointer as the iterator, as opposed to making a friend class with overloaded operators (i.e. list).

Share this post


Link to post
Share on other sites
A vector internally stores a buffer in memory, of a size equal to the vector's capacity. The buffer can be indexed as a normal array. However, not all elements in the buffer are necessarily constructed objects. When an element is push_back()'d into a vector, and the size of the vector is less than the capacity, the next element in the vector's buffer is constructed. If the vector's current size is equal to the capacity when an element is push_back()'d then a new buffer is allocated, and the contents of the current buffer are copied into the new buffer. The contents of the old buffer are then discarded (destructors called and the buffer is released). insert() works analagously, though may construct multiple objects at the end of the buffer.

pop_back() works by calling the destructor of the last element in the buffer, erase() by moving the elements up to cover the hole of erased elements, and then the destructors of end elements called.

Share this post


Link to post
Share on other sites
Quote:
they were thinking about add exception handling ot the indexation


The standard is defined such that you can take the address of an item outside the array, so adding exception handling would be... hard.

Specifically, you can get
&v[v.size()]
as the "end of the array" (which isn't *necessary* the same as v.end()).

Share this post


Link to post
Share on other sites
I remember reading somewhere that

T &operator[](size_t)

would have teh same checks as teh .at() version and throw an out_of_range exception.

At least they were considering, which would make it more safe, but I also dislike it.

Share this post


Link to post
Share on other sites

This topic is 4729 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this