llvm/llvm/include/llvm/ADT/SetVector.h

//===- llvm/ADT/SetVector.h - Set with insert order iteration ---*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
///
/// \file
/// This file implements a set that has insertion order iteration
/// characteristics. This is useful for keeping a set of things that need to be
/// visited later but in a deterministic order (insertion order). The interface
/// is purposefully minimal.
///
/// This file defines SetVector and SmallSetVector, which performs no
/// allocations if the SetVector has less than a certain number of elements.
///
//===----------------------------------------------------------------------===//

#ifndef LLVM_ADT_SETVECTOR_H
#define LLVM_ADT_SETVECTOR_H

#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Support/Compiler.h"
#include <cassert>
#include <iterator>

namespace llvm {

/// A vector that has set insertion semantics.
///
/// This adapter class provides a way to keep a set of things that also has the
/// property of a deterministic iteration order. The order of iteration is the
/// order of insertion.
///
/// The key and value types are derived from the Set and Vector types
/// respectively. This allows the vector-type operations and set-type operations
/// to have different types. In particular, this is useful when storing pointers
/// as "Foo *" values but looking them up as "const Foo *" keys.
///
/// No constraint is placed on the key and value types, although it is assumed
/// that value_type can be converted into key_type for insertion. Users must be
/// aware of any loss of information in this conversion. For example, setting
/// value_type to float and key_type to int can produce very surprising results,
/// but it is not explicitly disallowed.
///
/// The parameter N specifies the "small" size of the container, which is the
/// number of elements upto which a linear scan over the Vector will be used
/// when searching for elements instead of checking Set, due to it being better
/// for performance. A value of 0 means that this mode of operation is not used,
/// and is the default value.
template <typename T, typename Vector = SmallVector<T, 0>,
          typename Set = DenseSet<T>, unsigned N = 0>
class SetVector { … };

/// A SetVector that performs no allocations if smaller than
/// a certain size.
template <typename T, unsigned N>
class SmallSetVector : public SetVector<T, SmallVector<T, N>, DenseSet<T>, N> { … };

} // end namespace llvm

namespace std {

/// Implement std::swap in terms of SetVector swap.
template <typename T, typename V, typename S, unsigned N>
inline void swap(llvm::SetVector<T, V, S, N> &LHS,
                 llvm::SetVector<T, V, S, N> &RHS) { … }

/// Implement std::swap in terms of SmallSetVector swap.
template<typename T, unsigned N>
inline void
swap(llvm::SmallSetVector<T, N> &LHS, llvm::SmallSetVector<T, N> &RHS) { … }

} // end namespace std

#endif // LLVM_ADT_SETVECTOR_H