Overview
Examples
Screenshots
Comparisons
Applications
Download
Documentation
Bazaar
Status & Roadmap
FAQ
Authors & License
Forums
Funding Ultimate++
Search on this site













SourceForge.net Logo

InVector

template <class T>

class InVector : public MoveableAndDeepCopyOptionInVector<T> > 

InVector is random access access container (with operator[]) with very fast insertion times for large  numbers of elements. O(n) complexity of insertions is relativaly hard to evaluate, but it should be log(n) for any realistic numbers of elements. Index retrieval complexity is log(n), but thanks to per-thread cache it is fast for simple range scans using increasing/decreasing single index over single container and fast for any iterator based scans.

Generally, any method that changes the number of elements in InVector (plus Shrink method) invalidate any iterators to InVector and references to elements in InVector.

InVector has default pick transfer semantics with optional deep-copy. It is Moveable.

InVector requires elements to be Moveable.

 

Public Method List

 

T& Insert(int i)

Inserts default constructed elementa at i. Invalidates iterators and references to elements.

 


 

T& Insert(int i, const T& x)

Inserts a copy of x at i. Invalidates iterators and references to elements.

 


 

void InsertN(int i, int count)

Inserts count default constructed elements at i. Invalidates iterators and references to elements.

 


 

void Remove(int i, int count = 1)

Removes count elements at i. Invalidates iterators and references. Invalidates iterators and references to elements.

 


 

const T& operator[](int iconst

T& operator[](int i)

Returns a reference to element at i.

 


 

T& Add()

Same as Insert(GetCount()). Invalidates iterators and references to elements.

 


 

T& Add(const T& x)

Same as Insert(GetCount(), x). Invalidates iterators and references to elements.

 


 

void AddN(int n)

Same as InsertN(GetCount(), n). Invalidates iterators and references to elements.

 


 

int GetCount() const

Returns a number of elements in InVector.

 


 

bool IsEmpty() const

Same as GetCount() == 0.

 


 

void Trim(int n)

Same as Remove(n, GetCount() - n). Invalidates iterators and references to elements.

 


 

void SetCount(int n)

Sets the number of elements to be n either removing surplus elements or using AddN to extend the InVector. Invalidates iterators and references to elements.

 


 

void Clear()

Same as Remove(0, GetCount()). Invalidates iterators and references to elements.

 


 

T& At(int i)

If i >= GetCount, performs SetCount(i + 1) to make sure element at i exists. elements. In all cases, returns a reference to element at i. Invalidates iterators and references to elements.

 


 

void Shrink()

Miminizes the heap memory allocated by InVector. Invalidates iterators and references to elements.

 


 

void Set(int i, const T& x, int count)

Sets the value of count elements starting at i to x.

 


 

T& Set(int i, const T& x)

Sets the value of element at i to x.

 


 

void Swap(int i1, int i2)

Swaps elements at position i1 and i2.

 


 

void Drop(int n = 1)

Removes n elements at the end of InVector.

 


 

T& Top()

const T& Top() const

Returns a reference to the last element.

 


 

T Pop()

Returns a copy to the last element and removes it.

 


 

template <class Lint FindUpperBound(const T& val, const L& lessconst

int FindUpperBound(const T& valconst

Finds the upper bound for val using less / StdLess<T> as comparison predicate. InVector should be sorted using the same predicate.

 


 

template <class Lint FindLowerBound(const T& val, const L& lessconst

int FindLowerBound(const T& valconst

Finds the lower bound for val using less / StdLess<T> as comparison predicate. InVector must be sorted using the same predicate.

 


 

template <class Lint InsertUpperBound(const T& val, const L& less)

int InsertUpperBound(const T& val)

Inserts the element at posiotion found using FindUpperBound (but the whole operation is optimized relative to FindUpperBound/Insert pair). InVector must be sorted using the same predicate.

 


 

template <class Lint Find(const T& val, const L& lessconst

int Find(const T& valconst

Finds the position of val in InVector sorted using less / StdLess<T>. If not found, returns negative value.

 


 

ConstIterator Begin() const

ConstIterator End() const

ConstIterator GetIter(int posconst

Iterator Begin()

Iterator End()

Iterator GetIter(int pos)

Returns constant/nonconstant iterator to the begin/end/pos.

 


 

InVector()

Constructs empty InVector.

 


 

InVector(const InVector& v, int)

Optional deep copy constructor.

 


 

InVector(std::initializer_list<Tinit)

C++ 11 initialization.

 


 

void Swap(InVector& b)

Swap with another InVector.

 

 

Examples on InVector caching

 

Following examples demonstrate what is meant by "simple scan" which are using cache to accelerate index retrieval vs more complex non-cached scans:

 

Cached cases

 

int m = 0;

for(int i = 0; i < x.GetCount(); i++)

    m += x[i];

for(int i = x.GetCount(); --i >= 0;)

    m += x[i];

 

 

InVector<int> y;

y <<= x;

int m = 0;

for(int i = 0; i < x.GetCount(); i++)

    m += x[i];

for(int i = y.GetCount(); --i >= 0;)

    m += y[i];

 

 

 

Non-Cached cases (about 8x times slower in this case)

 

int m = 0;

for(int i = 0; i < x.GetCount(); i++)

    m += x[i] + x[x.GetCount() - i - 1];

 

InVector<int> y;

y <<= x;

int m = 0;

for(int i = 0; i < x.GetCount(); i++)

    m += x[i] + y[i];

 

Last edit by klugier on 06/12/2016. Do you want to contribute?. T++