SetVector.h revision 0bdc620c16963908d74db498f79676e558f09e82
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::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 iterator I = find(vector_.begin(),vector_.end(),X); 116 if (I != vector_.end()) 117 vector_.erase(I); 118 } 119 } 120 121 122 /// @returns 0 if the element is not in the SetVector, 1 if it is. 123 /// @brief Count the number of elements of a given key in the SetVector. 124 size_type count(const key_type &key) const { 125 return set_.count(key); 126 } 127 128 /// @brief Completely clear the SetVector 129 void clear() { 130 set_.clear(); 131 vector_.clear(); 132 } 133 134 /// @brief Remove the last element of the SetVector. 135 void pop_back() { 136 assert(!empty() && "Cannot remove an element from an empty SetVector!"); 137 set_.erase(back()); 138 vector_.pop_back(); 139 } 140 141private: 142 set_type set_; ///< The set. 143 vector_type vector_; ///< The vector. 144}; 145 146} // End llvm namespace 147 148// vim: sw=2 ai 149#endif 150