Thread: Array trying to be a vector

  1. #1
    Registered User
    Join Date
    Sep 2004
    Posts
    153

    Exclamation 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 ->Chap
    Last edited by Chaplin27; 03-02-2005 at 08:55 PM. Reason: extra info

  2. #2
    Registered User
    Join Date
    Apr 2003
    Posts
    2,663
    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?

  3. #3
    Registered User
    Join Date
    Sep 2004
    Posts
    153
    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

  4. #4
    Registered User
    Join Date
    Apr 2003
    Posts
    2,663
    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?
    Last edited by 7stud; 03-02-2005 at 09:40 PM.

  5. #5
    Registered User
    Join Date
    Sep 2004
    Posts
    153
    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 )
    Last edited by Chaplin27; 03-02-2005 at 09:48 PM.

  6. #6
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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.

  7. #7
    Registered User
    Join Date
    Apr 2003
    Posts
    2,663
    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'.

  8. #8
    Registered User
    Join Date
    Sep 2004
    Posts
    153
    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

  9. #9
    Registered User
    Join Date
    Apr 2003
    Posts
    2,663
    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.
    Last edited by 7stud; 03-02-2005 at 10:44 PM.

  10. #10
    Registered User
    Join Date
    Sep 2004
    Posts
    153
    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!!

  11. #11
    Registered User
    Join Date
    Jan 2003
    Posts
    311
    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.

  12. #12
    Carnivore ('-'v) Hunter2's Avatar
    Join Date
    May 2002
    Posts
    2,879
    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!
    Last edited by Hunter2; 03-02-2005 at 10:32 PM.
    Just Google It. √

    (\ /)
    ( . .)
    c(")(") This is bunny. Copy and paste bunny into your signature to help him gain world domination.

  13. #13
    Registered User
    Join Date
    Sep 2004
    Posts
    153
    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!

  14. #14
    Carnivore ('-'v) Hunter2's Avatar
    Join Date
    May 2002
    Posts
    2,879
    >>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
    Just Google It. √

    (\ /)
    ( . .)
    c(")(") This is bunny. Copy and paste bunny into your signature to help him gain world domination.

  15. #15
    Registered User
    Join Date
    Sep 2004
    Posts
    153
    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):
    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
    //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...

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. converting a vector of strings into an array.
    By LightsOut06 in forum C++ Programming
    Replies: 2
    Last Post: 10-27-2005, 07:14 PM
  2. Type and nontype parameters w/overloading
    By Mr_LJ in forum C++ Programming
    Replies: 3
    Last Post: 01-02-2004, 01:01 AM
  3. Certain functions
    By Lurker in forum C++ Programming
    Replies: 3
    Last Post: 12-26-2003, 01:26 AM
  4. Operators for 3D Vector Mathematics
    By Anarchist in forum C++ Programming
    Replies: 10
    Last Post: 01-31-2003, 07:33 PM
  5. How can I convert a vector into an array??
    By shanedudddy2 in forum C++ Programming
    Replies: 6
    Last Post: 01-22-2003, 12:15 PM