LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

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 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