Fill a C++ bidimensional array of objects

Question

I'm having a simple issue with std :: fill.

First I define a 2-dimensions array of pairs.

const int NMAX = 13;                                                             
typedef pair<int, set<int>> solution;                                            
solution memo[NMAX][NMAX];

I assume that at that stage my array is initialized with default pair constructor. Then, I would like to initialize this array without relying on a nested loop. What I am doing is this:

solution s;                                                                  
s.first = -1;                                                                                                 
std::fill( &memo[0][0], &memo[0][0] + sizeof(memo), s);

But I get a bus error... What am I doing wrong?

_`solution memo[NMAX][NMAX];`_ why not `vector> memo;` instead? Also `array,MAX> memo;` should be fine. — πάντα ῥεῖ, Mar 19 '15 at 14:26
`sizeof` is not the number of elements, but the number of chars (bytes). — Ulrich Eckhardt, Mar 19 '15 at 14:26
@πάνταῥεῖ Not the same. The data in the vector of vectors is not contiguous. — juanchopanza, Mar 19 '15 at 14:35
@juanchopanza what ? vector provide contiguous memory location. — Félix Cantournet, Mar 19 '15 at 15:29
@FélixCantournet: we are talking about `vector>` which have several non-contiguous buffers of contiguous `T`s. — Jarod42, Mar 19 '15 at 15:32
@Jarod42 yes ok. the top-level vector only garantees that the vector objects are contiguous which you don't really care about. Damn you indirection ! — Félix Cantournet, Mar 19 '15 at 15:35

score 2 · Accepted Answer · answered Mar 19 '15 at 14:26

2

Your end pointer is wrong, you mean:

std::fill(&memo[0][0], &memo[0][0] + sizeof(memo) / sizeof (solution), s);

as sizeof(memo) is NMAX * NMAX * sizeof (solution).

answered Mar 19 '15 at 14:26

Jarod42

203,559
14
181
302

I'm pretty sure there's something about this being UB, because it accesses the outer array out of bounds. See http://stackoverflow.com/questions/7269099/may-i-treat-a-2d-array-as-a-contiguous-1d-array – juanchopanza Mar 19 '15 at 14:38
Technically this is UB; it is doing the same as `memo[0][NMAX] = s; memo[0][NMAX+1] = s;` etc. – M.M Mar 19 '15 at 14:39
@juanchopanza The relevant section in the standard is not clearly worded. It's not clear whether "an element of the array object" can be an `int` in this case. If you say "No it can't" then many commonly accepted techniques become illegal (e.g. iterating over `memo` with a `char *`). My interpretation is that it's legal to use an `int *` to iterate over the array, so long as you form it with `(int *)&memo` or `(int *)&memo[0]`, so that "the array object" unambiguously means `memo`, and not a sub-object of `memo`. – M.M Mar 19 '15 at 14:44
@MattMcNabb That used to be my interpretation (that it is OK) and then I got convinced otherwise. Now I'm not sure anymore. IIRC there was a defect report about this, but I don't know what happened with that. – juanchopanza Mar 19 '15 at 14:53
@juanchopanza re. the DRs, I don't think anyone on the committee wants to touch it :) – M.M Mar 19 '15 at 20:20

score 1 · Answer 2 · edited May 23 '17 at 12:30

Actually we can do all of this a lot easier with std::vector:

typedef pair<int, set<int>> solution; 
solution s;                                                                  
s.first = -1;
std::vector<std::vector<solution>> memo(NMAX, std::vector<solution>(NMAX, s));

Live Demo

Unless you have some restriction against using a std::vector, it's going to be much easier to work with rather than doing a bunch of pointer math.

Edit: It's not the worst idea to use std::array either, like πάντα ῥεῖ suggested. You can avoid writing the internal loop to perform the fill yourself with a std::for_each as follows:

std::array<std::array<solution, NMAX>, NMAX> memo;
solution s;                                                                  
s.first = -1;
std::for_each(std::begin(memo), std::end(memo), [&s](std::array<solution,NMAX>& next){next.fill(s);})

Demo 2

Edit 2: If you're really masochistic and want to compute [row][column] indices yourself, then you can use a single std::array<solution, NMAX*NMAX> and take advantage of std::begin() and std::end() to call std::fill:

std::array<solution, NMAX*NMAX> memo;
solution s;                                                                  
s.first = -1;
std::fill(std::begin(memo),std::end(memo), s);

Demo 3

Fill a C++ bidimensional array of objects

2 Answers2