Jump to content
  • Advertisement
Sign in to follow this  
kubicon

vector fastest access?

This topic is 5097 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

Advertisement
v[index]; should be faster (in release mode). std::vector::at() does range checking while operator[] does not.

Share this post


Link to post
Share on other sites
However, the difference is sorta small so they were thinking about add exception handling ot the indexation...

Share this post


Link to post
Share on other sites
How small is the difference. To me any difference is a difference, so I'll choose indexation. How slower do you think is the exeptions gonna make the indexation?

Share this post


Link to post
Share on other sites
I'm with SiCrane on this. The STL will have more overhead for such a simplistic operation.

Recall that

v[index] is the same as &v + (sizeof(v) * index) which does not require the range check.

Share this post


Link to post
Share on other sites
Is that true for a vector? I thought the way they were allocated was different than arrays, since you can add and subtract items at will. Does someone here want to point me to something explaining exactly how a vector works?

Share this post


Link to post
Share on other sites
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!