Michiel Salters wrote:

[...]
> Providing unique as you describe it on non-sortable ranges is quite hard;

I don't think so:

template<class ForwardIterator>
 void complete_unique(ForwardIterator begin, ForwardIterator end)
{
  while (begin != end)
  {
    typename iterator_traits<ForwardIterator>::value_type
      value = *begin;
    ++begin;
    end = remove(begin, end, value);
  }
}

> you'd probably need O(n*n) operations (since you must test element N
> against element 1..N-1).

Yes. remove is O(N), and the loop is O(N) as well.

> Besides, sorting std::lists can't be done in
> less then O(n*n) IIRC, so that's another reason why unique is probably
> better as it is now.

That's obviously wrong:

- copy into a vector: O(N)
- sort the vector: O(N log N)
- copy back into list: O(N)

This list-sorting algorithm has O(N log N) complexity.
Of course, you might not like the memory overhead ;-)

[...]

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

At the risk of sounding really dense .....

I have been following the other thread on the behavior of unique, and
from what I have been reading, it would seem that unique will only work
on a sorted container.

i.e. if i had a vector like 1 3 1 and called unique, i may not get 13
but if i sort the vector to get 1 1 3 then i will get 1 3 after the call
to unique.

Is my understanding correct ? If so, that seems like a really confusing
and weird behavior ....

Nick

--
Nick Ambrose
Senior Software Engineer
Ixia Communications, Inc.
<mailto:nick@ixia.com>
(818) 871-1800 x160

http://www.ixia.com

Ixia...
     When the test really counts.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Niklas Mellin wrote:

> In article <387E1282.34B082AD@ixia.com>,
>   Nick Ambrose <nick@ixia.com> wrote:
> > At the risk of sounding really dense .....
> >
> > I have been following the other thread on the behavior of unique, and
> > from what I have been reading, it would seem that unique will only
> > work on a sorted container.
>
> No such requirement at all, the only requirement on the range is
> that all "equal" (what ever that means) elements are stored next
> to each other.
>
> The exact wording of 25.2.8/1 is:
> "Effects: Eliminates all but the first element from every
> consecutive group of equal elements..."
>
> Of course sorting a container will put "equal" elements in
> "consecutive groups".
>

Hmm, OK, I get it now. It seems a little nasty (especially the wording in the
documentation for my particular compiler) that unique works that way.
Personally, if i called unique on the range 1 3 1 1 1 , i would certainly
expect to get 1 3, not 1 3 1. I can't really imagine ever wanting the current
behavior.
This also means it's very hard to make unique ranges out of objects that are
not sortable.

Nick

--
Nick Ambrose
Senior Software Engineer
Ixia Communications, Inc.
<mailto:nick@ixia.com>
(818) 871-1800 x160

http://www.ixia.com

Ixia...
     When the test really counts.



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Nick Ambrose wrote:
>
> At the risk of sounding really dense .....
>
> I have been following the other thread on the behavior of unique, and
> from what I have been reading, it would seem that unique will only work
> on a sorted container.
>
> i.e. if i had a vector like 1 3 1 and called unique, i may not get 13
> but if i sort the vector to get 1 1 3 then i will get 1 3 after the call
> to unique.
>
> Is my understanding correct ? If so, that seems like a really confusing
> and weird behavior ....

That's not correct. First of all, it takes an iterator range, not a
container. That range could be a subset of a container, or for that
matter a portion of an array.
Secondly, the elements of the range don't have to be sorted; unique<>
just has different consequences if the range isn't sorted. unique<>
removes consecutive duplicates, but not those which aren't consecutive.
It will convert 1 1 3 1 1 2 2 2 4 to 1 3 1 2 4; if that's what you want,
you don't have to sort it. If you want 1 2 3 4 as output, you'll have to
sort the range first. If you want 4 3 2 1 as output, you'll have to
reverse-sort it.
I've seen situations where I'd have wanted to use unique<> on non-sorted
data (though I didn't have access to STL at the time, so I couldn't
have).

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <387E1282.34B082AD@ixia.com>,
  Nick Ambrose <nick@ixia.com> wrote:
> At the risk of sounding really dense .....
>
> I have been following the other thread on the behavior of unique, and
> from what I have been reading, it would seem that unique will only
> work on a sorted container.

No such requirement at all, the only requirement on the range is
that all "equal" (what ever that means) elements are stored next
to each other.

The exact wording of 25.2.8/1 is:
"Effects: Eliminates all but the first element from every
consecutive group of equal elements..."

Of course sorting a container will put "equal" elements in
"consecutive groups".

/Niklas Mellin



Sent via Deja.com http://www.deja.com/
Before you buy.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Nick Ambrose wrote:

> >   Nick Ambrose <nick@ixia.com> wrote:

> > > I have been following the other thread on the behavior of unique, and
> > > from what I have been reading, it would seem that unique will only
> > > work on a sorted container.

[ Explanation snipped

> Hmm, OK, I get it now. It seems a little nasty (especially the wording in the
> documentation for my particular compiler) that unique works that way.
> Personally, if i called unique on the range 1 3 1 1 1 , i would certainly
> expect to get 1 3, not 1 3 1. I can't really imagine ever wanting the current
> behavior. This also means it's very hard to make unique ranges out
> of objects that are not sortable.

> Nick

Providing unique as you describe it on non-sortable ranges is quite hard;
you'd probably need O(n*n) operations (since you must test element N
against element 1..N-1). Besides, sorting std::lists can't be done in
less then O(n*n) IIRC, so that's another reason why unique is probably
better as it is now. But yes, if you must create a set without duplicate
elements, and the elements can't be sorted you'll have to write the
O(n*n) loop yourself.

Michiel Salters

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]