blob: 8366dda173e6bcdbcb25eff61324cad694cee835 [file] [log] [blame]
// Copyright 2020 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include <algorithm>
#include <utility>
#include <vector>
// A VectorSetSorter is a convenience class used to efficiently sort and
// de-duplicate one or more sets of items of type T, then iterate over the
// result, or get it as a simple vector. Usage is the following:
// For performance reasons, this implementation only stores pointers to the
// input items in order to minimize memory usage. Callers should ensure the
// items added to this sorter do not change until the instance is destroyed.
// 1) Create instance, passing an optional initial capacity.
// 2) Add items using one of the Add() methods, as many times as
// necessary. Note that this records only pointers to said items
// so their content should not change until the instance is destroyed.
// 3) Call IteratorOver() to iterate over all sorted and de-duplicated
// items.
// 4) Alternatively, call AsVector() to return a new vector that contains
// copies of the original sorted / deduplicated items.
template <typename T>
class VectorSetSorter {
// Constructor. |initial_capacity| might be provided to minimize the number
// of allocations performed by this instance, if the maximum number of
// input items is known in advance.
VectorSetSorter(size_t initial_capacity = 0) {
// Add one single item to the sorter.
void Add(const T& item) {
sorted_ = false;
// Add one range of items to the sorter.
void Add(typename std::vector<T>::const_iterator begin,
typename std::vector<T>::const_iterator end) {
for (; begin != end; ++begin)
sorted_ = false;
// Add one range of items to the sorter.
void Add(const T* start, const T* end) {
for (; start != end; ++start)
sorted_ = false;
// Iterate over all sorted items, removing duplicates from the loop.
// |item_callback| is a callable that will be invoked for each item in the
// result.
template <typename ITEM_CALLBACK>
void IterateOver(ITEM_CALLBACK item_callback) {
if (!sorted_) {
const T* prev_item = nullptr;
for (const T* item : ptrs_) {
if (!prev_item || *prev_item != *item) {
prev_item = item;
// Return the sorted and de-duplicated resulting set as a vector of items.
// Note that this copies the input items.
std::vector<T> AsVector() {
std::vector<T> result;
IterateOver([&result](const T& item) { result.push_back(item); });
return result;
// Sort all items previously added to this instance.
// Must be called after adding all desired items, and before
// calling IterateOver() or AsVector().
void Sort() {
std::sort(ptrs_.begin(), ptrs_.end(),
[](const T* a, const T* b) { return *a < *b; });
sorted_ = true;
std::vector<const T*> ptrs_;
bool sorted_ = false;