Flexible array(or suggest another data structure)

Question

I need to configure a 1D array in such a way that it's flexible to rearrange, as in pushing back all elements k times every next n elements, and then returning to the previous structure(bring the deleted elements back). Following is an example:

p[10]={        //this is a one-dimensional array
1, 2, 3, 4, 5
4, 5 ,6, 7, 8}


//push each 'row' 2 units back, every 5 elements.
//"Row" here refers to the next nth element, here 5.

<del>, <del>, 3, 4, 5
<del>, <del> ,6, 7, 8


//New structure
<reserved>, <reserved>, 3, 4, 5
<reserved>, <reserved>, 6, 7, 8

//This is how it should look like in terms of data relevance, 
//with the reserved spaces not shown.

    3, 4, 5
    6, 7, 8

Now p[0] should be 3, and p[3]=6.

The easiest way to do this is by creating a new array with the new elements, but I need to keep the old one and perform these operations repeatedly on the same array and then return it back to its original structure. I thought there might be a way using pointers, maybe an array of pointers but I'm not exactly sure. If there is a data structure that makes this easy for me than please point me to it.

Answer 1

You can make your own class, that will represent your array and will work as you want it. Internally it can have a vector of all the elements. Something in the lines of the following code.

Your custom made array:

#include <iostream>
#include <vector>

    class Container
{
public:
    Container(int* buf, int len);

    int operator[] (int i) { return buffer[validIndexes[i]]; }

    void pushRowsBack(int n, int rowLength);
    void restore();

    int size() { return validIndexes.size(); }

private:
    std::vector<int> buffer;
    std::vector<int> validIndexes;
};

Constructor implementation (just an example to have a working example):

Container::Container(int* buf, int len) 
    : buffer(buf, buf+len), 
    validIndexes(len, 0)
{
    for (int i = 0; i < len; ++i)
    {
        validIndexes[i] = i;
    }
}

pushBackRow() implementation:

void Container::pushRowsBack(int n, int rowLength)
{
    int numRows = validIndexes.size() / (float)rowLength + 0.5;
    std::vector<int>::iterator it = validIndexes.begin();

    // go through all the rows
    for (int i = 0; i < numRows; ++i)
    {
        // erase the first n elements in the row
        for (int j = 0; j < n; ++j)
        {
            it = validIndexes.erase(it);
        }

        // advance iterator to the next row
        it += rowLength - n; 
    }
}

restore() implementation:

void Container::restore()
{
    validIndexes.resize(buffer.size());
    for (int i = 0; i < validIndexes.size(); ++i)
    {
        validIndexes[i] = i;
    }
}

Example of usage:

void main()
{
    int buffer[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 };

    Container c(buffer, 13);

    c.pushRowsBack(2, 5);
    for (int i = 0; i < c.size(); ++i)
    {
        std::cout << c[i] << ", ";
    }
    std::cout << std::endl;

    c.restore();
    for (int i = 0; i < c.size(); ++i)
    {
        std::cout << c[i] << ", ";
    }
    std::cout << std::endl;
}

Input:

1, 2, 3, 4, 5, 
6, 7, 8, 9, 10, 
11, 12, 13

Output after pushing back rows with length of 5 by 2 elements:

3, 4, 5, 
8, 9, 10, 
13

Output after restore():

1, 2, 3, 4, 5, 
6, 7, 8, 9, 10, 
11, 12, 13

Answer 2

You have to encapsulate your data into a class that does not behave like a normal list (i.e. hide columns). If you only require to delete columns, then you can do it with something like this: (c++11)

#include <initializer_list>

template <typename DataT, unsigned Rows, unsigned Cols>
class Table
{
public:
    Table(const std::initializer_list<DataT>& list) {
        int i = 0;
        for (const DataT& item : list)
            data[i++] = item;
    }
    void setFirstCol(unsigned v) { firstCol = v; }
    DataT& operator[] (unsigned i) {
        const unsigned c = Cols-firstCol;
        return data[i/c*Cols + i%c + firstCol];
    }
private:
    unsigned firstCol = 0;
    DataT data[Rows*Cols];
};

Usage:

int main() {
    Table<int, 2, 5> table = {
        1, 2, 3, 4, 5,
        4, 5, 6, 7, 8
    };

    cout << table[0] << endl; // 1
    cout << table[5] << endl; // 4

    table.setFirstCol(2); // you can undo this with setFirstCol(0);

    cout << table[0] << endl; // 3
    cout << table[3] << endl; // 6
}

But if you require that any element can be deleted, then you would have to turn each element into a struct containing the element itself and a flag for the deleted state:

template<DataT>
struct Element { // store this struct in your array
    DataT data;
    bool deleted;
};

And you could retrive the element with something similar to this (note the linear complexity):

DataT& operator[](unsigned i) {
    for (Element& e : list) {
        if (i == 0) return e;
        if (!e.deleted) --i;
    }
    throw std::out_of_range("index is out of the container");
}

I think you got the idea.

Answer 3

As suggested by rozina:

#include <cassert>
#include <iostream>
#include <vector>

template <typename T>
class ArrayView
{
public:
    explicit ArrayView(const std::vector<T>& v) : v(&v) { assert(this->v->size() % 5 == 0); }

    const T& operator[] (std::size_t index) const {
        const std::size_t newIndex = getCorrectedIndex(index);

        return v->at(newIndex);
    }

    std::size_t size() const { return (v->size() / 5) * 3; }

private:
    std::size_t getCorrectedIndex(std::size_t index) const {
        return (index / 3) * 5 + (index % 3) + 2;
    }
private:
    const std::vector<T>* v;
};


int main(int argc, char* argv[]) {

    std::vector<int> v = {1, 2, 3, 4, 5,
                          4, 5, 6, 7, 8};
    ArrayView<int> a(v);

    for (std::size_t i = 0, size = a.size(); i != size; ++i) {
        std::cout << a[i] << " ";
        if ((1 +i) % 3 == 0) {
            std::cout << std::endl;
        }
    }
    return 0;
}

output:

3 4 5
6 7 8

Answer 4

You can use vectors for this. It has push_back, pop_back, insert, erase and some other methods. Check here for further information: http://www.cplusplus.com/reference/vector/vector/

vector<int> myArray;

for(int i=0;i<8;i++)
{
    myArray.push_back(i+1);//initialize
}

for(int i=0; i<8; i++)
{
    //do something for finding the first 2 of each 5, (you can use mod 5)
            myArray.erase(myvector.begin()+index) //removing
}