some operations present only for list<T>

[subramanian100in@yahoo.com, India]

There are some operations like sort, remove, remove_if which are
available as list<Tmember functions; but vector<T>, deque<Tdo not
seem have those functions. If am correct in this, what is the reason
for that. Moreover sort, remove, remove_if are available in
<algorithmals o. Then why does list<Thave these member operations ?

Kindly clarify.

Thanks
V.Subramanian

[Triple-DES]

Re: some operations present only for list&lt;T&gt;

On 6 Feb, 09:30, "subramanian10. ..@yahoo.com, India"
<subramanian10. ..@yahoo.comwro te:

There are some operations like sort, remove, remove_if which are
available as list<Tmember functions; but vector<T>, deque<Tdo not
seem have those functions. If am correct in this, what is the reason
for that. Moreover sort, remove, remove_if are available in
<algorithmals o. Then why does list<Thave these member operations ?
>

The algorithms in <algorithmopera te on ranges, not containers.
Therefore, an algorithm like std::remove_if will not actually remove
any elements, just copy the elements not removed to the front of the
range, and return a new end iterator.

The member functions of list naturally operate on the list itself.
Therefore list<T>::remove and list<T>::remove _if will actually erase
the elements from the list.

In general using the member functions where present will be faster,
and they often do slightly different things.

As for std::sort, this algorithm requires random access iterators,
while list only has bidirectional iterators. Therefore it needs its
own sort function.

[Phil Endecott]

Re: some operations present only for list&lt;T&gt;

Triple-DES wrote:

On 6 Feb, 09:30, "subramanian10. ..@yahoo.com, India"
<subramanian10. ..@yahoo.comwro te:

>There are some operations like sort, remove, remove_if which are
>available as list<Tmember functions; but vector<T>, deque<Tdo not
>seem have those functions. If am correct in this, what is the reason
>for that. Moreover sort, remove, remove_if are available in
><algorithmalso . Then why does list<Thave these member operations ?

As for std::sort, this algorithm requires random access iterators,
while list only has bidirectional iterators. Therefore it needs its
own sort function.

Does anyone know why this is not done with a specialisation of the sort
algorithm?

The same applies to find, i.e.

map m;
vector v;

m.find(...); // O(log N)
find(v.begin(), v.end(),...); // O(N)
find(m.begin(), m.end(),...); // O(N)
// but could be O(log N) if specialised?


Phil.

[Triple-DES]

Re: some operations present only for list&lt;T&gt;

On 6 Feb, 12:23, Phil Endecott <spam_from_usen et_0...@chezphi l.org>
wrote:

Triple-DES wrote:

On 6 Feb, 09:30, "subramanian10. ..@yahoo.com, India"
<subramanian10. ..@yahoo.comwro te:

There are some operations like sort, remove, remove_if which are
available as list<Tmember functions; but vector<T>, deque<Tdo not
seem have those functions. If am correct in this, what is the reason
for that. Moreover sort, remove, remove_if are available in
<algorithmals o. Then why does list<Thave these member operations ?

As for std::sort, this algorithm requires random access iterators,
while list only has bidirectional iterators. Therefore it needs its
own sort function.

>
Does anyone know why this is not done with a specialisation of the sort
algorithm?

It may not be impossible to do it, but I for one can't think of a good
way to implement it. The naive approach

template<typena me T>
void sort(typename std::list<T>::i terator first, typename
std::list<T>::i terator last)

doesn't work because the nested type can not be deduced (14.8.2.4/4).
Obtaining the actual container from just the two iterators could also
be a problem.