Sign in to follow this  
ConorH

Dynamic Array Woes

Recommended Posts

Fairly new to C++ and want to make an Array that I can add new elements, take some away, rearrange the order and such. With some tutorials I have read, none seem to be able to explain how I do this though. I have an inkling that these are properties of another concept (vector, map?) Tar

Share this post


Link to post
Share on other sites
Quote:
Original post by ConorH
Fairly new to C++ and want to make an Array that I can add new elements, take some away, rearrange the order and such. With some tutorials I have read, none seem to be able to explain how I do this though. I have an inkling that these are properties of another concept (vector, map?)

Tar

Arrays are usually static in size - that is, once you create the array, it stays at the size that you created it. It is possible to flag items in the array as in-use or not, but technically, they are still there. You probably want to look into something called a linked list. A linked list will allow you to add and remove items in the list, as well as reorder them.

Share this post


Link to post
Share on other sites
Im using my vector/list to store SDL_Surface* but when I try and return the reference for it, it gives me an error


std::list<SDL_Surface*> im;

int cSprite::LoadImage(const char* _file)
{
//Add the loaded file onto vector list
im.push_back(Gfx.LoadImage(_file));
return im.end();
}

1>.\engine.cpp(111) : error C2440: 'return' : cannot convert from 'std::list<_Ty>::_Iterator<_Secure_validation>' to 'int'
1> with
1> [
1> _Ty=SDL_Surface *,
1> _Secure_validation=true
1> ]


I want to be able to get the reference from the function though :(
Any ideas? I can see that Im doing something wrong here
edit: I assume that references arent in the form of int's then. Im used to referencing array elements with ints/int literals from when I used DarkBasic

Share this post


Link to post
Share on other sites
Quote:
Original post by ConorH
std::list<SDL_Surface*> im;

int cSprite::LoadImage(const char* _file)
{
//Add the loaded file onto vector list
im.push_back(Gfx.LoadImage(_file));
return im.end();
}
Two problems are immediately evident here:

1. list::end() returns an iterator that points 'one past the end' of the list. It appears you want to access the last item added to the list; to do so, use list::back().

2. The function return type is int, but you're trying to return an SDL_Surface*.

I recommend fixing these errors and then re-posting your code (as there are some other areas where improvements could be made).

Share this post


Link to post
Share on other sites
If list::end()/back() returns an iterator for the last element, how come its returning the value of it (SDL_Surface*)?

Im trying to abstract the use of SDL_Surfaces, and just use image numbers for instance, so that's why I want to return the iterator

Share this post


Link to post
Share on other sites
Quote:
Original post by ConorH
If list::end()/back() returns an iterator for the last element, how come its returning the value of it (SDL_Surface*)?


list::end() returns an iterator that is after the last valid iterator. It doesn't have an associated value and should not be dereferenced. If the iterator is bidirectional (it is, for a list), you may decrement a copy of end() to reach the last element.

list::back() returns a reference to the last element: it's neither an iterator nor a value.

Either way, an iterator is not an integer, so a function which has an int return type should not and cannot return an iterator.

EDIT: an alternative:


// Use integers as identifiers. They are recycled.
template<typename T>
class IDMap
{
std::vector<T*> elements;
std::vector<int> free_indices;
public:
T& operator[](int i)
{
assert (i >= 0);
assert (i < elements.size());
assert (elements[i]);
return *elements[i];
}

int add(T& element)
{
if (free_indices.empty())
{
elements.push_back(&element);
return elements.size() - 1;
}

else
{
int index = free_indices.back();
free_indices.pop_back();
elements[index] = &element;
return index;
}
}

void remove(int index)
{
assert (i >= 0);
assert (i < elements.size());
assert (elements[i]);

elements[index] = 0;
free_indices.push_back(index);
}
};



This object is responsible for translating indices into object pointers and vice versa, and may be used as part of a greater system which only lets the indices be public.

Of course, wrapping the texture in an object would be a much better way of abstracting this.

Share this post


Link to post
Share on other sites
A reference is a C++ language construct. It works as an alias to an existing object, instead of creating a copy from it. Unlike pointers, references cannot be reseated, and there is no such thing as a null reference.

An iterator is a generalization of the pointer concept: each is tied to a value in a sequence, which may be read or modified through it. Iterators may also be incremented or decremented to reach the previous or next elements in the sequence.

To return an iterator, simply use the correct return type. In your case, std::list<SDL_Surface*>::iterator.

Share this post


Link to post
Share on other sites
Quote:
Original post by ConorH
K, confused now. 2 Questions,
What's the diffrence between reference and iterator?
and
How can I return an iterator?
You might check out this site, in particular this section.

An 'iterator' is a generic concept used through the containers and algorithms portion of the standard C++ library. In general, iterators behave somewhat like pointers, although they are not in fact pointers (well, they might be, but as far as the user is concerned they have their own type).

Like pointers, they can be incremented, decremented (in some cases), compared with each other, or dereferenced via the * or -> operators. If you're at all familiar with how to use pointers, you'll find iterator semantics to be similar.

In your example, you have a couple of choices: you could return the iterator corresponding with the newly added object (probably not a terribly good idea), or return a copy of or reference to the object itself.

A list is not a random-access container, so in this case returning an integer value is not terribly useful (you could use distance, advance and so on to emulate this sort of behavior, but that also is not a terribly good idea).

What you should probably do, for now, is have the function return an SDL_Surface*, and just return im.back().

Once you have a better understanding of pointers, iterators, and other aspects of the SC++L, you will most likely want to instead manage your surfaces using smart pointers. boost::shared_ptr offers support for custom deleters, so it can be used with C-style resources such as SDL_Surface.

Share this post


Link to post
Share on other sites
When I make std::list<SDL_Surface*>::iterator im; I cant use im.push_back(). So, to rephrase, how can I get an integer representation of how many elements are in the list, or do I have to keep count myself?

Sorry if Im not getting this, I've never encountered any of this so far but thanks for the help so far

Edit: Would vectors be better for this sort of thing then?

Share this post


Link to post
Share on other sites
Quote:
Original post by ConorH
When I make std::list<SDL_Surface*>::iterator im; I cant use im.push_back().
push_back() is a member function of list<>, not list<...>::iterator.
Quote:
So, to rephrase, how can I get an integer representation of how many elements are in the list, or do I have to keep count myself?
If you just want to know how many elements are in a list, you can use the size() member function. However, this function should be used with care, as it's not guaranteed to be constant time (not AFAIK, at least).

I gather that the broader issue here is resource management, and how to manage (in particular) objects of type SDL_Surface, pass them around, clean them up when you're through with them, and so on.

In terms of safety and correctness, the optimal way to handle this is probably via smart pointers. However, if you're not yet comfortable with the fundamentals of the language, it may not be immediately obvious how or why this should be done.

That's probably as specific as I can be without knowing more about what you're trying to do. If you need further help you might post your cSprite class in its entirety. Perhaps you could also explain what the purpose of the return value of LoadImage() is.

Share this post


Link to post
Share on other sites
a = (int *)malloc(SIZE_OF_ARRAY*sizeof(int))

and to do it for 2 or 3 dimensional arrays you'd just use a for loop or an embedded for loop.

it's actually not very difficult to dynamically allocate space for arrays.

Share this post


Link to post
Share on other sites
Quote:
Original post by sharpnova
a = (int *)malloc(SIZE_OF_ARRAY*sizeof(int))

and to do it for 2 or 3 dimensional arrays you'd just use a for loop or an embedded for loop.

it's actually not very difficult to dynamically allocate space for arrays.
You might give the thread another read. The topic is not memory management in C, but rather resource management and the use of containers and iterators in C++ (or at least that's what it's evolved into).

Share this post


Link to post
Share on other sites
You know, this would have been a *lot* easier if you had said what you wanted the int to *mean*. Yeah, just use .size() on the list.

Quote:
Original post by ConorH
When I make std::list<SDL_Surface*>::iterator im; I cant use im.push_back(). So, to rephrase, how can I get an integer representation of how many elements are in the list, or do I have to keep count myself?


Ok, we're going to begin at the beginning.

A std::list is a thing that will store your elements. It knows how many elements it contains, and keeps them in a particular order. You can ask how many elements there are by calling .size() on the list. It's templated: you can make a std::list<int> which stores ints, or a std::list<SDL_Surface*> which stores pointers to SDL_Surfaces, or basically anything else.

A reference is a language construct: it provides an alias for an existing "thing". So we can make a reference to an SDL_Surface* which is in the list, and that variable effectively becomes another name for that particular SDL_Surface*.

When you use .back() on a container (such as std::list), it gives you a reference to the last element in the container. That is, it gives you that element, not by copying it, but by aliasing it:


std::list<int> foo;

foo.push_back(42);

int& lastThingInList = foo.back();
lastThingInList = 23;
// Now '23' is stored in the list instead of '42', because the name
// 'lastThingInList' aliases the (single) value stored in the list.

int bar = lastThingInList; // the '23' gets assigned to 'bar' as well.
// Since 'bar' is not a reference, the value gets copied across.
bar = 42; // does not affect the list, because bar is not a reference.


Of course, there's nothing special about references to ints; we can just as easily make a reference to a pointer to an SDL_Surface:


std::list<SDL_Surface*> surfaces;

surfaces.push_back(SDL_loadImage(whatever));
SDL_Surface* s = surfaces.back();
// That's a copy of the pointer value; but the pointed-at surface is NOT copied.
SDL_Surface*& s2 = surfaces.back();
// That's a reference to the pointer value, i.e. an alias for it.
s2 = NULL; // now NULL is stored in the list, but 's' still points at the same
// surface, and the surface still exists.


An iterator is a concept created by the standard library - it is not built into the language itself. The idea is that in C++, because you can overload operators, it is possible to make a struct or class that "behaves like" a pointer, by giving it operators that correspond to the operations that are valid on pointers. Thus, pointers themselves are a kind of iterator, but not an especially powerful one.

A std::list<foo>::iterator is an iterator that is designed to "iterate over" the elements of a std::list. As you would expect, dereferencing it (as you would a pointer) gives you some element of the list, according to its current "position". Because it's possible to modify pointed-at things via a pointer, iterators in general support that as well. Therefore, the dereferencing operator is defined to return a reference. (That way, when you subsequently assign, you assign to the pointed-at thing, instead of a copy.) In order to make the list::iterator useful, "incrementing" or "decrementing" it causes it to "point to" the next or previous element of the list, correspondingly. This works even though that element could be anywhere else in memory - something a plain old pointer can't do (incrementing a plain old pointer would make it point at the next element-sized block of memory, and there could be ANYTHING there). It can do this because it's *not* a raw pointer, but an instance of a class that has some knowledge about the std::list's internal structure.

An "end" iterator is an iterator that "points one past the end" of a container. It may not be dereferenced, but it may at least be created and compared to. Oh, and it can be decremented (there's nowhere valid to increment it to). The reason for having such a thing is that the "distance" (number of times you'd have to increment/decrement to get from one to the other) between a "begin" iterator (one that "points to" the initial element) and the corresponding "end" iterator is equal to the number of elements. Standard library containers will give you a begin iterator to themselves if you ask with .begin(), and an end iterator if you ask with .end(). Because these are objects, they have some particular type. For standard library containers, the type name is simply 'iterator', but the class is nested within the container class: thus, a std::list<SDL_Surface*>::iterator is an iterator over a list of pointers to SDL_Surfaces, which is provided to you by the list of pointers to SDL_Surfaces so that you can iterate over it.

In a related way, you can loop ("iterate") over a container until you reach the end iterator, i.e. while your current iterator is not equal to the end iterator: e.g. "for (std::list<SDL_Surface*>::iterator it = mylist.begin(); it != mylist.end(); ++it)". This is actually quite similar to what beginning students are often taught to do with arrays:


int arr[SIZE];
for (int i = 0; i < SIZE; ++i) {
arr[i] = 0;
}


Of course, this "i" concept is a little messy; what we really want to do is set "each element of arr". So we want to get some kind of handle to "elements of arr". Well, the obvious thing would be to have a pointer... the first element is arr[0], but that's just equivalent to *arr. If we have some pointer that's initialized to arr, and keep incrementing it, then it will iteratively (hmm, key word :) ) point at each element of the array. Now, the first "element" that we *don't* want to access is arr[SIZE], since it doesn't actually exist. That is, we don't want to dereference our pointer when it equals &(arr[SIZE]), which you should know from more basic teaching is equal to just 'arr + SIZE'. So that gives us:


int arr[SIZE];
for (int* it = arr; it < arr + SIZE; ++it) {
*it = 0;
}


Hopefully you have the idea now. Arrays are the most primitive kind of container, and pointers are the natural iterator type for arrays, because they're the most primitive kind of iterator ;) All that's different is that we normally use '!=' to compare to an end iterator instead of '<', because there is actually no need for iterators to be "ordered" (even if the elements are). We only care if we reach the end; the idea that all the other positions have been "less than" the end is circumstantial.

(Of course, we don't need to write this loop most of the time, either, because the standard library also provides "algorithms" that do this kind of drudge work.)




That said, just to recap, we never have to count up the elements ourselves, because the list is also counting them for us. Just use .size().

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