1 //===- llvm/ADT/SetVector.h - Set with insert order iteration ---*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file implements a set that has insertion order iteration 11 // characteristics. This is useful for keeping a set of things that need to be 12 // visited later but in a deterministic order (insertion order). The interface 13 // is purposefully minimal. 14 // 15 // This file defines SetVector and SmallSetVector, which performs no allocations 16 // if the SetVector has less than a certain number of elements. 17 // 18 //===----------------------------------------------------------------------===// 19 20 #ifndef LLVM_ADT_SETVECTOR_H 21 #define LLVM_ADT_SETVECTOR_H 22 23 #include "llvm/ADT/SmallSet.h" 24 #include <algorithm> 25 #include <cassert> 26 #include <vector> 27 28 namespace llvm { 29 30 /// This adapter class provides a way to keep a set of things that also has the 31 /// property of a deterministic iteration order. The order of iteration is the 32 /// order of insertion. 33 /// @brief A vector that has set insertion semantics. 34 template <typename T, typename Vector = std::vector<T>, 35 typename Set = SmallSet<T, 16> > 36 class SetVector { 37 public: 38 typedef T value_type; 39 typedef T key_type; 40 typedef T& reference; 41 typedef const T& const_reference; 42 typedef Set set_type; 43 typedef Vector vector_type; 44 typedef typename vector_type::const_iterator iterator; 45 typedef typename vector_type::const_iterator const_iterator; 46 typedef typename vector_type::size_type size_type; 47 48 /// @brief Construct an empty SetVector 49 SetVector() {} 50 51 /// @brief Initialize a SetVector with a range of elements 52 template<typename It> 53 SetVector(It Start, It End) { 54 insert(Start, End); 55 } 56 57 /// @brief Determine if the SetVector is empty or not. 58 bool empty() const { 59 return vector_.empty(); 60 } 61 62 /// @brief Determine the number of elements in the SetVector. 63 size_type size() const { 64 return vector_.size(); 65 } 66 67 /// @brief Get an iterator to the beginning of the SetVector. 68 iterator begin() { 69 return vector_.begin(); 70 } 71 72 /// @brief Get a const_iterator to the beginning of the SetVector. 73 const_iterator begin() const { 74 return vector_.begin(); 75 } 76 77 /// @brief Get an iterator to the end of the SetVector. 78 iterator end() { 79 return vector_.end(); 80 } 81 82 /// @brief Get a const_iterator to the end of the SetVector. 83 const_iterator end() const { 84 return vector_.end(); 85 } 86 87 /// @brief Return the last element of the SetVector. 88 const T &back() const { 89 assert(!empty() && "Cannot call back() on empty SetVector!"); 90 return vector_.back(); 91 } 92 93 /// @brief Index into the SetVector. 94 const_reference operator[](size_type n) const { 95 assert(n < vector_.size() && "SetVector access out of range!"); 96 return vector_[n]; 97 } 98 99 /// @returns true iff the element was inserted into the SetVector. 100 /// @brief Insert a new element into the SetVector. 101 bool insert(const value_type &X) { 102 bool result = set_.insert(X); 103 if (result) 104 vector_.push_back(X); 105 return result; 106 } 107 108 /// @brief Insert a range of elements into the SetVector. 109 template<typename It> 110 void insert(It Start, It End) { 111 for (; Start != End; ++Start) 112 if (set_.insert(*Start)) 113 vector_.push_back(*Start); 114 } 115 116 /// @brief Remove an item from the set vector. 117 bool remove(const value_type& X) { 118 if (set_.erase(X)) { 119 typename vector_type::iterator I = 120 std::find(vector_.begin(), vector_.end(), X); 121 assert(I != vector_.end() && "Corrupted SetVector instances!"); 122 vector_.erase(I); 123 return true; 124 } 125 return false; 126 } 127 128 129 /// @returns 0 if the element is not in the SetVector, 1 if it is. 130 /// @brief Count the number of elements of a given key in the SetVector. 131 size_type count(const key_type &key) const { 132 return set_.count(key); 133 } 134 135 /// @brief Completely clear the SetVector 136 void clear() { 137 set_.clear(); 138 vector_.clear(); 139 } 140 141 /// @brief Remove the last element of the SetVector. 142 void pop_back() { 143 assert(!empty() && "Cannot remove an element from an empty SetVector!"); 144 set_.erase(back()); 145 vector_.pop_back(); 146 } 147 148 bool operator==(const SetVector &that) const { 149 return vector_ == that.vector_; 150 } 151 152 bool operator!=(const SetVector &that) const { 153 return vector_ != that.vector_; 154 } 155 156 private: 157 set_type set_; ///< The set. 158 vector_type vector_; ///< The vector. 159 }; 160 161 /// SmallSetVector - A SetVector that performs no allocations if smaller than 162 /// a certain size. 163 template <typename T, unsigned N> 164 class SmallSetVector : public SetVector<T, SmallVector<T, N>, SmallSet<T, N> > { 165 public: 166 SmallSetVector() {} 167 168 /// @brief Initialize a SmallSetVector with a range of elements 169 template<typename It> 170 SmallSetVector(It Start, It End) { 171 this->insert(Start, End); 172 } 173 }; 174 175 } // End llvm namespace 176 177 // vim: sw=2 ai 178 #endif 179
