Slices in C++

[Ginto8]

As many of you probably know already, I have recently been looking at alternatives to C++. Though I have realized now that C++ is the best tool for what I would do, I have learned a few interesting paradigms and idioms for programming. One of these was the slice. It is a concept I got from Go, and here's the general gist of it:

• it is thought of as a "subarray" - it points to a very specific chunk (or "slice") of an underlying array
  it is, for most intents and purposes, a pointer-length pair
  it can provide information as to the capacity of the underlying array
  the underlying array has an immutable size
  the slice itself can be easily and cheaply resized or moved
  the underlying array is garbage collected

Looking at most of the things, you may wonder, "Why not just pass around a pointer-length pair?" The answer is simple: no necessary memory management. A slice implementation should dynamically allocate the underlying arrays and automatically free them when they are no longer needed. I do it via garbage collecting.

Now enough babbling, time for the code:
Slice.hpp:

Code: Select all

#ifndef SLICE_HPP
#define SLICE_HPP

#include <stdexcept>
#include <cstring>

namespace g {

using namespace std;

template<typename T>
class Slice {
    template<typename U>
    struct Array {
        U* ptr;
        int cap;
        int numRefs;

        Array(U* _ptr = NULL,int _cap = 0) : ptr(_ptr),cap(_cap) {}
        ~Array() { delete [] ptr; }
    };

    static const int MIN_ARRAYSALLOCED = 8;

    static Array<T>* arrays;
    // the cap is so that only O(log n) allocations are done rather than O(n)
    static int numArrays,capArrays;
    static Array<T>& alloc(int cap) {
        Array<T> ret(new T[cap],cap);
        memset(ret.ptr,0,ret.cap*sizeof(T));
        for(int i=0;i<numArrays;++i) {
            Array<T>& ref = arrays[i];
            if(ref.numRefs < 1)
                return (ref = ret);
        }
        if(capArrays == 0) {
            capArrays = MIN_ARRAYSALLOCED;
            arrays = new Array<T>[capArrays];
        } else if(numArrays == capArrays) {
            capArrays *= 2;
            Array<T>* newArrays = new Array<T>[capArrays];
            memcpy(newArrays,arrays,numArrays*sizeof(Array<T>));
            delete [] arrays;
            arrays = newArrays;
        }
        return (arrays[numArrays++] = ret);
    }

    Array<T>* ref;
    int loc,len;

    bool validArray() { return this->ref > arrays &&  this->ref < arrays+numArrays; }

public:

    Slice(int len = 0,int cap = 0,T* data = NULL) : loc(0),len(len) {
        if(len > cap)
            cap = len;
        if(cap > 0) {
            this->ref = &Slice::alloc(cap);
            ++this->ref->numRefs;
            if(data) {
                memcpy(this->ref->ptr,data,len*sizeof(T));
            }
        }
    }
    Slice(const Slice& other) : loc(other.loc),len(other.len) {
        // because this CAN be uninitialized and
        // ref CAN be another value than NULL
        if(this->validArray())
            --this->ref->numRefs;
        this->ref = other.ref;
        if(this->ref)
            ++this->ref->numRefs;
    }

    static const Slice NULLSLICE;

    ~Slice() {
        if(this->ref && !--ref->numRefs)
                delete [] ref->ptr;
    }

    void Copy(Slice other) {
        if(this->ref) {
            int len = this->len > other.len ? other.len : this->len;
            memcpy(this->ref->ptr+this->loc,other.ref->ptr+other.loc,len);
        }
    }

    Slice Copy(int cap = 0) const {
        return this->ref ? Slice(this->len,cap,this->ref->ptr+loc) : Slice(0,cap);
    }

    bool operator==(Slice other) const { return this->ref == other.ref && this->len == other.len && this->loc == other.loc; }

    T& operator[](int offset) const { return this->ref->ptr[this->loc+offset]; }
    T& at(int offset) throw(out_of_range) {
        if(offset > this->len) {
            throw out_of_range("Accessing element beyond slice bounds");
        }
    }

    int Len() const { return this->len; }
    int Cap() const { return this->ref ? this->ref->cap : 0; }

    // create a subslice with the range [start,end)
    Slice Sub(int start,int end) {
        Slice ret = *this;
        ret.loc = start;
        if(this->ref && start >= 0 && end > start && end < this->Cap()+1) {
            ret.len = end-start;
            return ret;
        }
        ret.len = 0;
        return ret;
    }
    Slice Sub(int start) const { return this->Sub(start,this->Len()); }

    static Slice Alloc(int len,int cap = 0) {
        if(len+cap > 0) {
            return Slice(len,cap);
        }
        return Slice::NULLSLICE;
    }

    typedef T* Iter;

    bool Iterate(Iter& i) const {
        if(!this->ref || i-(this->ref->ptr+this->loc) >= this->len-1)
            return false;
        if(i < this->ref->ptr+loc)
            i = this->ref->ptr+loc-1;
        ++i;
        return true;
    }
    Slice::Iter Begin() const {
        if(this->ref)
            return this->ref->ptr+this->loc;
        return NULL;
    }
    Slice::Iter End() const {
        if(this->ref)
            return this->ref->ptr+this->loc+this->len;
        return NULL;
    }

    void Fill(T val = T()) {
        for(Slice::Iter i;this->Iterate(i);) {
            *i = val;
        }
    }
};

template<typename T>
const Slice<T> Slice<T>::NULLSLICE = Slice<T>();
template<typename T>
Slice<T>::Array<T>* Slice<T>::arrays = NULL;
template<typename T>
int Slice<T>::numArrays=0;
template<typename T>
int Slice<T>::capArrays=0;

}

#endif

It's all in namespace g because it's part of LibG, the graphics/windowing library that I'm working on. As for general usage:

Code: Select all

#include "Slice.hpp"
#include <cstdio>
using namespace g;
using namespace std;

int main() {
    // create a slice of an array with len 15 and cap 20
    Slice<int> x = Slice<int>::Alloc(15,20);

    int y = 0;
    // built-in iteration function
    for(Slice<int>::Iter i;x.Iterate(i);)
        // fill the slice
        *i = y++;
    // create a slice of the elements [3,10)
    Slice<int> z = x.Sub(3,10);
    printf("Contents of x:\n");
    // also allows for more conventional iteration
    for(Slice<int>::Iter i=x.Begin();i<x.End();++i)
        printf("%d\n",*i);
    printf("\nValues in z:\n");
    // z is a subarray of x
    for(Slice<int>::Iter i=NULL;z.Iterate(i);)
        printf("%d\n",*i);
    // set z to the NULL value
    z = Slice<int>::NULLSLICE;
    // x now refers to the whole array
    x = x.Sub(0,x.Cap());
    printf("\nValues of whole underlying array:\n");
    for(Slice<int>::Iter i=NULL;x.Iterate(i);)
        printf("%d\n",*i);
    // no need for any memory freeing, it's all done automatically
    return 0;
}

Any questions, just ask.

EDIT: OK the code is fixed use to your heart's content

[WSPSNIPER]

wow that looks very impressive and usefull! thanks for teaching me this