new vs. vector vs. array

[Mark S.]

Hi,
even though I'm still at the beginning of my learning process, I am
anxious to program something "real". So I would like to write a little
program to solve Sudokus with variable dimensions (n*n). I think I have
a pretty good idea about the algorithm, but since you guys here strongly
suggested to avoid new & delete as much as possible, I was wondering how
you would suggest how I store the classes:

Basically, I think I need a class to store the dimensions of the field
which points to the n*m elements (with their own class). I thought I
would do something like this:

class Element {
public:
Element(int i = 0); // 0 means no number
// more variables to store status, etc.
}

class Field {
/* I don't know how to get any of these to work */
vector<Element> e || Element e[][] || Element* e // ???
public:
Field(int x = 1);
// functions to solve the Sudoku
};


The problem is that I don't know how to deal with multidimensional
vectors or arrays. I was thinking of using a single vector which is n*n
big. Of course, I would have to convert the numbers then (eg. for 3*3,
[1][1] would become [3]). Moreover, this solution does not seem very
elegant to me.

So, what would you recommend? An array of pointers to the elements? A
vector of pointers? Or a vector of the elements themselves?

Thank you in advance!
Mark


P.S.: I have used Google, of course, but I did not get any of these to work:

*[1]* Array (uses 'new' so maybe not recommended?):
This works in main():
const int n = 3;
int (*np)[n] = new int[n][n];
np[2][3] = 4;

However, I don't get it to work in my class (I know that the syntax is
wrong, but I don't know what the correct one is):
class Field {
const int n; // field dimensions
int x, y; // subsection dimensions
int (*fp)[];
public:
Field(int x = 1);
};

Field::Field(int i) : n(i) {
// { calculate subsection }
fp = new int[n][n];
}

*[2]* Vector:
I only know it's something like
vector< vector<Element> > f;
But I wouldn't even know how to push The elements to the right row, let
alone how to do this through a class.

 

[SG]

Hi,
even though I'm still at the beginning of my learning process, I am
anxious to program something "real". So I would like to write a little
program to solve Sudokus with variable dimensions (n*n). I think I have
a pretty good idea about the algorithm, but since you guys here strongly
suggested to avoid new & delete as much as possible, I was wondering how
you would suggest how I store the classes:

I'd probably build a class for managing a dynamic 2D array first.
Something like this

template<typename T>
class vector2d
{
std::vector<T> elements;
//...
public:
array2d(int rows, int cols, T const& fill = T());

int rows() const;
int cols() const;

T const& operator()(int r, int c) const;
T & operator()(int r, int c);
};

The problem is that I don't know how to deal with multidimensional
vectors or arrays. I was thinking of using a single vector which is n*n
big. Of course, I would have to convert the numbers then (eg. for 3*3,
[1][1] would become [3]). Moreover, this solution does not seem very
elegant to me.

Why not?

So, what would you recommend?
An array of pointers to the elements?

No. I would not recommend that. You'd need to explicitly provide a
destructor for cleaning up which also implies the need for user-
defined or explicitly disabled copy and assignment operations (see C++
"rule of three").

A vector of pointers?

No. I would not recommend that for the same reasons as above.


Cheers!
SG

 

[Mark S.]

I'd probably build a class for managing a dynamic 2D array first.
Something like this

template<typename T>
class vector2d
{
std::vector<T> elements;
//...
public:
array2d(int rows, int cols, T const& fill = T());

int rows() const;
int cols() const;

T const& operator()(int r, int c) const;
T & operator()(int r, int c);
};

Hmm, maybe it was too early for me to start this after all. I have not
learned what templates are yet and have no idea what it is you wrote.
Right now I'm at chapter 8 in TICPP (
http://www.linuxtopia.org/online_books/programming_books/thinking_in_c++/index.html
) and templates are discussed in chapter 16. Of course after your post I
read it anyways, though I still don't really understand what is going on
there. :-(
I assume that <typename T> means that T will be replaced (with int,
float, etc), eg. vector<T> becomes <vector<int>.
But I still can't make sense of the rest, in particular
array2d(int rows, int cols, T const& fill = T());
....
T const& operator()(int r, int c) const;
T & operator()(int r, int c);

And I also have no idea how I would actually put this to use. As I said,
maybe I'm not ready yet, though I had really hoped to make this work
with the knowledge I had so far.

The problem is that I don't know how to deal with multidimensional
vectors or arrays. I was thinking of using a single vector which is n*n
big. Of course, I would have to convert the numbers then (eg. for 3*3,
[1][1] would become [3]). Moreover, this solution does not seem very
elegant to me.

Why not?

Well, it means I have to spend a lot of extra time to calculate which
parts of the array I actually want to read/write. That sounds very
inefficient to me.

No. I would not recommend that. You'd need to explicitly provide a
destructor for cleaning up which also implies the need for user-
defined or explicitly disabled copy and assignment operations (see C++
"rule of three").


No. I would not recommend that for the same reasons as above.

Really? But I was told that vector is better than new/delete. I googled
"rule of three", but must say that I also don't understand what this has
to do with my example (even though the concept itself seems reasonable
and important in general).

 

[Lionel B]

On 24 Apr., 10:26, "Mark S." <[email protected]> wrote:

[...]

The problem is that I don't know how to deal with multidimensional
vectors or arrays. I was thinking of using a single vector which is
n*n big. Of course, I would have to convert the numbers then (eg. for
3*3, [1][1] would become [3]). Moreover, this solution does not seem
very elegant to me.

Why not?

Well, it means I have to spend a lot of extra time to calculate which
parts of the array I actually want to read/write. That sounds very
inefficient to me.

Actually, it's extremely efficient, easy for compilers to optimize and
very simple to implement (see Daniel T's post). In any case, you shouldn't
be worrying about efficiency at this stage (google "premature
optimization").

The chief alternative is a "vector of vectors" approach, which is probably
more fiddly to implement and unlikely to be more efficient.

 

[Mark S.]

On 24 Apr., 10:26, "Mark S." <[email protected]> wrote:

[...]

The problem is that I don't know how to deal with multidimensional
vectors or arrays. I was thinking of using a single vector which is
n*n big. Of course, I would have to convert the numbers then (eg. for
3*3, [1][1] would become [3]). Moreover, this solution does not seem
very elegant to me.
Why not?

Well, it means I have to spend a lot of extra time to calculate which
parts of the array I actually want to read/write. That sounds very
inefficient to me.

Actually, it's extremely efficient, easy for compilers to optimize and
very simple to implement (see Daniel T's post). In any case, you shouldn't
be worrying about efficiency at this stage (google "premature
optimization").

Alright, I'm convinced. But sadly I still don't know how to work these
templates, even though I get the feeling that's what OOP is all about.
I'll try a straight vector for now, but I think I was trying to avoid
what "premature optimization" is about (if I understood it correctly): I
wanted to have a multidimensional array so that I would have a clean
design (that I can address via xyz[a]) without the need to clutter
the source code with stuff about finding the right storage location.

 

[mzdude]

Hi,
even though I'm still at the beginning of my learning process, I am
anxious to program something "real". So I would like to write a little
program to solve Sudokus with variable dimensions (n*n). I think I have
a pretty good idea about the algorithm, but since you guys here strongly
suggested to avoid new & delete as much as possible, I was wondering how
you would suggest how I store the classes:

Basically, I think I need a class to store the dimensions of the field
which points to the n*m elements (with their own class). I thought I
would do something like this:

class Element {
public:
        Element(int i = 0);     // 0 means no number
        // more variables to store status, etc.

}

class Field {
        /* I don't know how to get any of these to work */
        vector<Element> e || Element e[][] || Element* e  // ???
public:
        Field(int x = 1);
        // functions to solve the Sudoku

};

The problem is that I don't know how to deal with multidimensional
vectors or arrays. I was thinking of using a single vector which is n*n
big. Of course, I would have to convert the numbers then (eg. for 3*3,
[1][1] would become [3]). Moreover, this solution does not seem very
elegant to me.

So, what would you recommend? An array of pointers to the elements? A
vector of pointers? Or a vector of the elements themselves?

Thank you in advance!
        Mark

P.S.: I have used Google, of course, but I did not get any of these to work:

*[1]* Array (uses 'new' so maybe not recommended?):
This works in main():
        const int n = 3;
        int (*np)[n] = new int[n][n];
        np[2][3] = 4;

However, I don't get it to work in my class (I know that the syntax is
wrong, but I don't know what the correct one is):
        class Field     {
                const int n;    // field dimensions
                int x, y;       // subsection dimensions
                int (*fp)[];
        public:
                Field(int x = 1);
        };

        Field::Field(int i) : n(i)      {
        //      {       calculate subsection    }
                fp = new int[n][n];
        }

*[2]* Vector:
I only know it's something like
        vector< vector<Element> > f;
But I wouldn't even know how to push The elements to the right row, let
alone how to do this through a class.

typedef std::vector<int> Columns;
typedef std::vector<Columns> Sodoku;
int main()
{
int n = 9;
int m = 4;
Sodoku s = Sodoku( n, Columns(m));

s[3][1] = 4;
}

 

[Lionel B]

SG wrote:
[...]

The problem is that I don't know how to deal with multidimensional
vectors or arrays. I was thinking of using a single vector which is
n*n big. Of course, I would have to convert the numbers then (eg.
for 3*3, [1][1] would become [3]). Moreover, this solution does not
seem very elegant to me.
Why not?
Well, it means I have to spend a lot of extra time to calculate which
parts of the array I actually want to read/write. That sounds very
inefficient to me.

Actually, it's extremely efficient, easy for compilers to optimize and
very simple to implement (see Daniel T's post). In any case, you
shouldn't be worrying about efficiency at this stage (google "premature
optimization").

Alright, I'm convinced. But sadly I still don't know how to work these
templates, even though I get the feeling that's what OOP is all about.

No, not really Templates have more to do with "generic programming".

I'll try a straight vector for now, but I think I was trying to avoid
what "premature optimization" is about (if I understood it correctly):

Premature optimization is about letting (quite likely unfounded)
optimization concerns influence/dictate your design. The "right" way to go
about things is to try to design your program logically around the problem
at hand. Then - and only then - consider whether efficiency is actually a
problem. If it is, *measure* to find out what is causing the inefficiency
and, if necessary, re-design to fix the problem. Frequently you will find
that there is no efficiency problem to worry about - and even if there is,
it's quite likely not caused by what you expected it to be. Human
programmers are remarkably bad at guessing where efficiency bottlenecks
are (partly because compilers can be rather clever).

I wanted to have a multidimensional array so that I would have a clean
design (that I can address via xyz[a])

Actually, using the single vector approach you will have a clean design
where you reference locations as xyz(a,b) (that's what the `operator()(int
row, int col)' lines are about).

without the need to clutter
the source code with stuff about finding the right storage location.

It's not clutter - it just does the business. And once written, you'll
never have to look at it again - it's tucked away in your matrix class. To
use your matrix class you simply use the public interface it exposes (such
as the subscripting operators).

 

[SG]

[...]

Hmm, maybe it was too early for me to start this after all. I have not
learned what templates are yet and have no idea what it is you wrote.

Ok, Another suggestion (see mzdude's post) was a vector of vector.
This should get you going.

Really? But I was told that vector is better than new/delete.

Right. Using a vector is fine. But in this case I would not use a
vector of *pointers*. What kind of pointers would that be? Pointers
you get from a new-expression? ;-)

I googled
"rule of three", but must say that I also don't understand what this has
to do with my example (even though the concept itself seems reasonable
and important in general).

If you don't provide your own copy constructor, assignment, etc. The
compiler will generate them for you where each member is copied. But
if you copy a vector of pointers it won't be a "deep" copy in the
sense that the pointees are copied as well. So, if you allocate arrays
via new, store pointers in a vector you need to do the cleaning up for
yourself in the destructir and provide a custom copy constructor and
custom assignment operator.

So, either use a vector<Element> and "emulate" a 2D array by
converting two coordinates to a single offset (see Daniel T's
implementation of the function call operator) or you can use a
vector<vector<Element> > instead.

Cheers!
SG

 

[peter koch]

SG wrote:

[...]

The problem is that I don't know how to deal with multidimensional
vectors or arrays. I was thinking of using a single vector which is
n*n big. Of course, I would have to convert the numbers then (eg. for
3*3, [1][1] would become [3]). Moreover, this solution does not seem
very elegant to me.
Why not?
Well, it means I have to spend a lot of extra time to calculate which
parts of the array I actually want to read/write. That sounds very
inefficient to me.

Actually, it's extremely efficient, easy for compilers to optimize and
very simple to implement (see Daniel T's post). In any case, you shouldn't
be worrying about efficiency at this stage (google "premature
optimization").

Alright, I'm convinced. But sadly I still don't know how to work these
templates, even though I get the feeling that's what OOP is all about.

No. Templates and OOP are orthogonal. Also, there is no reason that
you write a template class. Just write an ordinary class that can be a
matrix of some specific type - e.g. double. That class will likely be
a good basis for your coming templated class.

I'll try a straight vector for now, but I think I was trying to avoid
what "premature optimization" is about (if I understood it correctly): I
wanted to have a multidimensional array so that I would have a clean
design (that I can address via xyz[a]) without the need to clutter
the source code with stuff about finding the right storage location.

C++ only supports onedimensional arrays (and that support is rather
bad). Encapsulating your matrix in a class is the best way to removing
the clutter from your sourcecode - except in the one place where it is
relevant and thus not clutter.

/Peter

 

[James Kanze]

I'd probably build a class for managing a dynamic 2D array
first. Something like this

template<typename T>
class vector2d
{
std::vector<T> elements;
//...
public:
array2d(int rows, int cols, T const& fill = T());

int rows() const;
int cols() const;

T const& operator()(int r, int c) const;
T & operator()(int r, int c);
};

He doesn't really need a template for the moment. Since he's
still at the beginning of his learning process, a simple
implementation of Vector2dOfInt should suffice. (For that
matter, the preferred method of developing this sort of template
is first to get a non-template version working, then templatize
it.)

On the other hand, I'm wondering about his data representation
to begin with. My Sudoku solver didn't use any two dimensional
arrays of any sort.

The problem is that I don't know how to deal with
multidimensional vectors or arrays. I was thinking of using
a single vector which is n*n big. Of course, I would have to
convert the numbers then (eg. for 3*3, [1][1] would become
[3]). Moreover, this solution does not seem very elegant to
me.

Why not?

Again, I think he's gotten it backwards. Standard Sudoku
consists of a set of 81 squares. Each square is in three
different subsets. The traditional layout speaks of rows,
columns and I don't know what they call the third, but that's
really irrelevant with regards to solving the problem.

 

[James Kanze]

[...]

The problem is that I don't know how to deal with
multidimensional vectors or arrays. I was thinking of
using a single vector which is n*n big. Of course, I would
have to convert the numbers then (eg. for 3*3, [1][1]
would become [3]). Moreover, this solution does not seem
very elegant to me.
Why not?

Well, it means I have to spend a lot of extra time to
calculate which parts of the array I actually want to
read/write. That sounds very inefficient to me.

Actually, it's extremely efficient, easy for compilers to
optimize and very simple to implement (see Daniel T's post).
In any case, you shouldn't be worrying about efficiency at
this stage (google "premature optimization").

Especially since the data set is extremely small, so performance
is unlikely to be an issue.

The chief alternative is a "vector of vectors" approach, which
is probably more fiddly to implement and unlikely to be more
efficient.

On most modern machines, an indirection is more expensive than a
multiplication. If the data set was bigger, locality issues
would also argue against the vector of pointers.

Of course, if he really does want a vector of two dimensions,
the simplest solution is:

std::vector< std::vector< int > >
v( n, std::vector< int >( n ) ) ;

Under the hood, that's basically the vector of pointers
solution, at least with regards to performance, but it's a lot
easier to program than any of the alternatives, and the
difference in performance shouldn't matter unless he's thinking
in terms of a 1000x1000 Sudoku.

 

[James Kanze]

C++ supports arbitrarily dimensioned arrays. Multidimensional
array support is built into the core language, as in C.

Technically, no. C and C++ (and Pascal, and I suspect most
other modern languages) only have arrays of one dimension. The
elements of those arrays, however, can be an arbitrary type,
including an array type. And an array of an array is so close
to an array of two dimensions that it's generally considered not
worth the added complexity of introducing the additional
dimensions.

This is also untrue. Arrays have much more powerful semantics
in C++ than in most other languages; e.g., they support
pointer arithmetic, and their sizes are automatically
available as compile-time constants.

Pointer arithmetic is a serious defect, not a quality. And most
other languages make the size available, without requiring it to
be a compile time constant. And they continue to make it
available when the array is passed to a function. In addition,
in most other languages, arrays are first class object types,
not a hack: like every other object type, they support copy and
assignment, for example.

Raw C++ arrays impose absolutely minimal run-time overhead, so
they do not offer some features that are popular in other
languages; e.g., C++ arrays do not typically know their own
sizes at run-time, so index operations are not bounds-checked.

Whether index operations are bounds-checked or not is up to the
implementation. There have been implementations where they were
bounds checked. On the other hand, C style arrays are broken
enough to make bounds checking inordinately expensive, rather
than the very, very low cost is has in other languages.