vector fastest access?
Author
In a std::vector,
which one is faster for accessing the vector's value:
v[index];
//or
v.at(index);
v[index]; should be faster (in release mode). std::vector::at() does range checking while operator[] does not.
However, the difference is sorta small so they were thinking about add exception handling ot the indexation...
Author
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?
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.
Recall that
v[index] is the same as &v + (sizeof(v) * index) which does not require the range check.
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?
You can look at my code for a vector
I don't know if this is a working version btw =P
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).
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; } } #endifYou 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).
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.
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.
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()]This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement