A template function to check a std::vector<T> for duplicate values.

contains-duplicate.cpp

// O(n) time and O(n) space where n = length of the input sequence
template <typename T>
bool containsDuplicate(std::vector<T> &sequence) {
    std::unordered_set<T> uset;
    for (auto val : sequence) {
        if (uset.count(val) > 0) {
            return true;
        }
        uset.insert(val);
    }
    return false;
}

// Usage
std::vector<int> vec1;
vec1.push_back(1);
vec1.push_back(3);
vec1.push_back(1);
// 1 3 1
std::cout << containsDuplicate(vec1) << std::endl; // 1

Building on the above, we could have a struct or some other user defined data structure to represent each duplicate and store information about where the duplicate occurred.

struct DuplicateInfo {
	int val;
	int idx;
	DuplicateInfo() : val(0), idx(0) {};
	DuplicateInfo(int x, int index) : val(x), idx(index) {};
};

template <typename T>
std::vector<DuplicateInfo> containsDuplicate(std::vector<T>& sequence) {
	std::unordered_set<T> uset;
	std::vector<DuplicateInfo> info;
	for (int i = 0; i < sequence.size(); i++) {
		if (uset.count(sequence[i]) > 0) {
			DuplicateInfo d(sequence[i], i);
			info.push_back(d);
		}
		uset.insert(sequence[i]);
	}
	return info;
}


std::vector<int> vec;
vec.push_back(1);
vec.push_back(3);
vec.push_back(1);
vec.push_back(2);
vec.push_back(3);
vec.push_back(1);
vec.push_back(2);

vector<DuplicateInfo> duplicateList = containsDuplicate(vec);

if (duplicateList.size() > 0) {
    // list contains duplicates
    for (auto d : duplicateList) {
        cout << "Duplicate value: " << d.val << " at index: " << d.idx << endl;
    }
}

Duplicate value: 1 at index: 2
Duplicate value: 3 at index: 4
Duplicate value: 1 at index: 5
Duplicate value: 2 at index: 6