C++ : How to find duplicates in a vector ?

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

Advertisements
  • 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

Do you want to Learn Modern C++ from best?

We have curated a list of Best C++ Courses, that will teach you the cutting edge Modern C++ from the absolute beginning to advanced level. It will also introduce to you the word of Smart Pointers, Move semantics, Rvalue, Lambda function, auto, Variadic template, range based for loops, Multi-threading and many other latest features of C++ i.e. from C++11 to C++20.

Check Detailed Reviews of Best Modern C++ Courses

Remember, C++ requires a lot of patience, persistence, and practice. So, start learning today.

Leave a Comment

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Scroll to Top