some operations present only for list<T>

[subramanian100in]

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

Kindly clarify.

Thanks
V.Subramanian

 

[Triple-DES]

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

The algorithms in <algorithm> operate 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]

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]

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<typename T>
void sort(typename std::list<T>::iterator first, typename
std::list<T>::iterator 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.

 

[James Kanze]

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

Because the algorithms don't take containers, only iterators.
Once you've only got begin and end, you're stuck; you can't get
back to the container. (Note too that the iterators I pass to
std::sort may not cover the entire container.)

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?

Same problem.