Skip to main content
Tweeted twitter.com/StackCodeReview/status/1441598560965840896
Became Hot Network Question
edited tags
Link
Toby Speight
  • 81.7k
  • 14
  • 101
  • 308
Source Link

C++11 Custom Vector Implementation

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!