martinlicht

Removing duplicates from a C++ container, using forward iterators

This gist further discusses how to remove duplicates from a C++ container. A previous gist discussed the removal of duplicates from random access containers. But not every container supports random access; more precisely, not every container supports random access iterators.

Let us discuss removing duplicates when the container interface is the most basic one: only supporting forward iterators. Moreover, we will not require that the elements support comparisons.

A very basic and naive algorithm works in-place and runs in quadratic time.

martinlicht

How to remove duplicates from a C++ container

This Gist discusses how to remove duplicate elements from C++ Standard Template Library (STL) containers such as std::vector. Albeit an everday task, this functionality is not part of the STL. Every C++ programmer sooner or later needs to write this functionality on their own. Writing this up has actually shown me a few surprises.

Introduction

Let us start with the canonical C++ solution to this problem. We use a combination of std::sort() and std::unique(), followed by a resizing of the vector. We can write this up with a template for the std::vector container.