檢查一個字符串是否包含重複使用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()); 

Answer 2

它不起作用，因爲for循環內的每個符號都會重新創建uniq_hash_table。

嘗試將其移動到函數開頭的for循環前右：

std::map<char,int> uniq_hash_table; 

for(int i=0 ; i < s.size(); i++) 
{ 
    // ... 
} 

Answer 3

當你的映射定義的for循環體內，重新創建在每次迭代一個空映射。

聲明你的容器在循環之外，它會更好地工作。

請注意，如果您從不增加int值，則可以使用set而不是map。