SetVector.h revision cf48cab945f1cbdf637d7d970398cbe6d89135ee
1//===- llvm/ADT/SetVector.h - Set with insert order iteration ---*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by Reid Spencer and is distributed under 6// the University of Illinois Open Source 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//===----------------------------------------------------------------------===// 16 17#ifndef LLVM_ADT_SETVECTOR_H 18#define LLVM_ADT_SETVECTOR_H 19 20#include <set> 21#include <vector> 22#include <cassert> 23#include <algorithm> 24 25namespace llvm { 26 27/// This class provides a way to keep a set of things that also has the 28/// property of a deterministic iteration order. The order of iteration is the 29/// order of insertion. 30/// @brief A vector that has set insertion semantics. 31template <typename T> 32class SetVector { 33public: 34 typedef T value_type; 35 typedef T key_type; 36 typedef T& reference; 37 typedef const T& const_reference; 38 typedef std::set<value_type> set_type; 39 typedef std::vector<value_type> vector_type; 40 typedef typename vector_type::const_iterator iterator; 41 typedef typename vector_type::const_iterator const_iterator; 42 typedef typename vector_type::size_type size_type; 43 44 /// @brief Construct an empty SetVector 45 SetVector() {} 46 47 /// @brief Initialize a SetVector with a range of elements 48 template<typename It> 49 SetVector(It Start, It End) { 50 insert(Start, End); 51 } 52 53 /// @brief Determine if the SetVector is empty or not. 54 bool empty() const { 55 return vector_.empty(); 56 } 57 58 /// @brief Determine the number of elements in the SetVector. 59 size_type size() const { 60 return vector_.size(); 61 } 62 63 /// @brief Get an iterator to the beginning of the SetVector. 64 iterator begin() { 65 return vector_.begin(); 66 } 67 68 /// @brief Get a const_iterator to the beginning of the SetVector. 69 const_iterator begin() const { 70 return vector_.begin(); 71 } 72 73 /// @brief Get an iterator to the end of the SetVector. 74 iterator end() { 75 return vector_.end(); 76 } 77 78 /// @brief Get a const_iterator to the end of the SetVector. 79 const_iterator end() const { 80 return vector_.end(); 81 } 82 83 /// @brief Return the last element of the SetVector. 84 const T &back() const { 85 assert(!empty() && "Cannot call back() on empty SetVector!"); 86 return vector_.back(); 87 } 88 89 /// @brief Index into the SetVector. 90 const_reference operator[](size_type n) const { 91 assert(n < vector_.size() && "SetVector access out of range!"); 92 return vector_[n]; 93 } 94 95 /// @returns true iff the element was inserted into the SetVector. 96 /// @brief Insert a new element into the SetVector. 97 bool insert(const value_type &X) { 98 bool result = set_.insert(X).second; 99 if (result) 100 vector_.push_back(X); 101 return result; 102 } 103 104 /// @brief Insert a range of elements into the SetVector. 105 template<typename It> 106 void insert(It Start, It End) { 107 for (; Start != End; ++Start) 108 if (set_.insert(*Start).second) 109 vector_.push_back(*Start); 110 } 111 112 /// @brief Remove an item from the set vector. 113 void remove(const value_type& X) { 114 if (0 < set_.erase(X)) { 115 typename vector_type::iterator I = 116 std::find(vector_.begin(), vector_.end(), X); 117 assert(I != vector_.end() && "Corrupted SetVector instances!"); 118 vector_.erase(I); 119 } 120 } 121 122 123 /// @returns 0 if the element is not in the SetVector, 1 if it is. 124 /// @brief Count the number of elements of a given key in the SetVector. 125 size_type count(const key_type &key) const { 126 return set_.count(key); 127 } 128 129 /// @brief Completely clear the SetVector 130 void clear() { 131 set_.clear(); 132 vector_.clear(); 133 } 134 135 /// @brief Remove the last element of the SetVector. 136 void pop_back() { 137 assert(!empty() && "Cannot remove an element from an empty SetVector!"); 138 set_.erase(back()); 139 vector_.pop_back(); 140 } 141 142private: 143 set_type set_; ///< The set. 144 vector_type vector_; ///< The vector. 145}; 146 147} // End llvm namespace 148 149// vim: sw=2 ai 150#endif 151