How can I shift elements to left (in order to implement erase) in c++ container?

Viewed 288

From my previous question: How to implement erase on vector in c++, I have tried to implement erase via allocating new memory, and copying all elements except of that one erase to new array. From the answers, it is not a standard way of vector from STL, where the vector keeps old elements untouched, and only moves elements back after the one erased (this is part of the "invalidation" of previous iterators. So I have tried to use std::move():

#ifndef _vec_h
#define _vec_h

#include <stddef.h>
#include <memory>
#include <algorithm>

template<class T>
class Vec
{
public:
    typedef T* iterator;
    typedef T* const const_iterator;
    typedef T value_type;

    Vec() {
        create();
    }
    explicit Vec(size_t n, const T& val = T()) {
        create(n, val);
    }
    Vec(const Vec& v) {
        create(v.begin(), v.end());
    }
    Vec& operator=(const Vec& v);
    ~Vec() {
        uncreate();
    }
    T& operator[](size_t i) {
        return data[i];
    }
    const T& operator[](size_t i) const {
        return data[i];
    }
    void push_back(const T& val);
    size_t size() const {
        return avail - data;
    }
    iterator begin() {
        return data;
    }
    const_iterator begin() const {
        return data;
    }
    iterator end() {
        return avail;
    }
    const_iterator end() const {
        return avail;
    }
    void clear() {
        if (data)
        {
            for (iterator i=avail; i!=data; i--)
                i->~T();
        }
        avail=data;
    }
    std::allocator<T> alloc;

private:
    iterator data;
    iterator avail;
    iterator limit;

    void create();
    void create(size_t n, const T& val);
    void create(const_iterator b, const_iterator e);
    void uncreate();
    void grow();
    void unchecked_append(const T& val);
};


template<class T> Vec<T>& Vec<T>::operator=(const Vec& rhs)
{
    if (&rhs != this)
    {
        uncreate();
        create(rhs.begin(), rhs.end());
    }
    return *this;
}

template<class T> void Vec<T>::push_back(const T& val)
{
    if (avail == limit)
    {
        grow();
    }
    unchecked_append(val);
}

template<class T> void Vec<T>::create()
{
    data = avail = limit = 0;
}

template<class T> void Vec<T>::create(size_t n, const T& val)
{
    data = alloc.allocate(n);
    limit = avail = data + n;
    std::uninitialized_fill(data, limit, val);
}

template<class T> void Vec<T>::create(const_iterator i, const_iterator j)
{
    data = alloc.allocate(j-i);
    limit = avail = std::uninitialized_copy(i, j, data);
}

template<class T> void Vec<T>::uncreate()
{
    if (data)
    {
        iterator i = avail;
        while (i!=data)
        {
            alloc.destroy(--i);
        }
        alloc.deallocate(data, limit-data);
    }
    data=limit=avail=0;
}

template<class T> void Vec<T>::grow()
{
    size_t new_size = std::max(2*(limit-data), ptrdiff_t(1));
    iterator new_data = alloc.allocate(new_size);
    iterator new_avail = std::uninitialized_copy(data, avail, new_data);
    uncreate();
    data = new_data;
    avail = new_avail;
    limit = data + new_size;
}

template<class T> void Vec<T>::unchecked_append(const T& val)
{
    alloc.construct(avail++, val);
}
    //---------------------------------------------------------
    // here I am trying to implement the erase function with 3 pointers (data, avail, limit)
    template<class T>
    T* Vec<T>::erase(T *const i)
    {
       if(i==end())
       {
           return end();
       }
       else if(i >= begin() && i < end())
       {
          std::move(i+1, avail, i); //shift elements to the left
          return i;
       }
       else
       {
          return 0;
       }
    }

#endif

Which still causes segfault. So is there any way, how to implement the erase?

1 Answers

To compile I needed to add this method declaration:

T* erase(T *const i);

I added some quick test code to recreate your segfault:

int main()
{
  Vec<int> test;
  test.push_back(1);
  test.push_back(2);
  test.push_back(3);
  test.push_back(4);
  test.erase(test.begin() + 2);
  std::cout << test[2] << std::endl; // should output 4
}

However, the code outputed 4 as expected, and I did not get any segfault. I tried running in valgrind, and I didn't get any memory errors either. It appears to be working as you intended, but if you add some code to recreate the segfault, I will update the answer with a fix.

Related