A Wrapper for std::vector

• Download source - 1.6 KB

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

TcpIoThread in the Robust Services Core (RSC) originally used a raw array to implement the file descriptor (of handles to sockets) that it passes to TCP's poll function. I wanted to see if std::vector could be used instead, and this tip 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 desired behavior 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 Array, 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 Debug.h 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.

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 Erase function, which uses std::swap so that can reuse pop_back and its side effect of deleting an element. Note that, unlike vector::erase, this does not preserve the order of elements:

//  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();
}

We can also define a Replace function. Note that this overwrites the existing object, so check that it has a copy operator (operator=) if it has a destructor!

//  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");
   vector_[index] = item;
}

History

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