Making vector push-front improved to O(1) / 8192

Question

After working on it, my regenerating reserve vector may not be so bad after all. (In this stackoverflow question, I presented a vector with a regenerating reserve, faster at push_back when reserve can't be predicted).

Deque may be cool, but the vector is faster. So, I ameliorated my Vector, with two reserves: one before the begin and another after the end, thus, enabling push_front in a vector very quickly (push_back is still better than a normal vector).

With a RESA of 8192, and 1000 push_front, I had this results (computer is a Lenovo Think Center):

Duration of old push_front == 199 ticks (insert(v.begin () , s))

Duration of new push_front == 5 ticks

What do you think about it?

#ifndef __VECTOR2_HPP
#define __VECTOR2_HPP

class Concept {
public :
  Concept () {}
  ~Concept () {}
  enum const_e { //ok uw : PS = 512, FS 1024
    RESA = 8192
  };
};
#include <vector>
#include <iostream>
#include "Concept.hpp"
#include <exception>
#include <algorithm>

template <typename T>
class Vector : public std::vector<T> {
public :
  class Error : public std::exception {
  public :
    Error (std::string val = "") throw () : val_ (val) {}
    ~Error () throw () {}
    const char* what () throw () {
      std::string s ("Vector Error :");
      s += val_;
      return s.c_str();
    } 
  private :
    std::string val_;
  };
  typename std::vector<T>::iterator begin () {
    typename std::vector<T>::iterator i (std::vector<T>::begin ());
    i += lresa_;
    return i;
  }
  typename std::vector<T>::iterator end () {
    typename std::vector<T>::iterator i (std::vector<T>::end ());
    i -= rresa_;
    return i;
  }
  typename std::vector<T>::const_iterator begin () const {
    typename std::vector<T>::const_iterator i (std::vector<T>::begin ());
    i += lresa_;
    return i;
  }
  typename std::vector<T>::const_iterator end () const {
    typename std::vector<T>::const_iterator i (std::vector<T>::end ());
    i -= rresa_;
    return i;
  }
  typename std::vector<T>::reverse_iterator rbegin () {
    typename std::vector<T>::reverse_iterator i (std::vector<T>::rbegin ());
    i += rresa_;
    return i;
  }
  typename std::vector<T>::reverse_iterator rend () {
    typename std::vector<T>::reverse_iterator i (std::vector<T>::rend ());
    i -= lresa_;
    return i;
  }
  typename std::vector<T>::const_reverse_iterator rbegin () const {
    typename std::vector<T>::const_reverse_iterator i (std::vector<T>::rbegin ());
    i += rresa_;
    return i;
  }
  typename std::vector<T>::const_reverse_iterator rend () const {
    typename std::vector<T>::const_reverse_iterator i (std::vector<T>::rend ());
    i -= lresa_;
    return i;
  }
  Vector () : std::vector<T> (2*(size_t) Concept::RESA, T()), lresa_ ((size_t) Concept::RESA), rresa_ ((size_t) Concept::RESA) {
  }
  size_t size () const {
    size_t s (std::vector<T>::size ());
    s -= lresa_;
    s -= rresa_;
    return s;
  }
  Vector (int n, T t0) : std::vector<T> (n + 2*(size_t) Concept::RESA, t0), lresa_ ((size_t) Concept::RESA), rresa_ ((size_t) Concept::RESA) {
  }
  Vector (const Vector& v) : std::vector<T> (v), lresa_ (v.lresa_), rresa_ (v.rresa_) {
  }
  bool operator == (const Vector& v) const {
    return std::equal (begin (), end (), v.begin ());
  }
  bool operator != (const Vector& v) const {
    return !operator == (v);
  }
  T& operator [] (const size_t &s) {
    return std::vector<T>::operator [] (s+lresa_);
  }
  void push_front (const T& t) {
    if (!lresa_) {
      std::vector<T>::insert (std::vector<T>::begin (), (size_t) Concept::RESA, t);
      lresa_ = (size_t) Concept::RESA;
    }
    typename std::vector<T>::iterator i (std::vector<T>::begin ());
    i += lresa_ -1;
    *i = t;
    --lresa_;
  }
  void push_back (const T& t) {
    if (!rresa_) {
      std::vector<T>::insert (std::vector<T>::end (), (size_t) Concept::RESA, t);
      rresa_ = (size_t) Concept::RESA;
    }
    typename std::vector<T>::iterator i (std::vector<T>::end ());
    i -= rresa_;
    *i = t;
    --rresa_;
  }
  //can be optimized,but that s not the topic
  Vector& operator = (const Vector& v) {
    std::vector<T>::operator = (v);
    lresa_ = v.lresa_;
    rresa_ = v.rresa_;
    return *this;
  }
  //intelligent resize to do  
  //at the moment just stupid
  void resize (size_t n) {
    std::vector<T>::resize (n + lresa_ + rresa_);
  }
private :
  size_t lresa_;
  size_t rresa_;
};
#endif

Answer 1

Your class requires T to be DefaultConstructible for an empty container. std::vector doesn't.

__VECTOR2_HPP - change to VECTOR2_HPP__

Don't publicly inherit from such complex classes as std::vector. For example, think of the results of calling front() on an object of your class.

There is no reason for a hardcoded constant like Concept::RESA. Make it a parameter. Better yet, make the actual extent exponentially growing.

There is no need for rresa_. The std::vector itself handles it better.

Where do you use Vector::Error?

No modifications of your container other than by just looping through push_back() and/or push_front() are thought out at all. The ones inherited from std::vector are broken, and even the ones written by yourself are going to lead to unexpected results with T being something like std::shared_ptr.

Answer 2

Start by adding a type for you base class:

typedef std::vector<T> base;

This can be used to simplify many of your declarations within your code.

Your various begin/end functions can be simplified

auto begin() {
    return base::begin() + lresa_;
}

Unlike vector, your reserved areas contain default constructed objects. While this is not an issue for basic types like int, for more complicated types this can result in a performance hit and additional memory consumption.

Your operator== compares the contents of the reserve areas, which can cause incorrect comparison results. An easy way this can happen is if an element is added then removed (although you do not have any form of remove). Your reserve can be used as a remove proxy, and will leave valid constructed objects in your reserve area if the vector is shrunk.

You lack a operator[] const function.

How will you handle a move constructor?

You can improve your spacing/formatting. Having a space between a function name and the parenthesis is pretty uncommon and (IMHO) makes it harder to read. The overall indentation level is a bit shallow (3 or 4 spaces is more typical).

Answer 3

• This is not what anyone would expect when using a Vector. It's closer to a Deque.

• Use std::size_t, not size_t.

• It looks like we're casting Concept::RESA to size_t every time it's used. Perhaps it should be declared as std::size_t to start with.

---

Inheritance is not a good fit here.

• std::vector does not have a virtual destructor.

• std::vector does not use virtual functions, so the added functions do not override the normal functionality. For example, any function that accepts a std::vector<T> const& will accept a Vector<T> argument. It will then call the std::vector interface, and silently do the wrong thing.

• std::vector has many other functions, e.g. front(), back(), data(), cbegin() etc. that are accessible to class users due to public inheritance, but will not do the expected thing when called, because they aren't overridden.

• Even if all these other functions are re-implemented, the interface of std::vector may change in future, for example adding a new function. New functions will be accessible, but do something unexpected / wrong.

In short, we have to use composition here, not inheritance.