c++ - 使用 std::map 检查字符串是否包含重复项

Question

我有一个函数，通过将每个字符作为键，使用 std::map 检查字符串是否包含重复项。无法弄清楚为什么这不起作用。

#include<iostream>
#include<map>
#include<string>
int unique_char(std::string s){
 for(int i=0 ; i < s.size(); i++ )
  {
    std::map<char,int> uniq_hash_table;
    std::pair<std::map<char,int>::iterator,bool> ret;
    ret = uniq_hash_table.insert(std::pair<char,int>(s[i],0));
    if(ret.second==false)
     {
      std::cout << "The string contains duplicates" << std::endl;
      return 1;
     }
  }
return 0;
}
int main()
{
 std::string s="abcd";
 std::string s1="aabc";
 if(unique_char(s)==0){
 std::cout << "The 1st string does not contain duplicates" << std::endl;}
 if(unique_char(s1)==0){
 std::cout << "The 2nd string does not contain duplicates" << std::endl;}
 return 0;
}

对于这两个示例，程序都返回“字符串不包含重复项”。

ps:我故意使用 std::map 来获得 O(n) 解决方案。

Answer 1

您的解决方案不起作用，因为您的 std::map<char,int>在循环的每次迭代中重新创建。然后，在循环的每次迭代中，映射都是空的。那么，就没有重复了。

最好使用 std::set<char> .你可以这样做:

bool contains_duplicated_char(const std::string& s)
{
  std::set<char> check_uniq;
  for(unsigned long int i = 0; i < s.length(); ++i)
    if(!check_uniq.insert(s[i]).second)
      return true; // Duplicated char found
  return false; // No duplicated char found
}

然后这样调用:

const std::string str = "abcdefghijklamnopb";
const bool dupl = contains_duplicated(str);

为了让你的代码更通用(管理更多的数据类型)，你也可以这样创建你的函数:

template <typename Type, typename IteratorType>
bool contains_duplicated(IteratorType begin, IteratorType end)
{
  std::set<Type> check_uniq;
  for(IteratorType it = begin; it != end; ++it)
    if(!check_uniq.insert(*it).second)
      return true;
  return false;
}

然后像这样调用它:

std::vector<std::string> vec_str;
vec_str.push_back("Foo");
vec_str.push_back("Bar");
vec_str.push_back("Baz");
vec_str.push_back("Bar");
const bool dupl = contains_duplaicated<std::string>(vec_str.begin(), vec_str.end());
//...
const std::string str = "abcdefab";
const bool dupl2 = contains_duplacated<char>(str.begin(), str.end());
//...
const std::deque<long int> x(4, 0);
x[0] = 1;
x[1] = 17;
x[2] = 31;
x[3] = 0;
const bool dupl3 = contains_duplicated<long int>(x.begin(), x.end());