Get 1D array index from a 2D array

Question

Is there a way to get the array index of a 1D array from a 2D array?

For Eg: I have a 2D array, the array size is unknown and changes (I've used std::vector) to push_back as and when required. This works fine as long as its a 2D array but I need to get the 1D array index of this 2D array.

2D array:
Group 1 - 1, 2, 3
Group 2 - 4, 5, 6
Group 3 - 7, 8, 9, 10, 11, 12

and so on.

So, basically is there a quick way to know that when 6 is selected from Group 2 i.e. Array[1][2] = 6 => I need the array index as: 1D array=> Array[5] = 6 => i.e. I need 5 as my answer. I have tried several things but no luck so far. Any suggestions?

Was the sum of the sizes of all previous groups plus the index in the current group among the things you tried? — Daniel Daranas, Nov 27 '13 at 15:50
If you are using C++ don't use raw arrays to store matrcies. Use an ADT matrix type (like those provied by Linear algebra libraries) and call their .data() member function. — 111111, Nov 27 '13 at 15:51

yasen · Accepted Answer · 2013-11-27T16:02:38.173

2

If your data is static, you can make another array in which you will store the offset for each 1D array. For your example, you will have the following array offset = {0, 3, 6}. Then you can find the index by offset[row] + col.

If you can change the row sizes, then you can store the size of each row in a Binary indexed tree and find the offset in O(log n) with a single query, where n is the amount of rows (1D vectors). However, each time you change the row size, you would have to update the structure again in O(log n).

edited Nov 27 '13 at 16:02

answered Nov 27 '13 at 15:53

yasen

1,250
7
13

offset technically would be the .size() parameter of std::vector wouldn't it for each group? – Neophile Nov 27 '13 at 15:54
1

@TheNewbie Yes, the accumulated .size() parameters of each group. (as offset will be an array) – yasen Nov 27 '13 at 15:56
Your answer looks very promising but I am still trying to get the offset. Any suggestions on how do I get that? The .size() just gives me the current size of the Group. – Neophile Nov 27 '13 at 17:01
1

@TheNewbie I guess something like (assuming group is implemented as vector< vector > and offset is an regular array of ints): `offset[0] = 0; for (int row=0; row < (int)group.size; ++row) offset[row+1] = offset[row] + (int)group[row].size();` – yasen Nov 27 '13 at 17:14

score 0 · Answer 2 · answered Nov 27 '13 at 15:56

If you are creating a vector of vectors (or a list of vectors), the memory locations are not guaranteed to be related. So to make it behave like a 1-dimensional array, you would need to wrap the container in your own class and overload operator[]. That operator would then need to check the index to determine the proper vector element to return. A simplified version might look like:

T& operator[](std::size_t index)
{
    std::size_t temp = index;
    if (index < myVectors[0].size())
    {
        return myVectors[0][index];
    }

    temp = index - myVectors[0].size()
    if (temp < myVectors[1].size())
    {
        return myVectors[1][temp];
    }

    // etc ...
}

You can simplify it to a loop:

T& operator[](std::size_t index)
{
    std::size_t temp = index;
    for (std::size_t i = 0; i < myVectors.size(); ++i)
    {
        if (temp < myVectors[i].size())
        {
            return myVectors[i][temp];
        }
        temp -= myVectors[i].size();
    }
    throw std::out_of_range("Array access out of bounds!");
}

Get 1D array index from a 2D array

2 Answers2