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
– Daniel Daranas, Commented Nov 27, 2013 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
– 111111, Commented Nov 27, 2013 at 15:51

yasen · Accepted Answer · 2013-11-27 16:02:38Z

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, 2013 at 16:02

answered Nov 27, 2013 at 15:53

yasen

1,2607 silver badges13 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Neophile Over a year ago

offset technically would be the .size() parameter of std::vector wouldn't it for each group?

yasen Over a year ago

@TheNewbie Yes, the accumulated .size() parameters of each group. (as offset will be an array)

Neophile Over a year ago

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.

yasen Over a year ago

@TheNewbie I guess something like (assuming group is implemented as vector< vector<int> > 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();

Zac Howland · Accepted Answer · 2013-11-27 15:56:22Z

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!");
}

Collectives™ on Stack Overflow

Get 1D array index from a 2D array

2 Answers 2

4 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related