Удалить повторяющиеся символы из строки

Question

У меня есть строка, например, например. acaddef или bbaaddgg. Мне нужно как можно быстрее удалить все повторяющиеся символы. Так, например, pooaatat после этого должно выглядеть как poat и ggaatpop должно выглядеть как gatpo. Есть ли встроенная функция или алгоритм, чтобы сделать это быстро? Я пытался искать STL, но без удовлетворительного результата.

Answer 1

Итак, вот 4 различных решения.

Фиксированный массив

std::string str = "pooaatat"; 

// Prints "poat" 
short count[256] = {0}; 
std::copy_if(str.begin(), str.end(), std::ostream_iterator<char>(std::cout), 
      [&](unsigned char c) { return count[c]++ == 0; }); 

Count Algorithm + Итератор

std::string str = "pooaatat"; 

// Prints "poat" 
std::string::iterator iter = str.begin(); 
std::copy_if(str.begin(), str.end(), std::ostream_iterator<char>(std::cout), 
      [&](char c) { return !std::count(str.begin(), iter++, c); }); 

неупорядоченный набор

std::string str = "pooaatat"; 

// Prints "poat" 
std::unordered_set<char> container; 
std::copy_if(str.begin(), str.end(), std::ostream_iterator<char>(std::cout), 
      [&](char c) { return container.insert(c).second; }); 

Unordered Карта

std::string str = "pooaatat"; 

// Prints "poat" 
std::unordered_map<char, int> container; 
std::copy_if(str.begin(), str.end(), std::ostream_iterator<char>(std::cout), 
      [&](char c) { return container[c]++ == 0; }); 

Answer 2

AFAIK, для этого нет встроенного алгоритма. Алгоритм std::unique действителен, если вы хотите удалить только последовательные повторяющиеся символы.

Однако вы можете следовать следующей простой подход:

Если строка содержит только символы ASCII, вы можете сформировать булево массив A [256], обозначающее ли соответствующий характер встречались уже или нет.

Затем просто пройдете входную строку и скопируйте символ для вывода, если A [символ] по-прежнему 0 (и сделать A [символ] = 1).

В случае, если строка содержит произвольные символы, вы можете использовать std::unordered_map или std::map символа для int.

Answer 3

Встроенные регулярные выражения должны быть эффективными, т.е.

#include <regex> 
[...] 

const std::regex pattern("([\\w ])(?!\\1)"); 
string s = "ssha3akjssss42jj 234444 203488842882387 heeelloooo"; 
std::string result; 

for (std::sregex_iterator i(s.begin(), s.end(), pattern), end; i != end; ++i) 
    result.append((*i)[1]); 

std::cout << result << std::endl; 

Конечно, вы можете изменить группу cpaturing для ваших нужд. Хорошо, что он уже поддерживается в Visual Studio 2010 tr1. gcc 4.8, однако, имеет problem с итераторами регулярных выражений.