Click here to Skip to main content
15,867,835 members
Articles / Programming Languages / C++
Tip/Trick

A Wrapper for std::vector

Rate me:
Please Sign up or sign in to vote.
4.50/5 (2 votes)
23 Jun 2020GPL33 min read 18.9K   126   2   18
Replacing its erase() function
This article describes how to wrap std::vector with a different erase() function, and a new replace() function, that allows 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

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.

C++
#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:

C++
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.

C++
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:

C++
//  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!

C++
//  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

  • 13th June, 2020: Update Replace 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)


Written By
Architect
United States United States
Author of Robust Services Core (GitHub) and Robust Communications Software (Wiley). Formerly Chief Software Architect of the core network servers that handle the calls in AT&T's wireless network.

Comments and Discussions

 
GeneralMy vote of 5 Pin
User 1106097917-Aug-20 7:02
User 1106097917-Aug-20 7:02 
GeneralRe: My vote of 5 Pin
Greg Utas17-Aug-20 7:56
professionalGreg Utas17-Aug-20 7:56 
I don't think any upvotes have disappeared. This was published fairly recently and isn't very exciting. Smile | :) I think downvotes are sometimes deleted for obvious trolling or after an article is significantly revised, but I've never heard of it being done for upvotes.

GeneralMy vote of 3 Pin
Stefan_Lang14-Jul-20 21:13
Stefan_Lang14-Jul-20 21:13 
GeneralRe: My vote of 3 Pin
Greg Utas15-Jul-20 2:22
professionalGreg Utas15-Jul-20 2:22 
GeneralRe: My vote of 3 Pin
Stefan_Lang15-Jul-20 3:27
Stefan_Lang15-Jul-20 3:27 
GeneralRe: My vote of 3 Pin
Greg Utas15-Jul-20 3:33
professionalGreg Utas15-Jul-20 3:33 
GeneralRe: My vote of 3 Pin
Stefan_Lang15-Jul-20 3:35
Stefan_Lang15-Jul-20 3:35 
GeneralRe: My vote of 3 Pin
Greg Utas15-Jul-20 3:46
professionalGreg Utas15-Jul-20 3:46 
Questionstd::remove might be a nicer way of doing this. Pin
m0pey27-Jun-20 0:47
m0pey27-Jun-20 0:47 
AnswerRe: std::remove might be a nicer way of doing this. Pin
Greg Utas27-Jun-20 0:58
professionalGreg Utas27-Jun-20 0:58 
GeneralRe: std::remove might be a nicer way of doing this. Pin
m0pey27-Jun-20 1:48
m0pey27-Jun-20 1:48 
QuestionThis technique doesn't preserve element order Pin
hpcoder218-Jun-20 16:34
hpcoder218-Jun-20 16:34 
AnswerRe: This technique doesn't preserve element order Pin
Greg Utas19-Jun-20 0:09
professionalGreg Utas19-Jun-20 0:09 
QuestionA tip/trick... Pin
User 1106097913-Jun-20 9:10
User 1106097913-Jun-20 9:10 
AnswerRe: A tip/trick... Pin
Greg Utas13-Jun-20 9:49
professionalGreg Utas13-Jun-20 9:49 
GeneralRe: A tip/trick... Pin
User 1106097913-Jun-20 9:51
User 1106097913-Jun-20 9:51 
Questionstd::vector already has an erase method Pin
Mircea Neacsu13-Jun-20 3:32
Mircea Neacsu13-Jun-20 3:32 
AnswerRe: std::vector already has an erase method Pin
Greg Utas13-Jun-20 4:09
professionalGreg Utas13-Jun-20 4:09 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.