0

I need to store some data based on user's input. My program should create different data structures based on an int value that I get from cin.

For example, a value of 0 stores a scalar, 1 - vector, 2 - 2dArray, 3 - 3dArray, 4 - 4d array and so on...

My question is whether it's possible to write some code that will do this.

I know this might sound confusing, so I'll provide a few more examples.

Let's say the user enters 0 5, then my program should create an int variable and store 5 in it.

If the user enters 1 5,7,6, my program should create a vector = {5,7,6};

If the user enters 2 2,3 1,2,3,4,5,6 my program should create a 2d array a[2][3] and store the values there.

I could figure out a solution if I knew the maximum number of dimensions the user is going to have, but the goal of the assignment is that any number of dimensions can be specified...

Help please

Improve this question
3
  • 1
    Well, no, it is not possible unless you define some limit on the number of dimensions, since it would be infinitely recursive (an n-dimensional array is an array of (n-1) dimensional arrays, so doing what you want requires a type definition that is infinitely recursive, unless you specify a bound). What you can do is use a single dimensional array (or vector) and manage indices to emulate the behaviour you seek. Practically, there are VERY few real-world applications in which 10 or more dimension are needed, and the memory usage of such arrays will quickly exceed available memory anyway. Commented Sep 26, 2016 at 23:40
  • I was thinking about emulation too.. Could you please describe in more detail? How would you implement it? Commented Sep 27, 2016 at 0:03
  • Allocate an array of size equal to the product of dimensions. It has the number of elements that a multi-dimensional array would have. Work out a mapping between a set of indices and an index in the one-dimensional array. Commented Sep 27, 2016 at 0:18

3 Answers 3

Reset to default
1

It is possible if you relax some requirements ("create different data structures based on an int value that I get from cin"). Here's just a sketch, not a full answer, but hopefully it will put you on track.

Access to storage:

You will need to store the numbers in a single array of the desired type and wrap the access to them through an index mapping function. For example, in 2D, one such function is

int indexIn2D(uint rowCol[2], int rowCount) {
  // rowCol[0] - is row index, rowCol[1] is col index
  return rowCol[0]*rowCount + rowCol[1];
}

float* values=new float[numRows*numCols];

// I want the element at (i,j)
float& myIJElement=values[indexIn2D({i,j}, numRows)];

Transforming this into a N-dimension will require something on the line of

// suppose I'm storing a 3D matrix with [3 slices, 4 rows, 5 columns]
// as a 1D array and I want the element at [x,y,z] - what's it would be
// the position of that element in my 1D array?
// - fill coodIndex[3] with {x,y,z}
// - pass nDim=3
// - the dimSignature will be {3 /*slices*/, 4 /*rows*/, 5 /*columns*}
int indexInND(uint coordIndex[], uint numDim, uint[] dimSignature) {
   int ret=coordIndex[0];
   for(uint i=0; i<numDim-; i++) {
      ret=ret*dimSignature[i]+coordIndex[i+1];
   }
   return ret;
}

Variant-like type of storage

Well, we already know we'll be storing the entire "N-dim block" as an unidim array of the target type. So we can make use of pointers and have our "storage" something like

struct NDimStorage {
  // 0 for int, 1 for float, etc.
  int whichType; // or make it enum
  union {
    int* int_st;
    float* float_st;
  };
  uint numDims;
  uint dimSignature[];
};

Fallback fom variant to std::vector

Something like:

template <typename NumType> class VectNStorage {
   std::vector<NumType> storage;
   std::vector<uint> dimSignature;
protected:
   size_t indexMapping(const std::vector<uint>& indices) {
     size_t ret=indices[0];
     for(uint i=0; i<this->dimSignature.size()-1) {
       ret=ret*this->dimSignature[i]+indices[i+1];
     }
     return ret;
   }
public:
  VectNStorage(const std::vector<uint> dimsDef) : storage(), dimSignature(dimsDef) {
    uint howMany=1;
    for(auto d : this->dimSignature) {
      howMany*=d;
    }
    this->storage.resize(howMany);
    std::fill(this->storage.begin(), this->storage.end(), 0);
  }

  NumType& at(const std::vector<uint>& indices) {
    return this->storage[this->indexMapping(indices)];
  }
}
Improve this answer
Sign up to request clarification or add additional context in comments.

13 Comments

1. How do you map a 2D array into a 1D vector? Take the rows and put them one after the other. 2. How do you do it in nDim? well, take the last two dims and 'linearize' them as in 1, You'll get a nDim-1 array. Repeat this until you finish having a single 1D array.
Can I do the above with vectors so that I don't have to worry about memory allocation?
If you do it with vectors, you won't be able to use the NDimStorage variant-like structure. But the index mapping function will still be valid.
@kozouu "Can I do the above with vectors" There, as a sketch (didn't try if even compiles: take it as pseudo-code C++-style). Makes sense?
let me think for a bit :D
|
1
  1. Do you know how to read user input? If not, first figure out how to do that in C++.
  2. Read one variable from user input which will tell you the type of the structure you are going to create. (hint, use an int)
  3. Use appropriate checks to see what the user has entered (hint, use if() {} else if() {} etc.
  4. Based on the initial type, construct an appropriate structure, hint create all your types, for example, a struct Scalar{}, struct Vector{} etc.
  5. Call a read() method in each structure you've created to read in the remainder of the user input. (you will need to use some form of machanism to split the user input, hint: string tokenization)
  6. Reject a type you don't support.
Improve this answer

Comments

0

You can use plain std::vector for all types of user input. The only thing you need is some function f(x) that would map k-size vector of indices to index in plain array.

For example: x - k-sized index vector, s - k-sized dimension size vector

k = 1 -> f1(x,s) = x1;
k = 2 -> f2(x,s) = x2*s2 + x1;
k = 3 -> f3(x,s) = x3*s3*s2 + x2*s2 + x1 = x3*s3*s2 + f2(x2,x1,s2,s1);
k = 4 -> f4(x,s) = x4*s4*s3*s2 + f3(x3,x2,x1,s3,s2,s1);

there multiplier of last coordinate is volume of (k - 1) dimension object. Also, we consider, that numeration of coordinates starts from 0.

This looks like recursive function, that can be easy implemented. You just need to compute shift of (k - 1) dimension object, pop coordinate from array and call function from itself again.

Improve this answer

5 Comments

This looks doable, but what do you mean by k-sized index vector and k-sized dimension size vector? Could you describe the recursion in more detail as well?
@kozouu if your data structure has k dimensions, then you need k indices to address to element of this structure this is k-sized index and it would be natural to use vector to represent k indices. Same with size of data structure. You need to determine size of each dimension which gives k sizes. And they also can be stored as vector.
@SemyonBurov no need for recursion (other than for the intellectual realisation of what's going on). The formula for index-mapping goes similar to computing the value of a polynomial .
@AdrianColomitchi Yes, this can be implemented as loop, but with recursion code may looks better and more understandable. We can almost guarantee that stack wouldn't be overflowed - memory for plain array will run out faster, so this is question more of personal preference than performance and safety.
@SemyonBurov - :D ah, yes, "everything is better with bluetooth" ;) Perforrmance-wise - for the small number of dimension this is likely to be used, maybe it won't shave much, but keeping into account that the "positioning in matrix" will be the most frequent operation, it may lead to a notable change in performance (I don't say "significant", just notable).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.