llvm/llvm/include/llvm/ADT/MapVector.h

//===- llvm/ADT/MapVector.h - Map w/ deterministic value order --*- 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 map that provides insertion order iteration. The
/// interface is purposefully minimal. The key is assumed to be cheap to copy
/// and 2 copies are kept, one for indexing in a DenseMap, one for iteration in
/// a SmallVector.
///
//===----------------------------------------------------------------------===//

#ifndef LLVM_ADT_MAPVECTOR_H
#define LLVM_ADT_MAPVECTOR_H

#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallVector.h"
#include <cassert>
#include <cstddef>
#include <iterator>
#include <type_traits>
#include <utility>

namespace llvm {

/// This class implements a map that also provides access to all stored values
/// in a deterministic order. The values are kept in a SmallVector<*, 0> and the
/// mapping is done with DenseMap from Keys to indexes in that vector.
template <typename KeyT, typename ValueT,
          typename MapType = DenseMap<KeyT, unsigned>,
          typename VectorType = SmallVector<std::pair<KeyT, ValueT>, 0>>
class MapVector {
  MapType Map;
  VectorType Vector;

  static_assert(
      std::is_integral_v<typename MapType::mapped_type>,
      "The mapped_type of the specified Map must be an integral type");

public:
  using key_type = KeyT;
  using value_type = typename VectorType::value_type;
  using size_type = typename VectorType::size_type;

  using iterator = typename VectorType::iterator;
  using const_iterator = typename VectorType::const_iterator;
  using reverse_iterator = typename VectorType::reverse_iterator;
  using const_reverse_iterator = typename VectorType::const_reverse_iterator;

  /// Clear the MapVector and return the underlying vector.
  VectorType takeVector() { … }

  size_type size() const { … }

  /// Grow the MapVector so that it can contain at least \p NumEntries items
  /// before resizing again.
  void reserve(size_type NumEntries) { … }

  iterator begin() { … }
  const_iterator begin() const { … }
  iterator end() { … }
  const_iterator end() const { … }

  reverse_iterator rbegin() { … }
  const_reverse_iterator rbegin() const { … }
  reverse_iterator rend() { … }
  const_reverse_iterator rend() const { … }

  bool empty() const { … }

  std::pair<KeyT, ValueT>       &front()       { … }
  const std::pair<KeyT, ValueT> &front() const { … }
  std::pair<KeyT, ValueT>       &back()        { … }
  const std::pair<KeyT, ValueT> &back()  const { … }

  void clear() { … }

  void swap(MapVector &RHS) { … }

  ValueT &operator[](const KeyT &Key) { … }

  // Returns a copy of the value.  Only allowed if ValueT is copyable.
  ValueT lookup(const KeyT &Key) const { … }

  template <typename... Ts>
  std::pair<iterator, bool> try_emplace(const KeyT &Key, Ts &&...Args) { … }
  template <typename... Ts>
  std::pair<iterator, bool> try_emplace(KeyT &&Key, Ts &&...Args) { … }

  std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { … }
  std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) { … }

  template <typename V>
  std::pair<iterator, bool> insert_or_assign(const KeyT &Key, V &&Val) { … }
  template <typename V>
  std::pair<iterator, bool> insert_or_assign(KeyT &&Key, V &&Val) { … }

  bool contains(const KeyT &Key) const { … }

  size_type count(const KeyT &Key) const { … }

  iterator find(const KeyT &Key) { … }

  const_iterator find(const KeyT &Key) const { … }

  /// Remove the last element from the vector.
  void pop_back() { … }

  /// Remove the element given by Iterator.
  ///
  /// Returns an iterator to the element following the one which was removed,
  /// which may be end().
  ///
  /// \note This is a deceivingly expensive operation (linear time).  It's
  /// usually better to use \a remove_if() if possible.
  typename VectorType::iterator erase(typename VectorType::iterator Iterator) { … }

  /// Remove all elements with the key value Key.
  ///
  /// Returns the number of elements removed.
  size_type erase(const KeyT &Key) { … }

  /// Remove the elements that match the predicate.
  ///
  /// Erase all elements that match \c Pred in a single pass.  Takes linear
  /// time.
  template <class Predicate> void remove_if(Predicate Pred);
};

template <typename KeyT, typename ValueT, typename MapType, typename VectorType>
template <class Function>
void MapVector<KeyT, ValueT, MapType, VectorType>::remove_if(Function Pred) { … }

/// A MapVector that performs no allocations if smaller than a certain
/// size.
template <typename KeyT, typename ValueT, unsigned N>
struct SmallMapVector
    : MapVector<KeyT, ValueT, SmallDenseMap<KeyT, unsigned, N>,
                SmallVector<std::pair<KeyT, ValueT>, N>> { … };

} // end namespace llvm

#endif // LLVM_ADT_MAPVECTOR_H