Fast C++ container combining the best features of std::vector and std::deque

veque

The double-ended vector


A very fast C++17 container combining the best features of std::vector and std::deque

"In Most Cases, Prefer Using deque (Controversial)"

-Herb Sutter, GotW #54

veque is an allocator-aware, efficient container with interface matching both std::vector and std::deque. Its data layout is very similar to std::vector, but with unused storage maintained both before and after the used storage.

Features

  • Like std::vector, veque is an ordered container in cache-friendly, array-compatible contiguous memory. That makes the data compatible with C APIs, pointer iteration, gsl::span, and similar.
  • Like std::deque, veque allows fast insertion/deletion from the front of the container
  • Because veque can resize from both sides, insertions and erasures from arbitrary locations will be twice as fast, because there are often two choices for what data to shift.

Usage

The complete API documentation may be viewed here.

The interface for veque maintains the entire interface for std::vector, allowing veque to be considered as a drop-in replacement. (See tradeoffs)

In addition, veque provides the following additional functions:

std::deque interface:

  • push_front()
  • emplace_front()
  • pop_front()

End-specific resizing:

  • resize_front()
  • resize_back() (Same as resize(), to match std::vector and std::deque behavior)
  • capacity_front()
  • capacity_back() (Same as capacity(), to match std::vector and std::deque behavior)
  • capacity_full()
  • reserve(size_type, size_type)

Strong exception guarantee pop-and-return, courtesy C++17:

  • pop_back_element()
  • pop_front_element()

In the spirit of C++20, it is reasonable to ask for the size as a signed type:

  • ssize()

Tradeoffs

Is veque better than std::vector in every conceivable way? No. But the tradeoffs are appealing.

  • veque is a bit more eager to preallocate memory than a typical std::vector implementation, to anticipate resizing from either end. (New - configurable via traits class!)
  • insert() and erase() function calls should be assumed to invalidate all iterators and references, since the resizing could happen from either direction. By comparison, the same std::vector and std::deque operations will sometimes only invalidate some of the iterators and references. (New - configurable via traits class!)
  • veque<bool> is not specialized. Whether that makes it better or worse is up to you.

Why "veque"?

As a developer, I am not good at naming things.

double_ended_vector?

dextor?

To do:

  • Perhaps C++14 support?
Similar Resources

About Write a program to create a circular doubly linked list and perform insertions and deletions of various cases

Write a program to create a circular doubly linked list and perform insertions and deletions of various cases Circular Doubly Linked List Circular Dou

Aug 28, 2021

This repository aims to solve and create new problems from different spheres of coding. A path to help students to get access to solutions and discuss their doubts.

CPP-Questions-and-Solutions 🎯 This repository aims to solve and create new problems from different spheres of coding, which will serve as a single po

Jul 27, 2022

The Repository Contains all about Data Structure and Algorithms with Practice problems, series, and resources to follow!

🏆 The Complete DSA Preparation 🏆 This repository contains all the DSA (Data-Structures, Algorithms, 450 DSA by Love Babbar Bhaiya,STriver Series ,FA

Jan 8, 2022

Starting with OpenCV and Qt on MacOS is a bit of difficult if you haven't installed and used libraries in XCode.

Starting with OpenCV and Qt on MacOS is a bit of difficult if you haven't installed and used libraries in XCode.

OpenCV and Qt on MacOS Introduction Starting with OpenCV and Qt on MacOS is a bit of difficult if you haven't installed and used libraries in XCode. T

Nov 18, 2021

A place where you can learn and practise various Problems and algorithms

A place where you can learn and practise various Problems and algorithms

Problem-Solving Problem solving is an art of solving some real time challenges. And this is a place to get started, you can find many problems to solv

Apr 22, 2022

This repo is created to post all my codes and learning of C++ and DSA in C++

This is a readme file where you can read some documentaton about learning on c++and Data Structures and algorithms . I will be posting each and every

Jul 27, 2022

Slides and other materials from CppCon 2020

CppCon 2020 Presentation Materials https://github.com/CppCon/CppCon2020 is the canonical location for presentations and code from CppCon 2020. For Spe

Aug 16, 2022

Slides and other materials from CppCon 2019

CppCon 2019 Presentation Materials https://github.com/CppCon/CppCon2019 is the canonical location for presentations and code from CppCon 2019. For Spe

Aug 7, 2022

Slides and other materials from CppCon 2018

CppCon 2018 Presentation Materials https://github.com/CppCon/CppCon2018 is the canonical location for presentations and code from CppCon 2018. For Spe

Aug 15, 2022
Comments
  • Faster still.

    Faster still.

    Veque now knows if a 'reallocation' doesn't require new underlying storage - that the current storage satisfies new memory requirements. In this case, elements are shifted within the current storage, instead of using the allocator.

  • Support for single-pass input iterators.  alloc_traits is now a publi…

    Support for single-pass input iterators. alloc_traits is now a publi…

    …c type. Private functions _copy_construct_range and _nothrow_move_construct_range now match std::copy function signature. Comparison operators no longer require matching allocators or resize strategies.

  • Meson build system support

    Meson build system support

    veque looks useful, especially in comparison with std::deque.

    I'd like to use it in mediasoup, but for that Meson build system support would be needed.

    Creating this for tracking purposes, will likely contribute later (should be very simple) unless you're opposed to including it.

This is a simple UNITEST to test the implementation of the the various container types of the C++ standard template library

ft_container UNITest. This is a simple UNITEST to test the implementation of the the various container types of the C++ standard template library that

Aug 5, 2022
C++ intrusive container templates. Abstract node links, no use of new/delete.

C-plus-plus-intrusive-container-templates C++ intrusive container templates. Abstract node links, no use of new/delete (AVL tree, singly-linked list,

Feb 10, 2022
Collaborative Collection of C++ Best Practices.

Collaborative Collection of C++ Best Practices. This online resource is part of Jason Turner's collection of C++ Best Practices resources.

Aug 11, 2022
A cheatsheet of modern C++ language and library features.

C++20/17/14/11 Overview Many of these descriptions and examples come from various resources (see Acknowledgements section), summarized in my own words

Aug 8, 2022
simple and fast scripting language

The Aument Language The Aument language is a work-in-progress dynamically-typed scripting language with performance first: this scripting language is

Mar 21, 2022
Simple, fast, safe, compiled language for developing maintainable software
Simple, fast, safe, compiled language for developing maintainable software

Simple, fast, safe, compiled language for developing maintainable software. Compiles itself in <1s with zero library dependencies.

Aug 8, 2022
Welcome to my dungeon. Here, I keep all my configuration files in case I have a stroke and lose all my memory. You're very welcome to explore and use anything in this repository. Have fun!

Fr1nge's Dotfiles Welcome to my dungeon. Here, I keep all my configuration files in case I have a stroke an d lose all my memory. You're very welcome

Apr 16, 2022
This repository contains notes and starter code for Bit manipulation and mathematics session for DSA bootcamp organized by Codeflows.

Bitmanipulation_maths This repository contains notes and starter code for Bit manipulation and mathematics session for DSA bootcamp organized by Codef

Jun 15, 2022
cpp fundamentals and questions for beginners and intermediates
cpp fundamentals and questions for beginners and intermediates

DSA 60 days Hi people! So we have started grasping dsa concepts and solving problems from 12 July. And we shall continue till September 10 Starting fr

Aug 6, 2022
A demonstration of implementing, and using, a "type safe", extensible, and lazy iterator interface in pure C99.

c-iterators A demonstration of implementing, and using, a "type safe", extensible, and lazy iterator interface in pure C99. The iterable is generic on

Jul 26, 2022