[STL Unique] what are the duplicated elements?


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 3 of 3

Thread: [STL Unique] what are the duplicated elements?

  1. #1
    Join Date
    Oct 2005
    Posts
    173

    [STL Unique] regarding the duplicated elements

    Question on what happens to the extra elements that are found to be duplicates. Specifically, the last sentence in the following paragraph.

    http://www.sgi.com/tech/stl/unique.html
    Every time a consecutive group of duplicate elements appears in the range [first, last), the algorithm unique removes all but the first element. That is, unique returns an iterator new_last such that the range [first, new_last) contains no two consecutive elements that are duplicates. [1] The iterators in the range [new_last, last) are all still dereferenceable, but the elements that they point to are unspecified.
    So it's dereferenceable but you get garbage for those elements?

    in SGI's example, they created new iterator.
    vector<int>::iterator new_end = unique(V.begin(), V.end());

    what if I reused the end() iterator?
    V.end() = unique(V.begin(), V.end());

    is this causing memory leak from the new end() to the old end()?

    Let's say there are 10 total elements and 5 are duplicates. So according to the SGI description, the size() will still be 10 after unique. What's the preferred way to get the right size? do you always have to involve an extra erase command after unique?
    Last edited by rssmps; 12-26-2005 at 06:40 AM.

  2. #2
    Join Date
    Nov 2003
    Posts
    4,118
    unique rearranges the container, pushing duplicates past the new logical end, but not erasing them. it returns an iterator that marks the new logical end of the container, i.e., the first non-unique element (which is one position past the last unique element). so if you have the following sequence:
    1,2,3,2,5
    the rerranged container after calling unique is:
    1,2,3,5,[2]
    the new_end points to the fifth element (instead of the sixth, as in the origianl container. remmeber that end() always returns one past the last valid element)

    The iterators aren't strictly invalidated because the container doesn't reallocate or shrink. However, the values to which the iterators point might change, so if for instance *it was 5, it could now be 2. The values of the dereferenced iterators are unspecified because you can't tell how the duplicates (i.e., the elements at new_end and higher) are ordered. So if you access such an iterator, your code will not crash but the value is unknown, or at least not portably known.
    This implies that in order to remove the duplciates you have to call erase (new_end, end) and if you want to release the memory occupied by these elements you have to use the self-swapping idiom described here:
    http://www.devx.com/cplus/10MinuteSolution/29484
    Last edited by Danny; 12-26-2005 at 05:08 PM.
    Danny Kalev

  3. #3
    Join Date
    Oct 2005
    Posts
    173
    OK, I get it.
    The swap is a neat trick!

    Thanks!
    Last edited by rssmps; 12-27-2005 at 03:51 AM.

Similar Threads

  1. Replies: 1
    Last Post: 10-31-2005, 03:04 PM
  2. Netscape Form Elements Inside DIV's
    By J.C. Tierney in forum Enterprise
    Replies: 0
    Last Post: 01-14-2002, 08:32 AM
  3. Replies: 5
    Last Post: 08-03-2001, 02:06 PM
  4. accessing textfield elements in a array
    By dominic in forum Java
    Replies: 2
    Last Post: 04-30-2001, 03:27 AM
  5. xml attributes vs. elements
    By monife in forum XML
    Replies: 1
    Last Post: 01-30-2001, 01:47 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center