Friday, December 24, 2010

Append integer to string (c++)

In this blog article we'll be using operator overloading with strings to let us append integers to the end of them (something pretty useful which std::string doesn't do for us already! :/)

We will be using some code described in a previous article to do the actual conversion from int to string.

We will be overloading the "<<" operator so that we can append to a string, and we will use the "+" operator so that we return a copy of the result of appending a string.

So it will work as follows:

int main() {
string str0("hello");
string str1("hello");

cout << str0 << endl; // prints 'hello'
str0 << 123;
cout << str0 << endl; // prints 'hello123'

cout << str1 << endl; // prints 'hello'
str1 + 123; // does not modify str1 (effectively does nothing)
cout << str1 << endl; // prints 'hello'
cout << str1 + 123 << endl; // prints 'hello123'
return 0;
}


Note: The reason we're overloading '<<' instead of '+=', is because '+=' is not an operator that allows for global operator overloading. See this link for more details on that.

So how do we make the above code work?
We need to add the following above the 'main()' function:

template<typename T>
string toString(T t) {
stringstream s;
s << t;
return s.str();
}

string& operator<<(string& s, int i) {
return s.append(toString(i));
}

string operator+(string s, int i) {
return s.append(toString(i));
}


Using the above overloads, the code in the main() function compiles and prints what we wanted it to.

Notice that the '<<' operator overload takes a reference to a string as one of its parameters, this is done so that the actual string is modified. The '+' operator overload takes a copy of the string and then does the appending, so the original string is not modified.

We can extend the above code to work for floats, doubles, and any datatype that our toString() function accepts. One way we do that is to use templates on our operator overloads.

Here's the new code:

template<typename T>
string& operator<<(string& s, T i) {
return s.append(toString(i));
}

template<typename T>
string operator+(string s, T i) {
return s.append(toString(i));
}


Although the above code works and is cool, there is a downside to doing this.
It won't allow us to do stuff like: string("s") + "hello", anymore. If we try to do that the compiler will generate a ambiguity error because it doesn't know which overload to choose. The +(string, char) overload is already defined by standard strings and our above template operator overload also handles this case; so the compiler doesn't know which to use and generates an error.

Our solution then is to not use templates and just manually overload the operators for the specific types on the + operator, but to use templates for the << operator since the c++ standard doesn't overload the <<(string, char) operator.
This is the code I currently use in my projects:

template<typename T>
string& operator<<(string& s, T i) {
return s.append(toString(i));
}
string operator+(string s, int i) {
return s.append(toString(i));
}
string operator+(string s, float i) {
return s.append(toString(i));
}
string operator+(string s, double i) {
return s.append(toString(i));
}


So there you have it, you can now do stuff like:

double myDouble = 123.79;
string s("My double is ");
s << myDouble << ". My int is " << 12 << ".";
cout << s << endl; // prints 'My double is 123.79. My int is 12.'

// this prints the same thing as above but uses
// printf() and C-style strings (null-terminated char arrays)
printf("%s", s.c_str());

Returning Arrays by Reference in C++

Last article we talked about returning arrays, but we only did it by value (so that a copy of the data is returned). This time we'll look at returning arrays using references.

This feature is something that I rarely see used in practice, I think partially because the syntax is so bizarre and confusing to those that have never seen it. I first saw it in some code by shuffle2 and thought it was crazy; but now I understand why the syntax is the way it is.

Here's how to do it:

int testArr[5] = { 1000, 1, 2, 3, 4 };

int (&retArr())[5] {
return testArr;
}

int main() {
int (&arr)[5] = retArr();
cout << arr[0] << endl; // prints 1000
return 0;
}


The 'retArr()' is the function which is returning a reference to an int array with 5 elements. If you wanted any parameters for the function 'retArr()' you can place them in the '()' like you normally would.

The seemingly awkward syntax becomes less awkward when you think of the syntax for declaring references to an array.
'int (&arr)[5] = ...' is how you would declare a normal reference to an array, so studying that syntax and then looking at the function prototype 'int (&retArr())[5]' should help you understand it.

Also why is returning a reference to an array useful?
Well its useful for various reasons, but I'll give an interesting example.

Assume that you have a memory buffer that was dynamically allocated (for w/e reason, maybe a custom allocation routine to guarantee alignment), then you want that buffer to be thought of as a fixed-size array; well you can do that by returning a reference to an array.

Like so:

struct myStruct {
int* myPtr;
myStruct() {
myPtr = new int[5];
myPtr[0] = 1000;
myPtr[1] = 1;
myPtr[2] = 2;
myPtr[3] = 3;
myPtr[4] = 4;
}
~myStruct() {
delete[] myPtr;
}
int (&getArray())[5] {
return (int(&)[5])*myPtr; // cast to a reference
}
};

int main() {
myStruct testStruct;
cout << testStruct.getArray()[0] << endl; // prints 1000
cout << sizeof(testStruct.getArray()) << endl; // prints 20
return 0;
}


The benefit of returning an array by reference instead of just an int pointer in the above code is that the former explicitly tells the programmer reading the function signature that the buffer being returned holds 5 ints, returning an int pointer instead will not tell us how much elements are in the array.
Also sizeof(testStruct.getArray()) returns 5*sizeof(int), whereas if we were returning an int pointer, it would just return sizeof(int*), which most-likely isn't what we wanted.

Sunday, December 19, 2010

Returning arrays in C++ (including multi-dimensional arrays)

Last article we were talking about passing arrays as arguments and it got a bit long, so this time I'm going to try to keep it shorter.

First I'll say that like when we passed an array by value in the last article, there is no built in easy way to return arrays by value, so we have to use workarounds.

The first thing I'll show is some WRONG CODE that beginners might try to use:

int* getArray() {
int my_arr[10] = { 0,1,2,3,4,5,6,7,8,9 };
return my_arr;
}

int main() {
int* arr = getArray();
arr[1] = 4;
for(int i = 0; i < 10; i++) {
cout << arr[i] << endl;
}
return 0;
}


Can you see the error?
Well the problem is that in the function getArray() the array 'my_arr' is being allocated on the stack, and then you are returning a pointer to it. By the time you're back in the function main() 'my_arr' is not guaranteed to be valid anymore so using it as if its valid will cause undefined behavior. So don't do this.

Now lets look at some correct ways to do this.
One way is to use dynamic memory allocation to allocate the array on the heap and then pass a pointer to it, and then consider that memory as an array.

It looks like this (also note that I'm going to use a multi-dimensional array so people know how to do this):


const int n = 5;
const int m = 5;

int* getArray() {
int* arr = new int[n*m];
for(int i = 0; i < n*m; i++) arr[i] = i;
return arr;
}

int main() {
int* ptr = getArray();
int (&arr)[n][m] = (int(&)[n][m])*ptr;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
cout << arr[i][j] << endl;
}}
delete[] ptr;
return 0;
}


In the function getArray() we allocate a chunk of memory the size of n*m*sizeof(int) bytes. Then we initialize it to the numbers 0...n*m-1, then we return it as an int*.
Back in the function main() we get the ptr and then consider it as a multi-dimensional array by using references. Here you can see how to cast a pointer to an array (for single-dimensional arrays just ignore the extra [m] part).
Lastly we need to remember to delete[] the ptr, because we allocated this memory on the heap so it won't automatically delete it for us.


Since the above method has us needing to delete[] our memory ourselves, it is slightly inconvenient. This last approach doesn't have that problem, we use a struct like we did when we passed arrays as arguments in the last article.

const int n = 5;
const int m = 5;

struct arrayStruct {
int arr[n][m];
};

arrayStruct getArray() {
arrayStruct t;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
t.arr[i][j] = i*m + j;
}}
return t;
}

int main() {
arrayStruct a = getArray();
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
cout << a.arr[i][j] << endl;
}}
return 0;
}


When we use a struct to encapsulate the array, c++ creates a default copy constructor that will copy our data created in getArray() to our 'a' struct in main().

If we didn't want to access the array by using 'a.arr[i][j]', we could again use references like so:

int main() {
arrayStruct a = getArray();
int (&arr)[n][m] = a.arr;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
cout << arr[i][j] << endl;
}}
return 0;
}


We have now seen a couple ways to do this, there are more ways to accomplish this task but this blog post would get huge if I continue listing the various ways.

Saturday, December 4, 2010

Passing Arrays as Arguments in C++

In C++ and other programming languages there is the concept of Arrays.
One of the things you might want to do with arrays is pass them to another function so that that function can read the data in the array.

The simplest thing you might think of to accomplish this task might be:

void foo(char* a) {
cout << a[0] << endl; // prints 0
cout << sizeof(a) << endl; // prints 4
}

int main() {
char my_array[128] = {0};
foo(my_array);
return 0;
}


And this does work. What its doing here is passing the pointer to first element in 'my_array' to the function 'foo', and 'foo' uses it as a normal char*.


The problem with this approach is if you want to specify that you want an array of a certain size as the parameter to the function. Since we're treating the array as a pointer, there is no hint to the programmer of the size needed for the array.

There is a feature that originated in C which lets us specify a size parameter, and it looks like this:

void foo(char a[128]) {
cout << a[0] << endl; // prints 0
cout << sizeof(a) << endl; // prints 4
}

int main() {
char my_array[128] = {0};
foo(my_array);
return 0;
}


Now this method is pretty evil in C++ (although in C I guess its more justifiable since it doesn't support the better way which i will explain later).

Now in the function 'foo' you are hinting to the programmer that you want an array with 128 elements, but guess what happens if you give it an array of 10 elements?
Nothing happens, its perfectly fine accepting that.

What happens if you pass it char* instead of an array of char?
Nothing happens, its perfectly fine accepting that.

Also notice what this function prints out. It prints out '4' for sizeof(a)!?

Any experienced coder will know that sizeof(some_array) will be the size of one element times the number of elements. So why is it giving us '4' instead of '128'?

Well it turns out that this feature is equivalent to the first method we used, that is it is as if we're passing a "char*", not an array by reference (as we may have thought).

So once we realize that, it all makes sense, sizeof(char*) on a 32bit system is '4', so that's how we got that number.

For these reasons this approach is what I would call 'evil'. You would expect it to behave a certain way, but it doesn't.

There is a special form of the above C-feature that looks like this:

void foo(char a[]) {
cout << a[0] << endl; // prints 0
cout << sizeof(a) << endl; // prints 4
}

int main() {
char my_array[128] = {0};
foo(my_array);
return 0;
}


This time in the function 'foo' we didn't specify a size of the array.
I don't think there's any reason to use this form as opposed to 'char* a' since they both behave the exact same way. And this time you're not even hinting to the programmer how big you want the array, so its kind-of pointless to have this notation.
'char a[]' might look cool though compared to just using 'char* a', so maybe that's why someone might want to use it. Although i would just recommend using 'char* a' since its more commonly seen (and therefor easier to read imo).


Now that we learned all these bad ways to pass arrays in C++, lets look at a good way.
Passing an array by reference! (Before we were just using different forms of passing a char*, but this time we will pass the array by reference and the compiler will understand that it is array).

It looks like this:

void foo(char (&a)[128]) {
cout << a[0] << endl; // prints 0
cout << sizeof(a) << endl; // prints 128
}

int main() {
char my_array[128] = {0};
foo(my_array);
return 0;
}


Aha! Finally the sizeof(a) is printing out 128 (what we expected it to).
Now 'a' is behaving like an array instead of 'char*' and that is what we wanted.

Now guess what happens if we try to pass an array of 10 elements to function 'foo'?
We get a compiler error! The compiler knows that an array of 10 elements is not an array of 128 elements, so it gives us an error.

Now guess what happens if we try to pass a char* to the function 'foo'?
We get a compiler error! The compiler knows that a char* is not the same as an array of 128 elements, so it gives use an error.

The compiler errors are useful in order to prevent bugs by people who mistakenly are passing arrays of incorrect size to the function.
In another article I will explain ways to circumvent such compiler errors when you 'know' for sure that the pointer/array you're passing is suitable for the function 'foo' but may not have the same type (such as an array of 1000 elements, whereas the function foo will only accept an array of 128 elements).



We have learned how to pass arrays using pointers and references (which means that any data of the array 'a' that was modified in function 'foo' modifies the data in 'my_array'), now we will learn how to pass an array by value (which means that a copy of the array data will be transferred via the stack to function 'foo', so that modifications to 'a' will not effect 'my_array').

Now here's the funny part about this, you can't do it! At least there's no fancy parameter declaration that lets you do this.

There are various workarounds for this problem, and one of them is to create a struct which will act as the array, and then pass the array as that struct on the stack.

For example:

struct temp_struct {
char a[128];
};
C_ASSERT(sizeof(temp_struct)==sizeof(char)*128);

void foo(temp_struct t) {
char (&a)[128] = t.a; // reference to the array t.a
cout << a[0] << endl; // prints 0
cout << sizeof(a) << endl; // prints 128
}

int main() {
char my_array[128] = {0};
foo((temp_struct&)my_array);
return 0;
}


Notice what we did here. We created a struct 'temp_struct' which holds only a single array of the size we're passing. (I will explain what the C_ASSERT does in a bit).
Then we made foo() take as a parameter the 'temp_struct' that we defined earlier.

In the first line of foo's body, we create a reference to the first element inside the foo struct. Then we use this array reference like normally.

Back in the function main(), we need to typecase my_array as a reference of type temp_struct. Basically what we're saying to the compiler is that this array should be treated as if it were a temp_struct, without doing any conversion of the data.
Now the last thing is, since the compiler thinks my_array is a temp_struct, it will copy over the array on the stack (like it would do for any other struct that was passed by value). So with that we have completed our goal.

C_ASSERT is a compile-time assert, and is useful for things like making sure structs you've declared are the size you expected them to be.
The C_ASSERT in the above example is added just to make sure the compiler is generating the struct the same exact size as the array we're dealing with.
If the compiler didn't make the struct the same size, then we would get a compiler error.
I think that a compiler will never end up breaking that C_ASSERT. But I don't know the full c++ standard well enough to guarantee that will never happen, so that's why I add the check in the first place.

Anyways hopefully this article was informative, and by now you should know how to pass an array by treating it as pointer, pass an array by reference, and pass an array by value.

Thursday, December 2, 2010

Simple Tic Tac Toe Game (c++)

I've seen a bunch of random people learning programming starting out with Tic Tac Toe games. It is an interesting challenge for beginners and I think its probably a great first-challenge to try once you think you're getting the hang of the language basics.

I myself had never made a Tic Tac Toe game, but after seeing so much beginners having trouble with it, and seeing their code filled with un-necessary "bloat", I decided to try making a lean C++ console based tic tac toe game.

The goal was to make a functional Tic Tac Toe game without the hundreds of lines other people's code usually takes.

In my head I was thinking it might even be possible to do in as few as 30 lines, but that was a bit too optimistic for me in practice.
Although if I didn't handle bad-cases, and didn't format the output nicely, I could probably do that; but the quality of a program should not be sacrificed for "less lines" of code, so I decided to handle all the bad-cases and such I'm aware of (which in turn increased the amount of code the program needed).

Anyways here's the full code:

#include <conio.h>
#include <iostream>
using namespace std;

void ticTacToe() {
char w = 0, b[9] = { '1','2','3','4','5','6','7','8','9' };
char player[][9] = { "Player O", "Player X" };
unsigned int slot = 0, turn = 1, moves = 0;
for(;;) {
system("cls");
cout << "Tic Tac Toe!" << endl << endl;
cout << " " << b[0] << "|" << b[1] << "|" << b[2] << endl << " -+-+-" << endl;
cout << " " << b[3] << "|" << b[4] << "|" << b[5] << endl << " -+-+-" << endl;
cout << " " << b[6] << "|" << b[7] << "|" << b[8] << endl << endl;
if (w || (++moves > 9)) {
if (w) cout << player[w=='X'] << " is the winner!!!" << endl << endl << endl;
else cout << "No Winner!!!" << endl << endl << endl;
cin.clear(); cin.ignore(~0u>>1, '\n'); _getch();
return;
}
cout << player[turn^=1] << " Choose a Slot... ";
cin >> slot;
if (slot < 1 || slot > 9 || b[slot-1] > '9') {
cout << "Please Choose A Valid Slot!!!" << endl;
cin.clear(); cin.ignore(~0u>>1, '\n'); _getch();
turn^=1; moves--;
continue;
}
b[slot-1] = turn ? 'X' : 'O';
((((b[0]==b[1]&&b[0]==b[2]&&(w=b[0])) || (b[3]==b[4]&&b[3]==b[5]&&(w=b[3]))
|| (b[6]==b[7]&&b[6]==b[8]&&(w=b[6])))||((b[0]==b[3]&&b[0]==b[6]&&(w=b[0]))
|| (b[1]==b[4]&&b[1]==b[7]&&(w=b[1])) || (b[2]==b[5]&&b[2]==b[8]&&(w=b[2])))
||((b[0]==b[4]&&b[0]==b[8]&&(w=b[0])) || (b[2]==b[4]&&b[2]==b[6]&&(w=b[2])))));
}
}

int main() {
for(;;) ticTacToe();
return 0;
}


The whole program ended up being 40 lines of code, which since it handles bad-cases, probably isn't that bad.

I would like to point out how few If statements or Switch Statements are needed for a tic tac toe game as seen above.
I usually see tic tac toe code examples filled with If/Switch statements that simply aren't necessary and make the code a lot bigger.

If you dislike the code above then I somewhat agree that the code could be prettier. Since the goal was to keep the amount of code to a minimum, it limited me in my code cleanliness.

If you notice, in my coding style there are times where I group more than one statement on the same line of code.
This is my personal preference when it comes to short statements that go hand-in-hand with each other. There are some programmers that don't like this style of mine, and I respect that, but I like code that is structured pretty, and grouping similar short statements allows me to accomplish nicer looking code IMO.

I kind-of lied with the title of this blog post though. Although this program is 'simple' in terms of 'little code', it isn't very 'simple' in terms of the ability for someone that isn't experienced with c++ to understand.
I used some tricks which newer c++ programmers may have trouble with; and if you do wish to understand or ask about part of the code above don't hesitate to leave a comment.