• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
Chad Smith

Array of Pointers

9 posts in this topic

I understand how pointers and arrays relate to each other though for some reason I am having a hard time grasping an array of pointers.

 

Basically lets say I have this code:

#include <iostream>

// preforms a selection sort on an array
void SelectionSort(int* arr[], int size);
// Shows the contents of the array passed in
void ShowArray(int* arr, int size);
// Show the contents of the sorted array
void ShowSortedArray(int* arr[], int size);

int main()
{
	int donations[5] = {5, 10, 1, 15, 7};
	// array of pointers
	int* sortedDonations[5];

	// before we sort, set it to the unsorted donations
	for(int i = 0; i<5; i++)
	{
		sortedDonations[i] = &donations[i];
	}

	SelectionSort(sortedDonations, 5);

	ShowArray(donations, 5);
	std::cout << "Sorted Donations: " <<std::endl;
	ShowSortedArray(sortedDonations, 5);

	return 0;
}

//preform a selection sort on the passed in array
void SelectionSort(int* arr[], int size)
{
	int startScan;
	int index;
	int minIndex;
	int* min;
	for(startScan = 0; startScan < size-1; startScan++)
	{
		min = arr[startScan];
		for(index = startScan+1; index<size; index++)
		{
			if(*arr[index] < *min)
			{
				min = arr[index];
				minIndex = index;
			}

		}
		arr[minIndex] = arr[startScan];
		arr[startScan] = min;
	}
}

// display an array
void ShowArray(int arr[], int size)
{
	for(int i = 0; i<size; i++)
	{
		std::cout << arr[i] << " ";
	}
	std::cout<<std::endl;
}

//Display an Array of pointers
void ShowSortedArray(int* arr[], int size)
{
	for(int i = 0; i<size; i++)
	{
		std::cout << *(arr[i]) << " ";
	}
	std::cout<<std::endl;
}

 

While I understand what is going on in this code I just don't understand why we must use an array of pointers here?

 

I understand that the code is running a selection sort on an array without messing with the original array.  Though why is it that I need to use an array of pointers?  What's actually going on there?  I understand the basics of why I guess though I don't think I could go in depth and if someone were to ask me why it used an array of pointers I wouldn't know what to say to them.

 

Thanks to all who can help...

0

Share this post


Link to post
Share on other sites

Working with pointers here is a more general version. For sorting integers you don't really need an array of pointers, but if you swap the integers with complex objects, it is more apparent why you should use pointers.

1

Share this post


Link to post
Share on other sites

The nutshell answer is, you use a collection of pointers to objects in the sort because it is substantially faster to move a pointer in many cases.  For example, if your object takes up say... 1000 bytes in memory, moving it will require copying 1000 bytes from one location to another, while copying the pointer involved only moving 4 or 8 bytes.  So instead of moving the actual data, you are simply moving the pointer to it.

 

 

As to why do you NEED to use an array of pointers, you don't.  In fact, you probably shouldnt be.  There are dozens of datatypes available to you that take care of the edge cases, memory management, etc... make use of them.

1

Share this post


Link to post
Share on other sites

To expand on Ashaman73's comment... maybe a (hopefully well commented) example will help you to see what happens when you sort the values directly vs sorting the pointers.

#include <iostream> // for std::cin
#include <string> // for std::string
#include <vector> // for std::vector
#include <algorithm> // for std::for_each, std::sort

// Lets make a more complicated donation. It has an amount and who donated it.
struct Donation {
  int         m_amount;
  std::string m_donor;

  // Constructor to make it easy to create these below.
  Donation(const std::string &donor, const int amount)
    : m_amount(amount), // this scary looking syntax is an initilizer list, it just sets the members of the struct.
      m_donor(donor) {
  }

  // This will trigger every time we have to copy a Donation. Let's pretend a copy here is super expensive
  // because people like to have 1,000,000 character names on average. We don't want to copy names.
  // It is an operator overload for 'operator =' and it called whenever you do something like:
  // Donation a("alice", 5), b("bob", 500);
  // a = b;
  // This function is usually auto-generated by the compiler, so you don't need to write it.
  // The only reason I did write it was to include the std::cout.
  Donation &operator =(const Donation &other) {
    m_amount = other.m_amount;
    m_donor = other.m_donor;
    std::cout << "did an expensive copy" << std::endl;
    return *this;
  }
};

// Used in the sorting function below to sort by the ammount.
// You could just as easily change this to sort by name.
struct CompareDonation {
  // Version used for values.
  bool operator()(const Donation &a, const Donation &b) const { return a.m_amount < b.m_amount; }
  // Version used for pointers.
  bool operator()(const Donation *a, const Donation *b) const { return a->m_amount < b->m_amount; }
};

// Used to output the donations to the screen.
struct PrintDonation {
  void operator()(const Donation &d) {
    std::cout << "Donation: " << d.m_amount << " from " << d.m_donor << std::endl;
  }
  void operator()(const Donation *d) {
    std::cout << "Donation: " << d->m_amount << " from " << d->m_donor << std::endl;
  }
};

int main() {
  std::cout << "Setup..." << std::endl;
  // The standard library has a nicer container than arrays. It's called std::vector.
  // A std::vector<> is a template that lets you shove data into it on the fly.
  // A 'std::vector<Donation> array;' is similar to a 'Donation array[10];' but with some nice
  // features.
  std::vector<Donation> donations;
  donations.push_back(Donation("bob", 5));
  donations.push_back(Donation("sally", 5000));
  donations.push_back(Donation("tim", 50));
  donations.push_back(Donation("alice", 500));

  // We're going to sort the values. So lets make a copy to sort.
  std::vector<Donation> sortedDonations = donations;

  // We're also going to sort the pointers like your example did.
  std::vector<Donation *> alsoSortedDonations;
  for (std::vector<Donation>::size_type i = 0; i < donations.size(); ++i) {
    alsoSortedDonations.push_back(&donations[i]);
  }

  std::cout << "Sorting by values. (1)" << std::endl;
  // The standard library also comes with a built-in sort function. But for complex objects
  // you have to explain how to sort them. I chose to do this with the CompareDonation class.

  // Note that this sort causes our objects to be copied around.
  std::sort(sortedDonations.begin(), sortedDonations.end(), CompareDonation());
  std::cout << "Sorting by pointers. (2)" << std::endl;
  // Note that this sort does not.
  std::sort(alsoSortedDonations.begin(), alsoSortedDonations.end(), CompareDonation());

  // Now we print out all 3 vectors to prove that the neither sort call affected the
  // original, and that both sorted collections are sorted.
  std::cout << "---------- O R I G I O N A L ----------" << std::endl;
  // The standard library also comes with a 'for each' construct when you want to run
  // the same function a all the objects of a container like std::vector<>
  std::for_each(donations.begin(), donations.end(), PrintDonation());
  std::cout << "---------- S O R T E D  1 ----------" << std::endl;
  std::for_each(sortedDonations.begin(), sortedDonations.end(), PrintDonation());
  std::cout << "---------- S O R T E D  2 ----------" << std::endl;
  std::for_each(alsoSortedDonations.begin(), alsoSortedDonations.end(), PrintDonation());
  std::cout << "Done. Hit enter." << std::endl;
  std::cin.get();
  return 0;
}

While I fully appreciate this example and know what is going on and know that I should be using the standard library really for this.  I would if it was actually a project I was developing and not just something for practice.  Though I did +1 for this example as I did enjoy reading the code and you taking the time to give a commented example

 

The example is just from a book I am going through again to refresh some of my understanding of some things.  So maybe I should rephrase my question.

 

Maybe the question isn't why, but maybe more like "what is an array of pointers?"  I know of all the other datatypes that should be used though the reason I am going through this to refresh my understanding is because in a class I am taking at the University we are not allowed to use the built in datatypes that are in the standard really.  We are studying the theory behind them really.  So I guess it should be what.  What is going on with the array of pointers?  I understand the selection sort and all that.  Though why did we use the array of pointers?  What's going on actually?  Is it just because it would be faster to move them instead of just coping all the information over?

 

Maybe rephrasing it like this.  Thanks for all the answers though everyone.  I like reading about anything.  Though I know of some of the other datatypes that I should be using if this was actually a real project.  It's just because it seems most universities want you to learn about the theory behind some datatypes so you know what datatype to use at a certain time to give you a better idea.

 

Thanks everyone.

Edited by Chad Smith
0

Share this post


Link to post
Share on other sites
The main reason is the expense of copying large objects rather than pointers, which doesn't apply in the case of sorting an array of ints.

The other advantage to using pointers is you can maintain several different "views" of the data (e.g. one sorted ascending, one descending, one sorted on a different field, etc.) while still keeping the original data untouched and in the original order.

EDIT: Obviously, modifying the source data invalidates any pointers you have to it. Edited by Paradigm Shifter
1

Share this post


Link to post
Share on other sites

Here's a commonly used occurrence of arrays of pointers:
 

int main(int argc, char *argv[]) //'argv' is an array of char pointers.
{
    for(int i = 0; i < argc; i++)
    {
        char *str = argv[i];
        std::cout << "String " << i << ": " << str << std::endl;
    }
    
    return 0;
}

You keep saying an "an array of pointers", and you keep on using an array of pointers syntax. However, your functions look like you are actually wanting a pointer to an array instead of an array of pointers.

In C++ an array is almost identical to a pointer, and you can convert an array to a pointer very easily and implicitly:

int array[] = {0, 1, 2, 3, 4, 5};
int *pointer = array;
 
void myFunc(int *pointer);
myFunc(array);
2

Share this post


Link to post
Share on other sites

Here's a commonly used occurrence of arrays of pointers:
 

int main(int argc, char *argv[]) //'argv' is an array of char pointers.
{
    for(int i = 0; i < argc; i++)
    {
        char *str = argv[i];
        std::cout << "String " << i << ": " << str << std::endl;
    }
    
    return 0;
}

You keep saying an "an array of pointers", and you keep on using an array of pointers syntax. However, your functions look like you are actually wanting a pointer to an array instead of an array of pointers.

In C++ an array is almost identical to a pointer, and you can convert an array to a pointer very easily and implicitly:

 

int array[] = {0, 1, 2, 3, 4, 5};
int *pointer = array;
 
void myFunc(int *pointer);
myFunc(array);

Thanks Servant.  I knew of the pointers and arrays and that you could easily convert them.  Isn't it when you want to pass an array to a function, the compiler translates it to a pointer?  For example:

void MyFunc(int array[]);

// compiler would translate this to be

void MyFunc(int* array);

// This seems to be what it does in Visual C++ when I look at it

I used a pointer of arrays because I wanted the original array/pointer to stay the same order and not be sorted.  Using just a pointer, though I could have easily "designed" it wrong, I figured it would modify both of the array and sorted pointer when I sorted them.  I just did a quick test and they both ended up being sorted.  Am I right in thinking that?  So by using the array of pointers it ended up not messing with the original data.  Am I right on this?

 

Also am I right in thinking, now that I think about it, that an array of pointers would be the same as a double pointer?

 

Example:

void MyFunc(int* foo[]);

// is the same as

void MyFunc(int** foo);

//Would that be right?  Now that I think about it, yes I assume since we have

int main(int argc, char* argv[])

// and also

int main(int argc, char** argv) 

On of those tricky things about C++, and this might not make immediate sense, but an array isn't really a datatype, like an int, char or int* is.

 

An array is just syntactic sugar for logically group like wise types together.  When you declare an array, you are actually just getting a chunk of memory sized to fit the contents.

 

So for example

 

int32 myArray[16];

 

Is really just pretty syntax over a buffer of continous memory 4x16bytes in length.

 

On the same accord

 

int bob = myArray[1];

 

Is just a pretty way of saying give me the data value sizeof(int32) bytes in, or in English, give me the next 4 bytes 4 bytes into the memory dedicated to myArray.

 

This is why you can use array syntax on a pointer, or pointer syntax on an array...  At the end of the day, an array isn't actually a variable, it's simply a .... label, that refers to a fixed size chunk of memory.

Thanks for this.  Though I did understand arrays  Though for some reason my mind was having hard time grasping what an array of pointers actually was.  Would it be safe though for me to just tell my self, whenever I see an array to think of a pointer or something?

 

I've used both arrays and pointers before.  Understood both of them when not using them "together" just fine.  Though when I started to use them "together" I just couldn't wrap my mind around it.

0

Share this post


Link to post
Share on other sites

Thanks for this.  Though I did understand arrays  Though for some reason my mind was having hard time grasping what an array of pointers actually was.  Would it be safe though for me to just tell my self, whenever I see an array to think of a pointer or something?

 

I've used both arrays and pointers before.  Understood both of them when not using them "together" just fine.  Though when I started to use them "together" I just couldn't wrap my mind around it.

 

Sort of, but that is slightly inaccurate but close enough.

 

 

For the most part though, the address ( & ) of an array is functionally equivalent of a pointer to that type.

 

I say "sort of", because an array is much less flexible.  You cant reallocate an array for example, or use it as a param to a function like you can with a pointer.

 

 

The closest equivalent to an array I can think of is a const pointer.

 

 

In simple terms, and in 95% of times though, yes, you can look at an array and pointer as the same thing.  And generally use the same syntax with each.

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0