LLVM API Documentation

SetVector.h
Go to the documentation of this file.
00001 //===- llvm/ADT/SetVector.h - Set with insert order iteration ---*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements a set that has insertion order iteration
00011 // characteristics. This is useful for keeping a set of things that need to be
00012 // visited later but in a deterministic order (insertion order). The interface
00013 // is purposefully minimal.
00014 //
00015 // This file defines SetVector and SmallSetVector, which performs no allocations
00016 // if the SetVector has less than a certain number of elements.
00017 //
00018 //===----------------------------------------------------------------------===//
00019 
00020 #ifndef LLVM_ADT_SETVECTOR_H
00021 #define LLVM_ADT_SETVECTOR_H
00022 
00023 #include "llvm/ADT/SmallSet.h"
00024 #include <algorithm>
00025 #include <cassert>
00026 #include <vector>
00027 
00028 namespace llvm {
00029 
00030 /// \brief A vector that has set insertion semantics.
00031 ///
00032 /// This adapter class provides a way to keep a set of things that also has the
00033 /// property of a deterministic iteration order. The order of iteration is the
00034 /// order of insertion.
00035 template <typename T, typename Vector = std::vector<T>,
00036                       typename Set = SmallSet<T, 16> >
00037 class SetVector {
00038 public:
00039   typedef T value_type;
00040   typedef T key_type;
00041   typedef T& reference;
00042   typedef const T& const_reference;
00043   typedef Set set_type;
00044   typedef Vector vector_type;
00045   typedef typename vector_type::const_iterator iterator;
00046   typedef typename vector_type::const_iterator const_iterator;
00047   typedef typename vector_type::size_type size_type;
00048 
00049   /// \brief Construct an empty SetVector
00050   SetVector() {}
00051 
00052   /// \brief Initialize a SetVector with a range of elements
00053   template<typename It>
00054   SetVector(It Start, It End) {
00055     insert(Start, End);
00056   }
00057 
00058   /// \brief Determine if the SetVector is empty or not.
00059   bool empty() const {
00060     return vector_.empty();
00061   }
00062 
00063   /// \brief Determine the number of elements in the SetVector.
00064   size_type size() const {
00065     return vector_.size();
00066   }
00067 
00068   /// \brief Get an iterator to the beginning of the SetVector.
00069   iterator begin() {
00070     return vector_.begin();
00071   }
00072 
00073   /// \brief Get a const_iterator to the beginning of the SetVector.
00074   const_iterator begin() const {
00075     return vector_.begin();
00076   }
00077 
00078   /// \brief Get an iterator to the end of the SetVector.
00079   iterator end() {
00080     return vector_.end();
00081   }
00082 
00083   /// \brief Get a const_iterator to the end of the SetVector.
00084   const_iterator end() const {
00085     return vector_.end();
00086   }
00087 
00088   /// \brief Return the last element of the SetVector.
00089   const T &back() const {
00090     assert(!empty() && "Cannot call back() on empty SetVector!");
00091     return vector_.back();
00092   }
00093 
00094   /// \brief Index into the SetVector.
00095   const_reference operator[](size_type n) const {
00096     assert(n < vector_.size() && "SetVector access out of range!");
00097     return vector_[n];
00098   }
00099 
00100   /// \brief Insert a new element into the SetVector.
00101   /// \returns true iff the element was inserted into the SetVector.
00102   bool insert(const value_type &X) {
00103     bool result = set_.insert(X).second;
00104     if (result)
00105       vector_.push_back(X);
00106     return result;
00107   }
00108 
00109   /// \brief Insert a range of elements into the SetVector.
00110   template<typename It>
00111   void insert(It Start, It End) {
00112     for (; Start != End; ++Start)
00113       if (set_.insert(*Start).second)
00114         vector_.push_back(*Start);
00115   }
00116 
00117   /// \brief Remove an item from the set vector.
00118   bool remove(const value_type& X) {
00119     if (set_.erase(X)) {
00120       typename vector_type::iterator I =
00121         std::find(vector_.begin(), vector_.end(), X);
00122       assert(I != vector_.end() && "Corrupted SetVector instances!");
00123       vector_.erase(I);
00124       return true;
00125     }
00126     return false;
00127   }
00128 
00129   /// \brief Remove items from the set vector based on a predicate function.
00130   ///
00131   /// This is intended to be equivalent to the following code, if we could
00132   /// write it:
00133   ///
00134   /// \code
00135   ///   V.erase(std::remove_if(V.begin(), V.end(), P), V.end());
00136   /// \endcode
00137   ///
00138   /// However, SetVector doesn't expose non-const iterators, making any
00139   /// algorithm like remove_if impossible to use.
00140   ///
00141   /// \returns true if any element is removed.
00142   template <typename UnaryPredicate>
00143   bool remove_if(UnaryPredicate P) {
00144     typename vector_type::iterator I
00145       = std::remove_if(vector_.begin(), vector_.end(),
00146                        TestAndEraseFromSet<UnaryPredicate>(P, set_));
00147     if (I == vector_.end())
00148       return false;
00149     vector_.erase(I, vector_.end());
00150     return true;
00151   }
00152 
00153 
00154   /// \brief Count the number of elements of a given key in the SetVector.
00155   /// \returns 0 if the element is not in the SetVector, 1 if it is.
00156   size_type count(const key_type &key) const {
00157     return set_.count(key);
00158   }
00159 
00160   /// \brief Completely clear the SetVector
00161   void clear() {
00162     set_.clear();
00163     vector_.clear();
00164   }
00165 
00166   /// \brief Remove the last element of the SetVector.
00167   void pop_back() {
00168     assert(!empty() && "Cannot remove an element from an empty SetVector!");
00169     set_.erase(back());
00170     vector_.pop_back();
00171   }
00172   
00173   T LLVM_ATTRIBUTE_UNUSED_RESULT pop_back_val() {
00174     T Ret = back();
00175     pop_back();
00176     return Ret;
00177   }
00178 
00179   bool operator==(const SetVector &that) const {
00180     return vector_ == that.vector_;
00181   }
00182 
00183   bool operator!=(const SetVector &that) const {
00184     return vector_ != that.vector_;
00185   }
00186 
00187 private:
00188   /// \brief A wrapper predicate designed for use with std::remove_if.
00189   ///
00190   /// This predicate wraps a predicate suitable for use with std::remove_if to
00191   /// call set_.erase(x) on each element which is slated for removal.
00192   template <typename UnaryPredicate>
00193   class TestAndEraseFromSet {
00194     UnaryPredicate P;
00195     set_type &set_;
00196 
00197   public:
00198     TestAndEraseFromSet(UnaryPredicate P, set_type &set_) : P(P), set_(set_) {}
00199 
00200     template <typename ArgumentT>
00201     bool operator()(const ArgumentT &Arg) {
00202       if (P(Arg)) {
00203         set_.erase(Arg);
00204         return true;
00205       }
00206       return false;
00207     }
00208   };
00209 
00210   set_type set_;         ///< The set.
00211   vector_type vector_;   ///< The vector.
00212 };
00213 
00214 /// \brief A SetVector that performs no allocations if smaller than
00215 /// a certain size.
00216 template <typename T, unsigned N>
00217 class SmallSetVector : public SetVector<T, SmallVector<T, N>, SmallSet<T, N> > {
00218 public:
00219   SmallSetVector() {}
00220 
00221   /// \brief Initialize a SmallSetVector with a range of elements
00222   template<typename It>
00223   SmallSetVector(It Start, It End) {
00224     this->insert(Start, End);
00225   }
00226 };
00227 
00228 } // End llvm namespace
00229 
00230 // vim: sw=2 ai
00231 #endif