Array trying to be a vector

So I'm reading along, typing out code and just doing my thing, I then come across this baffling piece of code...now I was curious why the author didn't just use a vector b/c iterators make the word go round as far as I'm concerned (later on he did, so he won back my interest)...so rather he used this array system to remove the an observer object from a list of observers... now this is accomplished by the else if where if the address of the current iteration in the list is equal to the observer that called the function (I didnt print that part of the code, a this pointer is entered as RemoveObservers lone argument), then it is "removed" by simply overwriting that object with the next object in the list's address..what I'm not getting though is won't this leave a gap in your array? Here's the code:

Just a quick edit: m_Count is the size of the array of Observer objects called mp_List

Code:

---

void Subject::RemoveObserver(Observer* Item)
{
        int i;
        bool found = false;
        for (i = 0; i < m_Count; i++)
        {
                if (found)
                {}
                else if (mp_List[i] == Item)
                {
                        found = true;
                        mp_List[i] = mp_List[i+1];
                }
        }
        if (found)
                m_Count--;
}

---

If this does what I think it does and you have 5 objects in the array, and you are trying to remove the 3rd object, won't that end up leaving you with the 3rd and fourth being the same item? Sure, decrementing m_Count decreases the size of the array, but if you're not overwriting the second to last element, you're going to have duplicates...does this sound right? Any insight, any at ALL would be fantastic...this is driving me crazy hehe :eek: ->Chap

Quote:

---

Sure, decrementing m_Count decreases the size of the array, but if you're not overwriting the second to last element, you're going to have duplicates...does this sound right?

---

Who cares if you never look past m_Count?

Quote:

---

Originally Posted by 7stud

Who cares if you never look past m_Count?

---

the value of m_Count isn't affecting my scenario:
you have a five member array named mp_List, we'll say they are of type Dog, Cat, Monkey, Bird, Zebra so:
mp_List[m_Count] looks like this
mp_List[0] = Dog
mp_List[1] = Cat
mp_List[2] = Monkey <-remove this, set equal to next element
mp_List[3] = Bird
mp_List[4] = Zebra <- Lop off last element

So I'm thinking the update will look like this
mp_List[0] = Dog
mp_List[1] = Cat
mp_List[2] = Bird
mp_List[3] = Bird

is this wrong...that is my question...no offense, but a simple sentence with no further explanation does not a good reply make. Thanks for the fast response at least! ;) -Chap

Quote:

---

the value of m_Count isn't affecting my scenario:

---

Well, you posted this:

Code:

---

for (i = 0; i < m_Count; i++)

---

When the code does this:

mp_List[i] = mp_List[i+1]

if the elements are different class types, there has to be an operator equals function defined for the different types. After all, what does it mean to say that two different class types with different member variables are equal? For instance, if you have this setup:

Bird
wingspan = 10;
beak_color = "red";
weight = 4;

Cat
num_legs = 3;
eyes = "brown";
height = 10;

what does Bird = Cat mean?

wow...you're totally right...so I gave a bad example...the array is of the same type but different instances
So it should actually look like this:
mp_List[0] = Observer object(Dog derived class)
mp_List[1] = Observer object(Cat derived class)
mp_List[2] = Observer object(Bird derved class)
mp_List[3] = Observer object(Monkey derived class)
mp_List[4] = Observer object(Zebra derived class)

First off we're talking about an array to pointers...
Second, I did try this out myself and I worked with the last item of the array (which would mean i+1 would be an invalid section...but it worked fine!! WHich surprised me and caused to me to post :D)

As far as I can tell its an error and yes there will be duplicates in the array unless by some miracle its the second to last item thats being deleted. Not to mention that if the value is in the last index, then mp_List[i+1] is an out of bounds error.

My question though is, why don't you just test it yourself? If it doesn't work then you'll know you're right.

Quote:

---

SO what I'm basically asking is if the way I'm imagining what's happening to the data, ACTUALLY happening to the data?

---

Are you really having trouble understanding what happens in this setup:

mp_List[m_Count] looks like this
mp_List[0] = Dog
mp_List[1] = Cat
mp_List[2] = Monkey <-remove this, set equal to next element
mp_List[3] = Bird
mp_List[4] = Zebra <- Lop off last element

and supposing (mp_List[i] == Item) when i is 2, so the result is this:

mp_List[2] = mp_List[3];

That seems pretty straight forward, although I don't see any 'removing' or 'lopping off'.

the lopping off occurs when m_Count is decremented by one thus cutting the array from 5 to 4 elements
And removal was a poorm choice of words on my part...the element is being replaced

Quote:

---

m_Count is decremented by one thus cutting the array from 5 to 4 elements

---

That does sound like a problem if mCount starts at 5 elements, and the Item is found at element 0. When you copy element 1 to element 0, and mCount goes to 4, then there will be duplicates in the first 4 elements of the list.

well there wont be duplicates because of if(found) because when the element is found and "replaced" it sets found = true, then when the for loop iterates again (assuming it has to) it will skip the whole else if statementand exit the loop, decrement m_Count and leave the function...what I'm now curious about is how it overwrites the last element without crashing the program...we must band together and destroy this problem!! :)

My guess would be that what was wanted was to swap, rather than assign, and to do so so long as found was true. This would bubble the found item down to the end, preserving order. If you had an array or vector of vectors or strings this is not even that bad of an idea as swap tipically has nothrow, simple constant overhead. These are pointers, so there is little point.

Code:

---

void Subject::RemoveObserver(Observer* Item) {
    const Observer *end = mp_list+m_Count;
    for (Observer *i = mp_List; i != end;++i)  {
        if(*i == Item) {
            --m_Count;
            while(++i != end) std::swap(*(i-1),*i);
        }
    }
}

---

As to the bounds error, remember that accessing beyond the bounds is not an error, it's undefined, undefined's worse.

Where are you getting this code from? It looks like it's very poorly written.

Code:

---

if (found)
{}

---

Jeez, what's the point of this. If you want the loop to quit when the element is found, then either use break or else put found as part of the loop condition. As it is, it will almost guaranteed waste tons of time looping unnecessarily after an element has been found.

Code:

---

mp_List[i] = mp_List[i+1];

---

You are correct in your analysis of what happens. I believe the intent of this code was really to shift all following elements forward one position (so as not to leave a 'gap' when one element is erased), but this only shifts one element forward. This should be a loop:

Code:

---

for(; i < m_Count - 1; ++i)  //Technically shouldn't have m_Count - 1 as loop condition, should be pre-calculated for max efficiency.
{
  mp_List[i] = mp_List[i + 1];
}

---

Now, for:

Code:

---

if (found)
        m_Count--;

---

This separate test is completely unnecessary. It could be placed inside the loop, where found is set to true.

Also, since these are pointers, it makes me suspect (although you'll have to verify) that they point to dynamic memory; if they do, then simply erasing the pointers will give you a memory leak. You'd need to delete each pointer manually before doing the shuffling forward of all following elements.

So, a much improved version of the code would be:

Code:

---

void Subject::RemoveObserver(Observer* Item)
{
        for (int i = 0; i < m_Count; ++i)
        {
                if (mp_List[i] == Item)
                {
                        //Decrement right now, so we don't have to do it later.
                        //Also, so we don't have (m_Count - 1) as a loop condition.
                        --m_Count;

                        //Keep shifting the next element forward, until the (new) end.
                        //Uncomment this line if it's dynamic memory that you're responsible for freeing
                        //delete mp_List[i];
                        for(; i < m_Count; ++i)
                                mp_List[i] = mp_List[i+1];
                }
        }
}

---

Hope this helps!

ok hunter...THANK YOU!!! You're getting a rep boost for understanding exactly what I was asking and answering my question! Haha you're the *expletive deleted*!! woohoo...ok now, this code is in a C++ book I'm reading, and what's interesting (to me) is that I'm far enough in my learning that I noticed the exact same problems that you did in the code and questioned why the author would do such pointless things...this is obviously a better task for a vector which was meant for the dynamic element shifting that this program so desperately needs. I'm kinda scared that not even half way through the book I can already spot glaring optimization and syntax issues...thanks hunter!

>>this code is in a C++ book I'm reading
Out of curiosity, what book is it?

>>I'm kinda scared that not even half way through the book I can already spot glaring optimization and syntax issues...
Rather, you should be glad that you can spot them ;)

it's C++ for dummies 7 books in one version...now up until this point I really have been enjoying the book. I mean, it's still an awesome book and it's really thorough, but I wonder if the author made his programs sorta ugly in order to allow the reader to develop a good eye for little issues. Although, that could just be uselessly defending busted code hehe. oh but anyways, on to more pressing issues...Hunter some of your comments before were really insightful (well all of them, but a couple in particular helped me out a lot...) such as (drum roll please):

Quote:

---

I believe the intent of this code was really to shift all following elements forward one position (so as not to leave a 'gap' when one element is erased), but this only shifts one element forward.

---

and also the comment in the code of

Quote:

---

//Uncomment this line if it's dynamic memory that you're responsible for freeing
//delete mp_List[i];

---

OK...SO...this brings me into what I was trying to get to the bottom of...if you have an array of pointers, using pointer arithmetic, if you do to the array of pointers what we've been talking about doing...does the replacement then change the order of elements...meaning (I really like these diagrams hehe, it all started with the UML and it's spiraling out of control ;)):
element[0] = p_observer1
element[1] = p_observer2
element[2] = p_observer3<-replace this with next element
element[3] = p_observer4
element[4] = p_observer5<-m_Count decremented by uno

does the new version look like this?:
element[0] = p_observer1
element[1] = p_observer2
element[2] = p_observer4
element[3] = p_observer5

I'm still toying with the code on this one so I'll come around to answering that eventually...although I would like some official analysis to work alongside with while I mess with the code (thus part of the beauty of these forums...I can't really ask the author for some help...well not without the restraining order that will inevitably follow my calling or emailing him nonstop muwahaha)
Thanks a lot Hunter and everyone else for the healthy and helpful dialogue...-Chap

Sorry for the long response...:(

one last thing...

Code:

---

for(; i < m_Count; ++i)
        mp_List[i] = mp_List[i+1];

---

I was under the impression that writing a for loop out like this was sloppy...clearly I'm in no position to even say ANYTHING about syntax or whatnot...it's helpful for me to know these kinds of things :) why not just use a while loop? Although, as we both are quite aware of, the for loop is the sexiest of all loops ;) hahaha

Oh hunter, one last thing, isn't i out of its scope in the nested for loop you provided in the updated code because it's defined in the first for loop as opposed to at the start of the function where it would be in scope throughout? Or is it within scope as long as it's inside the for loop where i is declared? If I'm bombarding you with questions...tell me so and I'll ask them in a whisper so you won't even know they're there :p

>>does the new version look like this?:
Assuming all elements are shifted forward properly, that's generally how it will look. However, as has been mentioned by grib, if you don't care about preserving the order of the elements (i.e. the array is just acting as a big collection of unsorted items), then it is more efficient to simply swap the element you're 'removing' with the last element, and then decrease the element count. That way the element you want deleted is removed from its position and moved to the 'back', where it will be safely ignored due to the decreased element count, and the element at the 'back' will be moved into the position vacated by the element you just removed so it will still be 'inside' the array.

>>I was under the impression that writing a for loop out like this was sloppy
Quite possibly. I think it's more a matter of style though (oooh, that 's' word!); when I see 'for', I think "this is going to loop for (the condition) number of times", but when I see 'while', I think "This is going to loop until for some reason (the condition) is false". Therefore, in this case, I used a 'for' because the loop should execute (from the current position to the end of the array) times. Also, when a for loop is of the form:

Code:

---

for(; condition; ++i)

---

This, to me, is usually a clear indication that the loop is picking up where another has left off - in this case, it is continuing to the end of the array from where the outer loop has 'paused'. Admittedly, this isn't totally clear since it's continuing the outer loop from the inside; it would likely be more intuitive if the if statement checking for equality simply did break; and the nested loop were placed outside. Either way, however, the effect would be pretty much the same.

Quote:

---

isn't i out of its scope in the nested for loop you provided in the updated code because it's defined in the first for loop as opposed to at the start of the function where it would be in scope throughout? Or is it within scope as long as it's inside the for loop where i is declared?

---

In very simplistic terms, an object is in scope as long as the innermost {} block it was defined inside is still open - literally. You can, in fact, do:

Code:

---

int main()
{
  int i = 5;
  std::cout << i;

  {
      int j = 1;  //j temporarily brought into scope
      std::cout << j;
  }

  //j now out of scope

  return 0;
}

---

Of course, it's a *little* different in for loops:

Code:

---

//i is not in scope
for(int i = 0; i < 5; ++i)  //i is in scope
{
  //i is in scope
}
//i is not in scope

---

As you can see, the variiable declared in () acts as if it were declared inside the {}. Similarly:

Code:

---

//i is out of scope
for(int i = 0; i < 5; ++i)  //i is in scope
  std::cout << i;  //i is in scope
//i is out of scope

---

So basically, i is in scope as long as the code block it was declared in is still open. Since the code block in this example is a single line, i is in scope for that single line.

**EDIT**
Oops. Well, to answer the question :D:
i is still in scope because, as you guessed, the code block it was defined inside of (the outer for loop) hasn't ended yet.

awesome hunter....if I could boost your rep again I would! haha your info has been beyond helpful. It should also be noted that this has been the longest thread I've started which I thought was kinda cool...I look forward to more posts and responses from you. Take it easy-Chap