Удаление дубликатов в векторе строк

Question

У меня есть вектор строк:

std::vector<std::string> fName

, который содержит список имен файлов <a,b,c,d,a,e,e,d,b>.

Я хочу избавиться от всех файлов, которые имеют дубликаты, и хочу сохранить только те файлы, которые не имеют дубликатов в векторе.

for(size_t l = 0; l < fName.size(); l++)
{
    strFile = fName.at(l);
    for(size_t k = 1; k < fName.size(); k++)
    {
        strFile2 = fName.at(k);
        if(strFile.compare(strFile2) == 0)
        {
            fName.erase(fName.begin() + l);
            fName.erase(fName.begin() + k);
        }
    }
}

Это удаляет несколько дубликатов, но осталось несколько дубликатов, нужна помощь в отладке.

Также мой ввод выглядит как <a,b,c,d,e,e,d,c,a>, и мой ожидаемый вывод - <b>, так как все остальные файлы b, c, d, e имеют дубликаты, которые они удаляют.

Answer 1

#include <algorithm>

template <typename T>
void remove_duplicates(std::vector<T>& vec)
{
  std::sort(vec.begin(), vec.end());
  vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
}

Примечание: для этого требуется, чтобы T определил operator< и operator==.

Почему это работает?

std ::sort сортирует элементы, используя их оператор сравнения меньше, чем

std :: unique удаляет дублирующиеся последовательные элементы, сравнивая их, используя их оператор сравнения

Что, если мне нужны только уникальные элементы?

Тогда вам лучше использовать std :: map

#include <algorithm>
#include <map>

template <typename T>
void unique_elements(std::vector<T>& vec)
{   
  std::map<T, int> m;
  for(auto p : vec) ++m[p];
  vec.erase(transform_if(m.begin(), m.end(), vec.begin(),
                         [](std::pair<T,int> const& p) {return p.first;},
                         [](std::pair<T,int> const& p) {return p.second==1;}),
            vec.end());
}

См .: здесь .

Answer 2

Если я правильно понимаю ваши требования, и я не совсем уверен в этом.Вы хотите сохранить только элементы в вашем векторе, которые не повторяются, верно?

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

map<string,int> m;
for (auto & i : v)
    m[i]++;
v.clear();
for (auto & i : m)
    if(i.second == 1)
        v.push_back(i.first);

Или, для вызываемой функции компилятора:

map<string,int> m;
for (vector<string>::iterator i=v.begin(); i!=v.end(); ++i)
    m[*i]++;
v.clear();
for (map<string,int>::iterator i=m.begin(); i!=m.end(); ++i)
    if (i->second == 1)
        v.push_back(i->first);

Answer 3

#include <algorithms>

template <typename T>
remove_duplicates(std::vector<T>& vec)
{
  std::vector<T> tvec;
  uint32_t size = vec.size();
  for (uint32_t i; i < size; i++) {
    if (std::find(vec.begin() + i + 1, vec.end(), vec[i]) == vector.end()) {
      tvec.push_back(t);
    } else {
      vec.push_back(t);
    }
  vec = tvec; // : )
  }
}

Answer 4

Вы можете устранить дубликаты в O (log n) времени выполнения и O (n) пространстве:

std::set<std::string> const uniques(vec.begin(), vec.end());
vec.assign(uniques.begin(), uniques.end());

Но O (log n) время выполнения немного вводит в заблуждение, потому что пространство O (n)фактически делает O (n) динамических распределений, которые дороги с точки зрения скорости.Элементы также должны быть сопоставимы (здесь operator<(), который std::string поддерживает как лексикографическое сравнение).

Если вы хотите хранить только уникальные элементы:

template<typename In>
In find_unique(In first, In last)
{
    if( first == last ) return last;
    In tail(first++);
    int dupes = 0;
    while( first != last ) {
        if( *tail++ == *first++ ) ++dupes;
        else if( dupes != 0 ) dupes = 0;
        else return --tail;
    }
    return dupes == 0 ? tail : last;
}

Алгоритмвыше берет отсортированный диапазон и возвращает первый уникальный элемент, в линейном времени и постоянном пространстве.Чтобы получить все уникальные объекты в контейнере, вы можете использовать его так:

auto pivot = vec.begin();
for( auto i(find_unique(vec.begin(), vec.end()));
     i != vec.end();
     i = find_unique(++i, vec.end())) {
    std::iter_swap(pivot++, i);
}
vec.erase(pivot, vec.end());