LLVM API Documentation
00001 //===- llvm/ADT/SetVector.h - Set with insert order iteration ---*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by Reid Spencer and is distributed under 00006 // the University of Illinois Open Source 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 //===----------------------------------------------------------------------===// 00016 00017 #ifndef LLVM_ADT_SETVECTOR_H 00018 #define LLVM_ADT_SETVECTOR_H 00019 00020 #include <set> 00021 #include <vector> 00022 #include <cassert> 00023 #include <algorithm> 00024 00025 namespace llvm { 00026 00027 /// This class provides a way to keep a set of things that also has the 00028 /// property of a deterministic iteration order. The order of iteration is the 00029 /// order of insertion. 00030 /// @brief A vector that has set insertion semantics. 00031 template <typename T> 00032 class SetVector { 00033 public: 00034 typedef T value_type; 00035 typedef T key_type; 00036 typedef T& reference; 00037 typedef const T& const_reference; 00038 typedef std::set<value_type> set_type; 00039 typedef std::vector<value_type> vector_type; 00040 typedef typename vector_type::iterator iterator; 00041 typedef typename vector_type::const_iterator const_iterator; 00042 typedef typename vector_type::size_type size_type; 00043 00044 /// @brief Construct an empty SetVector 00045 SetVector() {} 00046 00047 /// @brief Initialize a SetVector with a range of elements 00048 template<typename It> 00049 SetVector(It Start, It End) { 00050 insert(Start, End); 00051 } 00052 00053 /// @brief Determine if the SetVector is empty or not. 00054 bool empty() const { 00055 return vector_.empty(); 00056 } 00057 00058 /// @brief Determine the number of elements in the SetVector. 00059 size_type size() const { 00060 return vector_.size(); 00061 } 00062 00063 /// @brief Get an iterator to the beginning of the SetVector. 00064 iterator begin() { 00065 return vector_.begin(); 00066 } 00067 00068 /// @brief Get a const_iterator to the beginning of the SetVector. 00069 const_iterator begin() const { 00070 return vector_.begin(); 00071 } 00072 00073 /// @brief Get an iterator to the end of the SetVector. 00074 iterator end() { 00075 return vector_.end(); 00076 } 00077 00078 /// @brief Get a const_iterator to the end of the SetVector. 00079 const_iterator end() const { 00080 return vector_.end(); 00081 } 00082 00083 /// @brief Return the last element of the SetVector. 00084 const T &back() const { 00085 assert(!empty() && "Cannot call back() on empty SetVector!"); 00086 return vector_.back(); 00087 } 00088 00089 /// @brief Index into the SetVector. 00090 const_reference operator[](size_type n) const { 00091 assert(n < vector_.size() && "SetVector access out of range!"); 00092 return vector_[n]; 00093 } 00094 00095 /// @returns true iff the element was inserted into the SetVector. 00096 /// @brief Insert a new element into the SetVector. 00097 bool insert(const value_type &X) { 00098 bool result = set_.insert(X).second; 00099 if (result) 00100 vector_.push_back(X); 00101 return result; 00102 } 00103 00104 /// @brief Insert a range of elements into the SetVector. 00105 template<typename It> 00106 void insert(It Start, It End) { 00107 for (; Start != End; ++Start) 00108 if (set_.insert(*Start).second) 00109 vector_.push_back(*Start); 00110 } 00111 00112 /// @brief Remove an item from the set vector. 00113 void remove(const value_type& X) { 00114 if (0 < set_.erase(X)) { 00115 iterator I = std::find(vector_.begin(),vector_.end(),X); 00116 assert(I != vector_.end() && "Corrupted SetVector instances!"); 00117 vector_.erase(I); 00118 } 00119 } 00120 00121 00122 /// @returns 0 if the element is not in the SetVector, 1 if it is. 00123 /// @brief Count the number of elements of a given key in the SetVector. 00124 size_type count(const key_type &key) const { 00125 return set_.count(key); 00126 } 00127 00128 /// @brief Completely clear the SetVector 00129 void clear() { 00130 set_.clear(); 00131 vector_.clear(); 00132 } 00133 00134 /// @brief Remove the last element of the SetVector. 00135 void pop_back() { 00136 assert(!empty() && "Cannot remove an element from an empty SetVector!"); 00137 set_.erase(back()); 00138 vector_.pop_back(); 00139 } 00140 00141 private: 00142 set_type set_; ///< The set. 00143 vector_type vector_; ///< The vector. 00144 }; 00145 00146 } // End llvm namespace 00147 00148 // vim: sw=2 ai 00149 #endif