CODEWITHSUNDEEP
c++stringdictionary
user_3505115
user_3505115

Reputation: 61

Check if a string contains duplicates using std::map

I have a function that checks if a string contains duplicates using std::map by putting each char as a key. Can't figure out why this doesn't work.

#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;
}

The program returns "string does not contain duplicates" for both examples.

ps: I'm purposely using std::map to get O(n) solution.

Upvotes: 1

Views: 763

Answers (3)

Caduchon
Caduchon

Reputation: 5201

Your solution doesn't work because your std::map<char,int> is re-created at each iteration of the loop. Then, at each iteration of the loop, the map is empty. Then, there is no duplication.

Better to use a std::set<char>. You can do something like that :

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
}

and then call it by this way :

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

In order to make your code more generic (managing more data types), you can also create your function in that way :

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;
}

and then call it like :

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());

Upvotes: 2

Christophe
Christophe

Reputation: 73376

As your map definition is within the body of the for loop, you recreate an empty map at each iteration.

Declare your container outside the loop and it 'll work better.

Note that you could use a set instead of a map if you never increment the int value.

Upvotes: 1

Edgar Rokjān
Edgar Rokjān

Reputation: 17483

It does not work because uniq_hash_table is recreated for each symbol inside for loop.

Try to move it into the beginning of the function right before the for loop:

std::map<char,int> uniq_hash_table;

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

Upvotes: 1

Related Questions