Лучший контейнер C ++ для удаления элементов?

Question

У меня есть список файлов (хранящихся в виде строк в стиле c), по которым я буду выполнять поиск, и я буду удалять те файлы, которые не соответствуют моим параметрам. Какой контейнер лучше всего использовать для этой цели? Я думаю, Set по состоянию на сейчас. Обратите внимание, что список файлов никогда не будет больше, чем при инициализации. Я буду только удалять из контейнера.

Answer 1

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

Если вы собираетесь выполнить эту операцию один раз, я бы использовал std :: vector с remove_if (из ), за которым следует удаление. Если вы ранее не использовали remove_if, то он проходит и сдвигает все соответствующие элементы вниз, перезаписывая ненужные элементы в процессе. Вы должны следовать за ним со стиранием, чтобы уменьшить размер вектора. Вот так:

std::vector<const char*> files;
files.erase(remove_if(files.begin(), files.end(), RemovePredicate()), files.end());

Написание кода для того же самого с использованием std :: list будет немного сложнее, если вы захотите воспользоваться его свойством времени удаления O (1). Поскольку вы выполняете эту разовую операцию, которая, вероятно, займет так мало времени, что вы даже не заметите ее, я бы порекомендовал сделать это, так как это самый простой способ.

И, честно говоря, я не думаю, что вы увидите такую ​​большую разницу в скорости между подходами std :: list и std :: vector. Векторный подход копирует каждое значение только один раз, так что на самом деле он довольно быстрый, но занимает гораздо меньше места. По моему мнению, переход к std :: list и использование трехкратного пробела оправдано только в том случае, если вы выполняете много операций по добавлению и удалению в течение всего срока службы приложения.

Answer 2

Элементы в std :: set должны быть уникальными, поэтому, если имена файлов не являются глобально уникальными, это не будет соответствовать вашим потребностям.

Возможно, я бы порекомендовал std :: list.

Answer 3

С SGI :

• A vector - это последовательность, которая поддерживает произвольный доступ к элементам, постоянное время вставки и удаления элементов в конце, а также линейное время вставки и удаления элементов в начале или в середине.

• A list является двусвязным списком. Таким образом, это последовательность, которая поддерживает как прямой, так и обратный обход, а также (амортизируется) постоянное время вставки и удаления элементов в начале или в конце, или в середине.

• slist - это односвязный список: список, где каждый элемент связан со следующим элементом, но не с предыдущим элементом. То есть это последовательность, которая поддерживает прямой, но не обратный обход, и (амортизируется) вставку и удаление элементов с постоянным временем.

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

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

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

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

(некоторые контейнеры были опущены.)

Я бы пошел с hash_set, если все, что вам нужно, это контейнер, который работает быстро и не содержит нескольких идентичных ключей. hash_multiset если вы это сделаете, set или multiset, если вы хотите, чтобы строки были отсортированы, или list или slist, если вы хотите, чтобы строки сохранили порядок вставки.

После того, как вы создали свой список / набор, используйте remove_if, чтобы отфильтровать ваши элементы на основе ваших критериев.

Answer 4

Вы можете использовать два списка / вектора / что угодно:

using namespace std;

vector<const char *> files;

files.push_back("foo.bat");
files.push_back("bar.txt");

vector<const char *> good_files;  // Maybe reserve elements given files.size()?

for(vector<const char *>::const_iterator i = files.begin(); i != files.end(); ++i) {
    if(file_is_good(*i)) {
        new_files.push_back(*i);
    }
}

Answer 5

Если ваши критерии поиска не зависят от имени файла (т. Е. Вы ищете контент, размеры файлов и т. Д.), Поэтому вы не можете использовать набор, я бы выбрал list. Вам понадобится O (N), чтобы составить весь список, и O (1) за одно удаление.

Если вы хотите сделать это еще быстрее и не настаиваете на использовании готовых контейнеров STL, я бы:

1. используйте vector
2. удалить используя false delete, т.е. пометка элемента как удаленного
3. когда отношение удаленных / всех элементов поднимается выше определенного порога, я бы фильтровал элементы с remove_if

Это должно дать вам лучшую производительность пространства / времени / кэша. (Хотя вы должны профилировать это, чтобы быть уверенным)

Answer 6

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