Articles An Enhancement to std::vector by Greg Utas

[emailx45]

An Enhancement to std::vector
Greg Utas - 13/Jun/2020

Спойлер: Content

[SHOWTOGROUPS=4,20]

Adding erase() and replace() functions
This article describes how to extend std::vector with erase() and replace() functions that allow it to be used for things like the socket descriptor passed to TCP's poll().

Introduction
Users of std::vector typically insert and erase elements only at the end of the vector, with push_back and pop_back respectively. But what if we need the ability to erase or replace any element? Although vector provides an erase function, it fills the vacated slot by moving all of the subsequent items up, which can be very inefficient.

Background
Для просмотра ссылки Войди или Зарегистрируйся in the Для просмотра ссылки Войди или Зарегистрируйся (RSC) originally used a raw array to implement the file descriptor (of handles to sockets) that is passed to TCP's poll function. I wanted to see if std::vector could be used instead, and this article describes the code that emerged.

Using the Code
The problem with using vector for a socket descriptor is that any socket can be released when a TCP connection is closed. Implementations of poll require the sockets to be contiguous, without any intervening invalid (null) entries. This can be achieved by moving the array's last socket into the slot that is vacated when a socket is removed from the middle of the array. However, vector does not support this behavior. It only provides the restrictive pop_back and inefficient erase. It is therefore necessary to implement the capability with a new template which forwards to vector when possible, but which adds new functions when necessary.

If this new template is to be general purpose, it should support any type of object, not only socket handles. It should therefore preserve the semantics of pop_back, which also deletes the object that is being removed. The new template should also allow for a custom allocator, in the same way as vector.

I ended up calling the new template Для просмотра ссылки Войди или Зарегистрируйся, which is rather uninspired. Maybe you can suggest a better name. In any case, let's look at its data and functions.

#include <cstddef>
#include <memory>
#include <utility>
#include <vector>

template< typename T, class A = std::allocator< T >> class Array
{
   //  The maximum size allowed for the array.
   //
   size_t max_;

   //  The array of items.
   //
   std::vector< T, A > vector_;
};

Array is implemented in terms of vector but enforces a maximum length. If you don't want a limit, you can remove occurrences of max_ or simply set it to SIZE_MAX.

Next, we have some simple things:

Array() : max_(0) { }

~Array() = default;

Array(const Array& that) = delete;

Array& operator=(const Array& that) = delete;

//  Specifies that the array is limited to MAX elements.
//
void Init(size_t max) { max_ = (max < 2 ? 2 : max); }

Before elements can be added to Array, Init must be invoked to set its maximum size. I didn't need Array to be copyable, so I deleted those functions. If you need them, they can be defaulted, the same as the destructor.

Next, we have functions that often just forward to vector. However, they also enforce the maxium size and use RSC's Для просмотра ссылки Войди или Зарегистрируйся to support a function trace tool and exceptions with stack traces. Dependencies on Debug.h have been removed from the code shown in this article but have been retained in the .zip file.

Спойлер: Code

bool PushBack(T& item)
{
   if(vector_.size() >= max_) return false;
   vector_.push_back(item);
   return true;
}

size_t Size() const { return vector_.size(); }

bool Empty() const { return vector_.empty(); }

const T& Front() const { return vector_.front(); }

T& Front() { return vector_.front(); }

const T& Back() const { return vector_.back(); }

T& Back() { return vector_.back(); }

const T& At(size_t index) const { return vector_.at(index); }

T& At(size_t index) { return vector_.at(index); }

const T& operator[](size_t index) const { return vector_[index]; }

T& operator[](size_t index) { return vector_[index]; }

const T* Data() const
{
   if(vector_.empty()) return nullptr;
   return vector_.data();
}

T* Data()
{
   if(vector_.empty()) return nullptr;
   return vector_.data();
}

bool Reserve(size_t capacity)
{
   if(capacity > max_) return false;
   vector_.reserve(capacity);
   return true;
}

Finally, we get to the new functions, Erase and Replace. Both use std::swap so they can reuse pop_back and its side effect of deleting an element:

Спойлер: Code

//  Erases the item in the cell specified by INDEX and moves
//  the last item into its cell.
//
void Erase(size_t index)
{
   auto size = vector_.size();
   if(index >= size) throw("invalid index for Array.Erase");
   if(index < (size - 1))
   {
      std::swap(vector_[index], vector_.back());
   }
   vector_.pop_back();
}

//  Replaces the item in the cell specified by INDEX with ITEM.
//
void Replace(size_t index, T& item)
{
   if(&item == nullptr) throw("invalid item for Array.Replace");
   auto size = vector_.size();
   if(index >= size) throw("invalid index for Array.Replace");

   //  As Mircea points out in his comment, the following could
   //  simply be replaced by
   //    vector_[index] = item;
   //
   vector_.push_back(item);
   std::swap(vector_[index], vector_.back());
   vector_.pop_back();
}

Source: https://dumpz.ws/resources/an-enhancement-to-std-vector.172/

History

• 13th June, 2020: Updated based on Mircea's comments
• 12th June, 2020: Initial version

License
This article, along with any associated source code and files, is licensed under The GNU General Public License (GPLv3)

[/SHOWTOGROUPS]