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!