std::vector like container optimized for pushing elements to the back. More...

#include <src/growvector.h>

Inheritance diagram for GrowVector< T >:

Classes
struct	Chunk

class	Iterator
	bidirectional iterator More...

Public Types
using	iterator = Iterator<GrowVector,T>

using	const_iterator = Iterator<const GrowVector,const T>

Public Member Functions
iterator	begin ()
	returns an iterator to the beginning

const_iterator	begin () const
	returns an iterator to the beginning

iterator	end ()
	returns an iterator to the end

const_iterator	end () const
	returns an iterator to the end

size_t	size () const
	returns the number of elements

void	push_back (T &&t)
	adds an element to the end

template<class... Args>
void	emplace_back (Args &&...args)
	constructs an element in-place at the end

void	pop_back ()
	removes the last element

T &	at (size_t i)
	access specified element

const T &	at (size_t i) const
	access specified element

T &	front ()
	access the first element

const T &	front () const
	access the first element

T &	back ()
	access the last element

const T &	back () const
	access the last element

bool	empty () const
	checks whether the container is empty

void	clear ()
	clears the contents

Private Types
using	ChunkPtr = std::unique_ptr<Chunk>

Private Member Functions
void	make_room ()

Private Attributes
std::vector< ChunkPtr >	m_chunks

Static Private Attributes
static const size_t	chunkBits = 4

static const size_t	chunkSize = 1 << chunkBits

static const size_t	chunkMask = chunkSize-1

Detailed Description

template<class T>
class GrowVector< T >

std::vector like container optimized for pushing elements to the back.

It differs from std::vector in that it can grow without invalidating pointers to its members just like std::deque and std::list.

It differs from std::deque in that the value can be incomplete just like std::vector.

It differs from std::list in that it does not need to allocate each node separately and provides random access to its members.

It is implemented as a vector of chunks where each chunk is a fixed capacity vector of T.

Definition at line 39 of file growvector.h.

Member Typedef Documentation

◆ ChunkPtr

template<class T>

using GrowVector< T >::ChunkPtr = std::unique_ptr<Chunk>

private

Definition at line 50 of file growvector.h.

◆ const_iterator

template<class T>

using GrowVector< T >::const_iterator = Iterator<const GrowVector,const T>

Definition at line 80 of file growvector.h.

◆ iterator

template<class T>

using GrowVector< T >::iterator = Iterator<GrowVector,T>

Definition at line 79 of file growvector.h.

Member Function Documentation

◆ at() [1/2]

template<class T>

T & GrowVector< T >::at ( size_t i )

inline

access specified element

Definition at line 125 of file growvector.h.

125{ return m_chunks.at(i>>chunkBits)->data.at(i&chunkMask); }

GrowVector

std::vector like container optimized for pushing elements to the back.

Definition growvector.h:40

GrowVector::m_chunks

std::vector< ChunkPtr > m_chunks

Definition growvector.h:154

GrowVector::chunkBits

static const size_t chunkBits

Definition growvector.h:42

GrowVector::chunkMask

static const size_t chunkMask

Definition growvector.h:44

References chunkBits, chunkMask, and m_chunks.

◆ at() [2/2]

template<class T>

const T & GrowVector< T >::at ( size_t i ) const

inline

access specified element

Definition at line 127 of file growvector.h.

127{ return m_chunks.at(i>>chunkBits)->data.at(i&chunkMask); }

References chunkBits, chunkMask, and m_chunks.

◆ back() [1/2]

template<class T>

T & GrowVector< T >::back ( )

inline

access the last element

Definition at line 135 of file growvector.h.

135{ return m_chunks.back()->data.back(); }

References m_chunks.

Referenced by DocPara::handleHtmlStartTag(), DocParser::handleStyleEnter(), and DocParser::internalValidatingParseDoc().

◆ back() [2/2]

template<class T>

const T & GrowVector< T >::back ( ) const

inline

access the last element

Definition at line 137 of file growvector.h.

137{ return m_chunks.back()->data.back(); }

References m_chunks.

◆ begin() [1/2]

template<class T>

iterator GrowVector< T >::begin ( )

inline

returns an iterator to the beginning

Definition at line 83 of file growvector.h.

83{ return iterator(*this,0); }

GrowVector::iterator

Iterator< GrowVector, T > iterator

Definition growvector.h:79

◆ begin() [2/2]

template<class T>

const_iterator GrowVector< T >::begin ( ) const

inline

returns an iterator to the beginning

Definition at line 85 of file growvector.h.

85{ return const_iterator(*this,0); }

GrowVector::const_iterator

Iterator< const GrowVector, const T > const_iterator

Definition growvector.h:80

◆ clear()

template<class T>

void GrowVector< T >::clear ( )

inline

clears the contents

Definition at line 143 of file growvector.h.

143{ m_chunks.clear(); }

References m_chunks.

Referenced by flattenParagraphs(), and DocNodeList::move_append().

◆ emplace_back()

template<class T>

template<class... Args>

void GrowVector< T >::emplace_back ( Args &&... args )

inline

constructs an element in-place at the end

Definition at line 108 of file growvector.h.

    {
      make_room();
      m_chunks.back()->data.emplace_back(std::forward<Args>(args)...);
    }

References m_chunks, and make_room().

◆ empty()

template<class T>

bool GrowVector< T >::empty ( ) const

inline

checks whether the container is empty

Definition at line 140 of file growvector.h.

140{ return m_chunks.empty(); }

References m_chunks.

Referenced by DocParser::defaultHandleToken(), DocDiagramFileBase::hasCaption(), DocImage::hasCaption(), DocVhdlFlow::hasCaption(), DocRef::hasLinkText(), DocTitle::hasTitle(), DocParser::internalValidatingParseDoc(), DocPara::isEmpty(), DocRoot::isEmpty(), DocText::isEmpty(), DocHtmlRow::isHeading(), DocbookDocVisitor::operator()(), DocbookDocVisitor::operator()(), HtmlDocVisitor::operator()(), PrintDocVisitor::operator()(), XmlDocVisitor::operator()(), DocParamSect::parse(), DocSimpleSect::parse(), and DocSimpleSect::parseXml().

◆ end() [1/2]

template<class T>

iterator GrowVector< T >::end ( )

inline

returns an iterator to the end

Definition at line 88 of file growvector.h.

88{ return iterator(*this,size()); }

GrowVector::size

size_t size() const

returns the number of elements

Definition growvector.h:93

References size().

Referenced by DocPara::handleIncludeOperator().

◆ end() [2/2]

template<class T>

const_iterator GrowVector< T >::end ( ) const

inline

returns an iterator to the end

Definition at line 90 of file growvector.h.

90{ return const_iterator(*this,size()); }

References size().

◆ front() [1/2]

template<class T>

T & GrowVector< T >::front ( )

inline

access the first element

Definition at line 130 of file growvector.h.

130{ return m_chunks.front()->data.front(); }

References m_chunks.

Referenced by DocHtmlTable::firstRow(), and DocbookDocVisitor::operator()().

◆ front() [2/2]

template<class T>

const T & GrowVector< T >::front ( ) const

inline

access the first element

Definition at line 132 of file growvector.h.

132{ return m_chunks.front()->data.front(); }

References m_chunks.

◆ make_room()

template<class T>

void GrowVector< T >::make_room ( )

inlineprivate

Definition at line 146 of file growvector.h.

    {
      if (m_chunks.empty() ||
          m_chunks.back()->data.size()==chunkSize) // add new chuck if needed
      {
        m_chunks.push_back(std::make_unique<Chunk>());
      }
    }

References chunkSize, and m_chunks.

Referenced by emplace_back(), and push_back().

◆ pop_back()

template<class T>

void GrowVector< T >::pop_back ( )

inline

removes the last element

Definition at line 115 of file growvector.h.

    {
      m_chunks.back()->data.pop_back();
      if (m_chunks.back()->data.size()==0) // remove chunk if empty
      {
        m_chunks.pop_back();
      }
    }

References m_chunks.

Referenced by DocPara::handleCommand(), DocPara::handleFile(), DocPara::handleXRefItem(), DocParser::internalValidatingParseDoc(), DocAutoListItem::parse(), DocInternal::parse(), DocRoot::parse(), and DocSection::parse().

◆ push_back()

template<class T>

void GrowVector< T >::push_back ( T && t )

inline

adds an element to the end

Definition at line 100 of file growvector.h.

    {
      make_room();
      m_chunks.back()->data.push_back(std::move(t));
    }

References m_chunks, and make_room().

◆ size()

template<class T>

size_t GrowVector< T >::size ( ) const

inline

returns the number of elements

Definition at line 93 of file growvector.h.

    {
      return m_chunks.empty() ? 0 : (m_chunks.size()-1)*chunkSize +
                                     m_chunks.back()->data.size();
    }

References chunkSize, and m_chunks.

Referenced by end(), end(), DocPara::handleIncludeOperator(), DocHtmlRow::numCells(), and DocHtmlTable::numRows().

Member Data Documentation

◆ chunkBits

template<class T>

const size_t GrowVector< T >::chunkBits = 4

staticprivate

Definition at line 42 of file growvector.h.

Referenced by at(), and at().

◆ chunkMask

template<class T>

const size_t GrowVector< T >::chunkMask = chunkSize-1

staticprivate

Definition at line 44 of file growvector.h.

Referenced by at(), and at().

◆ chunkSize

template<class T>

const size_t GrowVector< T >::chunkSize = 1 << chunkBits

staticprivate

Definition at line 43 of file growvector.h.

Referenced by GrowVector< T >::Chunk::Chunk(), make_room(), and size().

◆ m_chunks

template<class T>

std::vector<ChunkPtr> GrowVector< T >::m_chunks

private

Definition at line 154 of file growvector.h.

Referenced by at(), at(), back(), back(), clear(), emplace_back(), empty(), front(), front(), make_room(), pop_back(), push_back(), and size().

The documentation for this class was generated from the following file:

src/growvector.h

Classes

Public Types

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Member Typedef Documentation

◆ ChunkPtr

◆ const_iterator

◆ iterator

Member Function Documentation

◆ at() [1/2]

◆ at() [2/2]

◆ back() [1/2]

◆ back() [2/2]

◆ begin() [1/2]

◆ begin() [2/2]

◆ clear()

◆ emplace_back()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ front() [1/2]

◆ front() [2/2]

◆ make_room()

◆ pop_back()

◆ push_back()

◆ size()

Member Data Documentation

◆ chunkBits

◆ chunkMask

◆ chunkSize

◆ m_chunks