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
25 /// This class provides a way to keep a set of things that also has the
26 /// property of a deterministic iteration order. The order of iteration is the
27 /// order of insertion.
28 /// @breif 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 Completely clear the SetVector
49 /// @brief Determine if the SetVector is empty or not.
51 return vector_.empty();
54 /// @brief Determine the number of elements in the SetVector.
55 size_type size() const {
56 return vector_.size();
59 /// @brief Get an iterator to the beginning of the SetVector.
61 return vector_.begin();
64 /// @brief Get a const_iterator to the beginning of the SetVector.
65 const_iterator begin() const {
66 return vector_.begin();
69 /// @brief Get an iterator to the end of the SetVector.
74 /// @brief Get a const_iterator to the end of the SetVector.
75 const_iterator end() const {
79 /// @brief Index into the SetVector.
80 const_reference operator[](size_type n) const {
84 /// @returns true iff the element was inserted into the SetVector.
85 /// @brief Insert a new element into the SetVector.
86 bool insert( const value_type& X ) {
87 std::pair<typename set_type::iterator,bool> insertion_result = set_.insert(X);
88 if ( insertion_result.second ) {
91 return insertion_result.second;
94 /// @returns 0 if the element is not in the SetVector, 1 if it is.
95 /// @brief Count the number of elements of a given key in the SetVector.
96 size_type count( const key_type& key ) const {
97 return set_.count(key);
101 set_type set_; ///< The set.
102 vector_type vector_; ///< The vector.
105 } // End llvm namespace