1 //===- llvm/ADT/SetVector.h - Set with insert order iteration ---*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
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.
8 //===----------------------------------------------------------------------===//
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.
15 //===----------------------------------------------------------------------===//
17 #ifndef LLVM_ADT_SETVECTOR_H
18 #define LLVM_ADT_SETVECTOR_H
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.
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;
44 /// @brief Construct an empty SetVector
47 /// @brief Initialize a SetVector with a range of elements
49 SetVector(It Start, It End) {
53 /// @brief Determine if the SetVector is empty or not.
55 return vector_.empty();
58 /// @brief Determine the number of elements in the SetVector.
59 size_type size() const {
60 return vector_.size();
63 /// @brief Get an iterator to the beginning of the SetVector.
65 return vector_.begin();
68 /// @brief Get a const_iterator to the beginning of the SetVector.
69 const_iterator begin() const {
70 return vector_.begin();
73 /// @brief Get an iterator to the end of the SetVector.
78 /// @brief Get a const_iterator to the end of the SetVector.
79 const_iterator end() const {
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();
89 /// @brief Index into the SetVector.
90 const_reference operator[](size_type n) const {
91 assert(n < vector_.size() && "SetVector access out of range!");
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;
100 vector_.push_back(X);
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);
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 = std::find(vector_.begin(),vector_.end(),X);
116 assert(I != vector_.end() && "Corrupted SetVector instances!");
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);
128 /// @brief Completely clear the SetVector
134 /// @brief Remove the last element of the SetVector.
136 assert(!empty() && "Cannot remove an element from an empty SetVector!");
142 set_type set_; ///< The set.
143 vector_type vector_; ///< The vector.
146 } // End llvm namespace