Как перегрузить std :: удалить для std :: list?

Question

Когда-то я узнал, что общий способ стирания элементов из контейнера - это стирание-удаление-идиома. Но я был удивлен, узнав, что реализация STL по крайней мере g ++ не перегружает std :: remove() для std :: list, так как в этом случае многие назначения объектов могут быть сохранены путем выполнения переупорядочения с помощью манипуляции с указателем.

Есть ли причина, по которой стандарт C++ не предусматривает такую ​​оптимизацию? Но мой главный вопрос заключается в том, как я могу перегрузить std :: remove() (он не должен быть переносимым за пределы g ++), поэтому я мог бы предоставить реализацию, которая использует list :: splice()/list :: merge(). Я попробовал пару подписей, но получаю сообщение об ошибке неоднозначности в лучшем случае, например:

template <typename T> 
typename std::list<T>::iterator 
remove(typename std::list<T>::iterator first, 
     typename std::list<T>::iterator last, const T &v); 

P.S .: Мне очень жаль, что я не был достаточно ясен. Пожалуйста, проигнорируйте, что функции исходят из пространства имен std и того, что они делают конкретно. Я просто хочу узнать больше о правилах шаблона/typetraits/overload в C++.

Answer 1

list::remove10 или list::erase самостоятельно сделает то, что вы видели, удалить и удалить идиому для векторов.

remove для значений или предикатов. erase для одиночных итераторов или диапазонов.

Answer 2

Совет, который вы получили, является хорошим, но не универсальным. Это хорошо для std::vector, но совершенно необходимо для std::list, так как std::list::erase() и std::list::remove() уже поступают правильно. Они делают все волшебство указателя, которое вы запрашиваете, что-то std::vector::erase() не может сделать, потому что его внутреннее хранилище отличается. Именно по этой причине std::remove() не специализируется на std::list: потому что нет необходимости использовать его в этом случае.

Answer 3

Это не является обязательным, потому что это не только оптимизация, она имеет различную семантику от того, что вы ожидали бы для последовательности контейнера:

std::list<int> l; 
l.push_back(1); 
l.push_back(2); 

std::list<int>::iterator one = l.begin(); 
std::list<int>::iterator two = l.end(); --two; 

if (something) { 
    l.erase(remove(l.begin(), l.end(), 1), l.end()); 
    // one is still valid and *one == 2, two has been invalidated 
} else { 
    l.remove(1); 
    // two is still valid and *two == 2, one has been invalidated 
} 

Что касается фактического вопроса: ISWYM, я застрял на данный момент как написать пару шаблонов функций, чтобы они соответствовали произвольным итераторам и другим итераторам списка матчей без двусмысленности.

Имейте в виду, что в стандарте нет никакой гарантии, что list<T>::iterator - это другой тип от some_other_container<T>::iterator. Поэтому, хотя на практике вы ожидаете, что у каждого контейнера будет свой собственный итератор, в принципе подход ошибочен, кроме того, что вы предложили перегрузить его в std. Вы не можете использовать только итераторы для внесения «структурных» изменений в соответствующие контейнеры.

Вы можете сделать это без двусмысленности:

template <typename Container> 
void erase_all(Container &, const typename Container::value_type &); 

template <typename T> 
void erase_all(std::list<T> &, const T &);