Jump to content

  • Log In with Google      Sign In   
  • Create Account

Array of Pointers


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
9 replies to this topic

#1 Chad Smith   Members   -  Reputation: 1144

Like
0Likes
Like

Posted 01 February 2013 - 12:05 AM

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...



Sponsor:

#2 Ashaman73   Crossbones+   -  Reputation: 7992

Like
1Likes
Like

Posted 01 February 2013 - 12:39 AM

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.



#3 KulSeran   Members   -  Reputation: 2586

Like
3Likes
Like

Posted 01 February 2013 - 04:15 AM

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;
}


#4 Serapth   Crossbones+   -  Reputation: 5760

Like
1Likes
Like

Posted 01 February 2013 - 09:39 AM

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.



#5 Chad Smith   Members   -  Reputation: 1144

Like
0Likes
Like

Posted 01 February 2013 - 12:31 PM

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, 01 February 2013 - 12:32 PM.


#6 Paradigm Shifter   Crossbones+   -  Reputation: 5436

Like
1Likes
Like

Posted 01 February 2013 - 12:42 PM

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, 01 February 2013 - 12:44 PM.

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

#7 Servant of the Lord   Crossbones+   -  Reputation: 21068

Like
2Likes
Like

Posted 01 February 2013 - 01:12 PM

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);

It's perfectly fine to abbreviate my username to 'Servant' rather than copy+pasting it all the time.
All glory be to the Man at the right hand... On David's throne the King will reign, and the Government will rest upon His shoulders. All the earth will see the salvation of God.
Of Stranger Flames - [indie turn-based rpg set in a para-historical French colony] | Indie RPG development journal

[Fly with me on Twitter] [Google+] [My broken website]

[Need web hosting? I personally like A Small Orange]


#8 Serapth   Crossbones+   -  Reputation: 5760

Like
3Likes
Like

Posted 01 February 2013 - 04:56 PM

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.


Edited by Serapth, 01 February 2013 - 04:59 PM.


#9 Chad Smith   Members   -  Reputation: 1144

Like
0Likes
Like

Posted 01 February 2013 - 07:42 PM

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.



#10 Serapth   Crossbones+   -  Reputation: 5760

Like
0Likes
Like

Posted 01 February 2013 - 08:06 PM

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.






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS