1 //===- SetVector.h - A set with insertion 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 SUPPORT_SETVECTOR_H
18 #define SUPPORT_SETVECTOR_H
26 /// This class provides a way to keep a set of things that also has the
27 /// property of a deterministic iteration order. The order of iteration is the
28 /// order of insertion.
29 /// @brief A vector that has set insertion semantics.
36 typedef const T& const_reference;
37 typedef std::set<value_type> set_type;
38 typedef std::vector<value_type> vector_type;
39 typedef typename vector_type::iterator iterator;
40 typedef typename vector_type::const_iterator const_iterator;
41 typedef typename vector_type::size_type size_type;
43 /// @brief Construct an empty SetVector
46 /// @brief Initialize a SetVector with a range of elements
48 SetVector(It Start, It End) {
52 /// @brief Determine if the SetVector is empty or not.
54 return vector_.empty();
57 /// @brief Determine the number of elements in the SetVector.
58 size_type size() const {
59 return vector_.size();
62 /// @brief Get an iterator to the beginning of the SetVector.
64 return vector_.begin();
67 /// @brief Get a const_iterator to the beginning of the SetVector.
68 const_iterator begin() const {
69 return vector_.begin();
72 /// @brief Get an iterator to the end of the SetVector.
77 /// @brief Get a const_iterator to the end of the SetVector.
78 const_iterator end() const {
82 /// @brief Return the last element of the SetVector.
83 const T &back() const {
84 assert(!empty() && "Cannot call back() on empty SetVector!");
85 return vector_.back();
88 /// @brief Index into the SetVector.
89 const_reference operator[](size_type n) const {
90 assert(n < vector_.size() && "SetVector access out of range!");
94 /// @returns true iff the element was inserted into the SetVector.
95 /// @brief Insert a new element into the SetVector.
96 bool insert(const value_type &X) {
97 bool result = set_.insert(X).second;
103 /// @brief Insert a range of elements into the SetVector.
104 template<typename It>
105 void insert(It Start, It End) {
106 for (; Start != End; ++Start)
107 if (set_.insert(*Start).second)
108 vector_.push_back(*Start);
111 /// @returns 0 if the element is not in the SetVector, 1 if it is.
112 /// @brief Count the number of elements of a given key in the SetVector.
113 size_type count(const key_type &key) const {
114 return set_.count(key);
117 /// @brief Completely clear the SetVector
123 /// @brief Remove the last element of the SetVector.
125 assert(!empty() && "Cannot remove an element from an empty SetVector!");
131 set_type set_; ///< The set.
132 vector_type vector_; ///< The vector.
135 } // End llvm namespace