C++11 Custom Vector Implementation

Question

This was my solution to an interview question:

Q: Implement an std::vector style container (does not have to be exactly compatible) with a fixed buffer and the following requirements and restrictions:

• The fixed buffer size should be provided by a template parameter.
• No dynamic memory allocations are allowed.
• Implement a “push_back” function that places an element to the end of the container if there is still room.
• Implement an “insert” function that inserts an element into a given position and moves other elements.
• Implement an “operator[]” function for the query of an element at a given index.
• Implement a “size” function, which returns the actual length of the vector

My solution:

#include <cstddef>
#include <stdexcept>

#ifndef NDEBUG
#include <iostream>
#endif /* !defined NDEBUG*/

/**
 * @brief      A vector with a fixed storage buffer implementing part of the std::vector interface
 */
template<int BUFFER_SIZE, typename T>
class Stable_vector{
public:

  /**
   * @brief      Syntax sugar to initialize the vector from { ,,, }
   *
   * @param[in]  list  The initializer list
   */
  Stable_vector (std::initializer_list<T> list) {
    for (auto i = list.begin(); i != list.end(); i++)push_back(*i);
  }
  Stable_vector (void){ }

  /**
   * @brief      Pushes an element into the array if there is capacity
   *
   * @param[in]  data  The data to be pushed back
   */
  void push_back(T data){
    if(BUFFER_SIZE > used_elements){
      internal_buffer[used_elements] = data;

      #ifndef NDEBUG
      std::cout << this << "->push_back: Pushing value " << data << " to ["<< used_elements <<"]"<< std::endl;
      #endif /* !defined NDEBUG*/

      ++used_elements;
    }else throw std::runtime_error("Vector Out of capacity!");
  }

  /**
   * @brief      Pops an element from the array if there is any
   *
   * @return     The copy of the element removed from the vector.
   *             It returns with a copy on purpose, as a reference would poit to a buffer
   *             item which may be overwritten later.
   */
  T pop_back(void){
    if(0u < used_elements){

      #ifndef NDEBUG
      std::cout << this << "->pop_back: Popping out internal buffer["<< (used_elements - 1u) <<"] -> " << internal_buffer[used_elements - 1u] << std::endl;
      #endif /* !defined NDEBUG*/

      --used_elements;
      return internal_buffer[used_elements]; /* as @used elements represents size and not index, it is at the correct position after the decrease */
    }else throw std::runtime_error("Nothing to pop from the Vector!");
  }

  /**
   * @brief      Pushes an element into the given index in case it is inside the used capacity
   *             of the vector. The last previously stored item is lost when the vector is at 
   *             full capacity.
   *
   * @param[in]  data   The data to be inserted
   * @param[in]  index  The index to insert the data at
   */
  void insert(T data, std::size_t index){

    #ifndef NDEBUG
    std::cout << this << "->insert: Trying to put value "<< data <<" into ["<< index <<"]" << std::endl;
    #endif /* !defined NDEBUG*/

    if(used_elements > index){
      if(BUFFER_SIZE > used_elements){

        #ifndef NDEBUG
        std::cout << this << "->insert: Pushing back the last item because ("<< BUFFER_SIZE <<">"<< used_elements <<")" << std::endl;
        #endif /* !defined NDEBUG*/

        this->push_back(this->back());
        /*!Note: by now it is guaranteed that there is at least 1 element in the vector
         *      because of the unsignedness of @index; In case (@used_elements > @index)
         *      @used_elements is at least 1 in this block.
         */
      }

      /* Copy the items from the index until the end */
      for(int copy_index =  (used_elements - 1u); copy_index >= index; --copy_index){
        (*this)[copy_index] = (*this)[copy_index - 1u];

        #ifndef NDEBUG
        std::cout << this << "->insert: Copying ["<< (copy_index - 1) << "]{"<< (*this)[copy_index - 1] << "}"
        << " to ["<< copy_index << "]" << std::endl;
        #endif /* !defined NDEBUG*/

      }

      #ifndef NDEBUG
      std::cout << this << "->insert: Finally ["<< index << "] = "<< data << std::endl;
      #endif /* !defined NDEBUG*/
      (*this)[index] = data;

    }else throw std::runtime_error("Index Out of bounds");
  }

  /**
   * @brief      Returns the number of elements stored in the vector
   *
   * @return     The number of elements
   */
  std::size_t size(void) const{
    return used_elements;
  }

  /**
   * @brief      Array indexer operator.
   *
   * @param[in]  index  The index
   *
   * @return     Non-const reference to the stored element or a tasty std::runtime_error
   */
  T& operator[](std::size_t index){
    if(used_elements > index){
      return internal_buffer[index];
    }else throw std::runtime_error("Index Out of bounds");
  }

  /**
   * @brief      Provides the last stored element in the vector if there is any
   *
   * @return     Non-const reference to the stored element or a tasty std::runtime_error
   */
  T& back(void){
    if(0u < used_elements){
      return internal_buffer[used_elements - 1u];
    }else throw std::runtime_error("No elements to provide!");
  }

private:
  T internal_buffer[BUFFER_SIZE];
  std::size_t used_elements = 0u;
};

I already sent it, but I'd like to get better at what I do. What could be improved with this? Thank you in advance!

Answer 1

This is not a bad attempt at making a vector-like container, except it is lacking support for const and makes unnecessary copies (see below for a more detailed explaination). The variable names are quite well chosen. It's also good to see Doxygen documentation.

Use std::size_t for the size of the storage

The template parameter BUFFER_SIZE should have type std::size_t. This will then also consistent with the type of used_elements. std::size_t is almost always the right type for sizes, counts and indices.

Omit void from empty parameter lists

Functions that don't take parameters should be declared as foo(), not foo(void). The latter is necessary for C, but not for C++.

Use = default to generate a default constructor

If you want the compiler to create a default constructor that takes no arguments, use = default to declare it:

Stable_vector() = default;

The same would go for other constructors and for destructors. By explicitly defining a constructor with an empty body, the compiler will treat it as a user-defined constructor, which sometimes might have some subtle consequences, although it doesn't matter for your class.

Use a consistent code style

I see that sometimes your use of spaces is not consistent, which makes the code look a bit messy. You also sometimes have two statements on the same line; try to limit it to one statement per line. Use a consistent code style (which one you use exactly is of less importance). Instead of fixing everything yourself manually, either check if your code editor has a function to reformat the code, or use an external tool such as Artistic Style or ClangFormat.

Remove debug statements from your code

Debug statements are helpful during initial development and for finding bugs, but it makes the code harder to read. I recommend you remove them, and only temporarily add them back as necessary.

Avoid unnecessary copies

Your push_back() function takes data by value, causing a copy to be made. It then makes another copy when storing it in the internal_buffer. Have a look at std::vector::push_back(): you'll note it has two variants, one that takes a const reference, and the other which takes a forwarding reference. The first one just avoids the first copy, the second one also allows you to std::move() data into internal_buffer, which might avoid part of the second copy, if T has a move assignment operator.

The same goes for insert() of course.

Don't let pop_back() return an element

You'll notice that std::vector::pop_back() is a function that returns void. Instead, you're supposed to use back() to get a reference to the back element, allowing you to read it without making a copy, and then you can remove it with pop_back() afterwards.

Add const versions of operator[] and back()

Since your operator[] and back() are not const functions, they can't be used with a const Stable_vector. You have to add const versions of them (that return const T& of course) to solve this issue.

Mark functions that don't throw exceptions noexcept

If you mark functions that will never throw exceptions as noexcept, this will help the compiler generate more optimal code.

Copy the API of STL containers as much as possible

Have a look at the API of std::vector and follow it as closely as possible, not just the syntax but also the semantics. For example, operator[] does not do bounds checking and will not throw, but there is an at() that does do this. While perhaps not mentioned in the requirements for your interview, it would also be nice to add front(), begin() and end(), emplace_back() and so on, so that your class will be a drop-in replacement for a regular std::vector.

Keep it professional

The code and comments look fine except for the "tasty" exceptions. Avoid making jokes in the code; it doesn't look professional, and it might actually be confusing for non-native speakers that might also need to work on the same code.

Answer 2

  T internal_buffer[BUFFER_SIZE];

This isn't what you want for types that are expensive to construct, or can't be default-constructed.

Your interviewer probably wants to see use of an uninitialized memory buffer, with placement-new and explicit destructor call to create and erase values.

When you get to C++17 or later, then you should probably be using std::uninitialized_value_construct() and std::destroy_at() (from <memory>). TBH, I wouldn't accept a job in a shop still working with C++11 right now...

Answer 3

This isn't bad, but it's not stellar either.

Names matter.

Stable is a very strange name here. It evokes pointer/iterator stability, a term used to indicate that pointers and iterators are stable in memory, for an construct in which they will NOT be.

I would recommend using Inline, instead, to indicate that the memory used is right here (in line) rather than hidden behind an indirection.

Do no default construct items

Creating an empty vector should be a no-op, both for performance reasons and to allow using the vector with non-default constructible items.

I recommend using a dedicated Raw class to represent potentially raw memory. You can use Rust's naming of MaybeUninit if you prefer. The advantage of clearly differentiating Raw<T>& from T& is, like all strong types, that it allows strictly differentiating between them.

template <typename T>
class Raw {
public:
    T const* pointer() const { return reinterpret_cast<T const*>(&mMemory); }
    T* pointer() { return reinterpret_cast<T const*>(&mMemory); }

    T const& ref() const { return *this->pointer(); }
    T& ref() { return *this->pointer(); }

private:
    std::aligned_storage_t<sizeof(T), alignof(T)> mMemory;
};

And from there you get:

template <typename T, std::size_t N>
class InlineVector {
public:
    /* Something */
private:
    std::size_t mSize = 0;
    std::array<Raw<T>, N> mData;
};

The downside is that you now need to implement all 5 special members yourself.

Use range-for syntax

Range-for syntax is easier, just use it.

InlineVector(std::initializer_list<T> list) {
    for (auto& i : list) { ... }
}

Use braces, even for one-liners.

I recommend reading goto fail bug; it's the best justification for the practice.

Use batch operations, for performance.

While calling push_back repeatedly is correct, it unfortunately suffers from the issue of checking the capacity every single time. This is rather unfortunate.

Instead, check once, and then perform the operation.

As a bonus, this means that your function now has transactional semantics, also known as Strong Exception Guarantee.

InlineVector(std::initializer_list<T> list) {
    if (list.size() > this->capacity()) {
        throw std::runtime_error("Insufficient memory");
    }

    for (auto& i : list) {
        new (mData[mSize].pointer()) T(i);
        ++mSize;
    }
}

Factorize, to avoid mistakes.

Of course, since pushing will really happen quite a few times, it's best to factorize all that:

template <typename... Args>
void emplace_back_impl(Args&&... args) {
    assert(this->size() < this->capacity());

    new (mData[mSize].pointer()) T(std::forward<Args>(args)...);

    //  Increment _after_ successfully construction, to avoid accessing
    //  a partially constructed object in case of exception.
    ++mSize;
}

Which allows us to rewrite the constructor as:

InlineVector(std::initializer_list<T> list) {
    if (list.size() > this->capacity()) {
        throw std::runtime_error("Insufficient memory");
    }

    for (T const& i : list) {
        this->emplace_back_impl(i);
    }
}

Note: further improvements would be to consider trivially copyable types.

Use = default whenever possible

Default generated members have special consideration in the standard, unlocking special capabilities.

InlineVector() = default;

Use guard style, instead of if/else

More of a stylistic rule, however the use of if/else tend to leave to convoluted highly-nested statements, which is hard for humans to follow.

Simpler code being better, favor guard styles:

void push_back(T data) {
    if (this->size() == this->capacity()) {
        throw std::runtime_error("Insufficient memory");
    }

    this->push_back_impl(data);
}

As a bonus, you'll note the check is very similar to that of the constructor, which means it should be factored away:

void ensure_space_for(std::size_t extra) {
    //  Careful here, this->size() + extra could overflow std::size_t.
    if (extra >= this->capacity() || this->size() >= this->capacity() - extra) {
        throw std::runtime_error("Insufficient memory");
    }
}

Allowing use to rewrite:

void push_back(T data) {
    this->ensure_space_for(1);

    this->push_back_impl(data);
}

Move, move!

Use moves whenever possible, they're more efficient than copies:

void push_back(T data) {
    this->ensure_space_for(1);

    this->push_back_impl(std::move(data));
}

Do not use primitive logging

You may need to use logging during debugging; that is fine.

DO NOT activate such crude logging with a generic-purpose flag such as NDEBUG. Your users will hate you.

And, really, consider removing such logging after you've tested and validated your code.

Do not use void for empty parameters list.

C++ is not C.

T pop_back() {
    //  OP: feel free to use an exception if you wish to.
    assert(this->size() > 0);

    --mSize;
    T& slot = (mData[mSize].ref();

    T result = std::move(slot);
    slot.~T();

    return result;
}

Note: I appreciate you deviating from std::vector and allowing users to pop-back a value in a single expression. Nice.

Consider Exception Safety

I won't lie, insert is hard in C++.

The most efficiency way is to move elements, creating gaps of raw memory when inserting multiple elements. Fortunately, here, we have a single element, so we're good.

void insert(T data, std::size_t at) {
    this->ensure_space_for(1);
    this->ensure_within_bounds(at);

    if (at == mSize) {
        this->push_back_impl(std::move(data));
        return;
    }

    assert(mSize > 0);

    //  Move last element into raw memory
    new (mMemory[mSize].pointer()) T(std::move(mMemory[mSize-1].ref()));

    //  Size cannot be incremented before the previous move, as in
    //  case of exception, there is no fully constructed element in
    //  the "new" slot.
    //  It should be incremented immediately afterwards, however, to
    //  ensure the element is destructed if anything goes wrong in
    //  latter operations.
    ++mSize;

    //  Move all elements from [at, mSize-1) to [at+1, mSize)
    for (std::size_t i = mSize - 1; i > at; --i) {
        mMemory[i].ref() = std::move(mMemory[i - 1].ref());
    }

    //  Overwrite element at index `at`.
    mMemory[at].ref() = std::move(data);
}

Note: for performance reasons, it would be better to delegate the entire "move sequence" to a separate function, which could be specialized for trivially copyable types -- think int.

Provide const/non-const access pairs.

It's very frustrating not to be able to use an access method because it was forgotten.

Exceptions have a cost, asserts are free.

Exceptions have a cost, so it may be best to avoid introducing exceptions in functions for which std::vector doesn't throw, as it may introduce unacceptable overhead preventing the switch to your variant.

Asserts are free (in Release), though, so pop them liberally.

T const& back() const {
   assert(mSize > 0);
   return mMemory[mSize - 1].ref();
}

T& back() {
   assert(mSize > 0);
   return mMemory[mSize - 1].ref();
}

T const& operator[](std::size_t at) const {
   assert(at < mSize);
   return mMemory[at].ref();
}

T& operator[](std::size_t at) {
   assert(at < mSize);
   return mMemory[at].ref();
}

Note: it would be tempting to implement back() in terms of (*this)[mSize - 1], and it would "work" even if mSize is 0, but it would be a bit confusing in the assert... sometimes a bit of duplication is clearer.

On testing.

I've written my fair share of containers in C++, and if I have one word of advice with regard to testing, it's that valgrind is your friend.

I tend to use a very simple HeapString class for testing, written on top of std::unique_ptr<char[]>. This requires an independent memory allocation for every instance, which means that any issue in forgetting to construct, badly copying/moving, or forgetting to destruct, is immediately flagged by Valgrind.

Combine with some "exhaustive" testing of each method, and I get very strong guarantees that I didn't mess things up.

Answer 4

1. Debug-code

   1. The proper destination for debug-output is std::clog (which goes to STDERR by default, std::cerr has the same destination but no buffering), not std::cout (which goes to STDOUT). Doubly so for trace-output.

   2. I guess you resort to std::endl because you use the wrong stream, though that's still a poor excuse. If you need an explicit flush, be explicit and use std::flush. Don't leave us wondering if you just wanted a newline.

   3. Get rid of all the conditional compilation using the preprocessor.
      While it might make sense to allow tracing your calls, code it similar to assert() or at least get rid of it at the end. Also, don't hang it on NDEBUG, tracing is far more intrusive.

   // trace.h
   #ifdef TRACE
   #undef trace
   #include <iostream>
   template<class...Ts>
   inline void trace(Ts const&... ts) noexcept {
       using T = int[];
       T{0, (std::cerr << ts, void(), 0)};
   }
   #define trace(...) trace(__VA_ARGS__)
   #else
   #define trace(...) void()
   #endif
   
   

2. Model your type on the standard library as good as you can. An interface should be as unsurprising as it can be without burdening the implementation unduly.

   1. Put the templates type-argument first. Everyone else does it.
   2. Use a std::size_t for the size like everyone else.
      Also, if you don't want to name it N, use something more descriptive like CAPACITY.
   3. Allow initialization from arbitrary iterator-pairs. That can be leveraged for std::initializer_list.
   4. Support move- and copy-insertion for .push_back(). The easiest way is by supporting .emplace_back(), as you don't need to special-case copying an element and re-allocation.
   5. For .insert(), create and delegate to .emplace().
   6. .pop_back() should not return anything, because copying the removed element can be a costly waste of time.
   7. operator[] needs a constant overload, and should not catch errors. Adding an assert() would be appropriate though.
      .at() is the member which should check bounds.
   8. .back() also misses its constant overload, and should at most contain an assert() for checking errors.
      Without .front() it seems lonely.
   9. You are missing the whole iterator-interface, among others. At least add a note: // TODO: iterators and more.

3. Polishing the interface

   1. Just use = default; instead of {} for the default ctor. Some code checks for trivial ctors and provides an optimized path.

   2. Use noexcept where expected. Doing so allows the compiler to remove exception-handling code, and there are often faster correct paths for code which cannot throw.

4. Working with raw memory

   1. Don't initialize a bunch of objects you might never need. Use an unnamed union for the data-array to suppress the compiler calling special functions.

      union { T internal_buffer[BUFFER_SIZE]; };
      

   2. Yes, the above point means that the default copy- and move- ctor/assignment as well as the default dtor do the wrong thing. Define them yourself to do the right thing.

   3. Even if you do not want to use the Uninitialized memory algorithms, you can use placement-new and manual destructor-invocation directly. Just include <new>.

5. (void) is the proper parameter-list for a no argument function in C, due to back-compatibility. While C++ accepts it, () is preferred.

Answer 5

if(0u < used_elements)

This is confusing to read and takes more time to understand than

if(used_elements > 0u)

I can understand using the reversed equality comparison 0u == used_elements to prevent accidentally writing used_elements = 0u (although I personally don't like that), but this is entirely unnecessary for inequalities.