Идиоматический способ дешево удалить элемент из произвольного контейнера?

Question

Все контейнеры стандартной библиотеки C++ имеют insert() Способ; пока они не все имеют remove() метод, который не принимает никаких аргументов, но выполняет самое дешевое удаление в произвольном порядке. Теперь, конечно, это будет действовать по-разному для разных контейнеров: в векторе, который мы удалили бы сзади, в списке с одним списком, который мы удалили бы спереди (если мы не сохранили указатель на хвост), и так далее, к деталям реализации.

Итак, есть ли более идиоматический способ сделать это, кроме использования собственной специализации шаблона для каждого контейнера?

Answer 1

Частью конструкции стандартных контейнеров является то, что они ТОЛЬКО предоставляют операции в качестве функций-членов, если возможно обеспечить тот, который является оптимальным (по выбранным мерам) для этого контейнера.

Если контейнер предоставляет функцию-член, то есть потому, что существует какой-то способ реализации этой функции, который является оптимальным для этого контейнера.

Если невозможно обеспечить оптимальную реализацию операции (например, remove()) тогда это не предусмотрено.

Только std::list и (C++11 и более поздние версии) std::forward_list предназначены для эффективного удаления элементов, поэтому они являются единственными контейнерами с remove() функция-член.

Другие контейнеры не предназначены для эффективного удаления произвольных элементов;

• std::array не может быть изменен, поэтому нет смысла иметь insert() ИЛИ remove() функция-член.
• std::deque оптимизирован только для удаления в начале или в конце.
• Удаление элемента из std::vector менее эффективен, чем другие контейнеры, кроме (возможно) с конца.

Реализация remove() Поэтому функция-член для этих контейнеров противоречит философии дизайна.

Поэтому, если вы хотите иметь возможность эффективно удалять элементы из контейнера, вам нужно выбрать подходящий контейнер для работы.

Свернуть свою собственную оболочку для стандартных контейнеров, чтобы эмулировать операции, которые не поддерживаются некоторыми контейнерами, просто вводит в заблуждение - в смысле поощрения пользователей ваших классов-упаковщиков полагать, что они не должны быть осторожны с выбором контейнера, если у них есть особые требования к производительности или использованию памяти.

Answer 2

Итак, чтобы ответить на ваш вопрос

"Итак, есть ли более идиоматический способ сделать это, кроме как развернуть мою собственную специализацию шаблонов для каждого контейнера?

Есть много способов сделать удаление

1. Контейнер последовательности и неупорядоченный контейнер erase() возвращает следующий итератор после стертого элемента.

2. Erase () ассоциативного контейнера ничего не возвращает.

/ * * Удалить из вектора или Deque * /

 vector<int> vec = {1, 4, 1, 1, 1, 12, 18, 16}; // To remove all '1'
  for (vector<int>::iterator itr = vec.begin(); itr != vec.end(); ++itr) {
     if ( *itr == 1 ) {
        vec.erase(itr);
     }
  }   // vec: { 4, 12, 18, 16}
  // Complexity: O(n*m)

  remove(vec.begin(), vec.end(), 1);  // O(n) 
                                      // vec: {4, 12, 18, 16, ?, ?, ?, ?}




  vector<int>::iterator newEnd = remove(vec.begin(), vec.end(), 1);   // O(n)
  vec.erase(newEnd, vec.end());  

  // Similarly for algorithm: remove_if() and unique()


  // vec still occupy 8 int space: vec.capacity() == 8
  vec.shrink_to_fit();   // C++ 11
  // Now vec.capacity() == 4 

  // For C++ 03:
  vector<int>(vec).swap(vec); // Release the vacant memory

/ * * Удалить из списка * /

  list<int> mylist = {1, 4, 1, 1, 1, 12, 18, 16};

  list<int>::iterator newEnd = remove(mylist.begin(), mylist.end(), 1);  
  mylist.erase(newEnd, mylist.end());


  mylist.remove(1);  // faster

/ * * Удалить из ассоциативных контейнеров или неупорядоченных контейнеров * /

  multiset<int> myset = {1, 4, 1, 1, 1, 12, 18, 16};

  multiset<int>::iterator newEnd = remove(myset.begin(), myset.end(), 1);  
  myset.erase(newEnd, myset.end()); // O(n)

  myset.erase(1); // O(log(n)) or O(1)