In this article we will discuss how to find duplicate elements in vector and their repetition count.

Suppose we have a vector of strings i.e.

// Vector of strings
std::vector<std::string> vecOfStings{ "at" , "hello", "hi", "there", "where", "now", "is", \
										"that" , "hi" , "where", "at", "no", "yes", "at"};

Let’s find duplicate elements from this list and their duplication count. For example in above vector duplicate strings and their duplication count is as follows,
at :: 3
hi :: 2
where :: 2

Let’s see how to do that,

Finding duplicates in a vector

Steps are :

  • Create a map of <string , int> type to store the frequency count of each string in vector.
  • Iterate over all the elements in vector try to insert it in map as key with value as 1.
    • If string already exists in map then increment its value by 1.

// Create a map to store the frequency of each element in vector
std::map<std::string, int> countMap;

// Iterate over the vector and store the frequency of each element in map
for (auto & elem : vecOfStings)
{
	auto result = countMap.insert(std::pair<std::string, int>(elem, 1));
	if (result.second == false)
		result.first->second++;
}

  • Now iterate over the map and print items whose value is greater than 1 i.e.

// Iterate over the map
for (auto & elem : countMap)
{
	// If frequency count is greater than 1 then its a duplicate element
	if (elem.second > 1)
	{
		std::cout << elem.first << " :: " << elem.second << std::endl;
	}
}

It will print duplicate elements in vector and their duplication count i.e.
at :: 3
hi :: 2
where :: 2

Generic function to find duplicates in vector :

Create a Generic function to get the duplicate elements and their duplication count i.e.

/*
 * Generic function to find duplicates elements in vector.
 * It adds the duplicate elements and their duplication count in given map countMap
 */
template <typename T>
void findDuplicates(std::vector<T> & vecOfElements, std::map<T, int> & countMap)
{
	// Iterate over the vector and store the frequency of each element in map
	for (auto & elem : vecOfElements)
	{
		auto result = countMap.insert(std::pair<std::string, int>(elem, 1));
		if (result.second == false)
			result.first->second++;
	}

	// Remove the elements from Map which has 1 frequency count
	for (auto it = countMap.begin() ; it != countMap.end() ;)
	{
		if (it->second == 1)
			it = countMap.erase(it);
		else
			it++;

	}
}

Let’s use this generic function to find duplicate elements in vector i.e.
std::map<std::string, int> duplicateElements;

// Get the duplicate elements in vector
findDuplicates(vecOfStings, duplicateElements);

Now Iterate over this map to print the duplicate elements with count i.e.
for (auto & elem : duplicateElements)
	std::cout << elem.first << " :: " << elem.second << std::endl;

Output:
at :: 3
hi :: 2
where :: 2

Complete example is as follows,
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <functional>
#include <string>

// Print the contents of vector
template <typename T>
void print(T & vecOfElements, std::string delimeter = " , ")
{
	for(auto elem : vecOfElements)
		std::cout<<elem<<delimeter;
	std::cout << std::endl;
}

/*
 * Generic function to find duplicates elements in vector.
 * It adds the duplicate elements and their duplication count in given map countMap
 */
template <typename T>
void findDuplicates(std::vector<T> & vecOfElements, std::map<T, int> & countMap)
{
	// Iterate over the vector and store the frequency of each element in map
	for (auto & elem : vecOfElements)
	{
		auto result = countMap.insert(std::pair<std::string, int>(elem, 1));
		if (result.second == false)
			result.first->second++;
	}

	// Remove the elements from Map which has 1 frequency count
	for (auto it = countMap.begin() ; it != countMap.end() ;)
	{
		if (it->second == 1)
			it = countMap.erase(it);
		else
			it++;

	}
}


int main()
{
	// Vector of strings
	std::vector<std::string> vecOfStings{ "at" , "hello", "hi", "there", "where", "now", "is", \
											"that" , "hi" , "where", "at", "no", "yes", "at"};

	print(vecOfStings);

	// Create a map to store the frequency of each element in vector
	std::map<std::string, int> countMap;

	// Iterate over the vector and store the frequency of each element in map
	for (auto & elem : vecOfStings)
	{
		auto result = countMap.insert(std::pair<std::string, int>(elem, 1));
		if (result.second == false)
			result.first->second++;
	}

	std::cout << "Duplicate elements and their duplication count " << std::endl;

	// Iterate over the map
	for (auto & elem : countMap)
	{
		// If frequency count is greater than 1 then its a duplicate element
		if (elem.second > 1)
		{
			std::cout << elem.first << " :: " << elem.second << std::endl;
		}
	}

	/*
	 * Finding duplicates in vector using generic function
	 */

	std::map<std::string, int> duplicateElements;

	// Get the duplicate elements in vector
	findDuplicates(vecOfStings, duplicateElements);

	std::cout << "Duplicate elements and their duplication count " << std::endl;
	for (auto & elem : duplicateElements)
			std::cout << elem.first << " :: " << elem.second << std::endl;

	return 0;
}

Output:
at , hello , hi , there , where , now , is , that , hi , where , at , no , yes , at , 
Duplicate elements and their duplication count 
at :: 3
hi :: 2
where :: 2
Duplicate elements and their duplication count 
at :: 3
hi :: 2
where :: 2

To compile the example use following command,

g++ –std=c++11 example.cpp

Related Posts: