diff options
Diffstat (limited to 'include/llvm/ADT/MapVector.h')
-rw-r--r-- | include/llvm/ADT/MapVector.h | 87 |
1 files changed, 67 insertions, 20 deletions
diff --git a/include/llvm/ADT/MapVector.h b/include/llvm/ADT/MapVector.h index 2eae22c..14c49c5 100644 --- a/include/llvm/ADT/MapVector.h +++ b/include/llvm/ADT/MapVector.h @@ -37,26 +37,20 @@ class MapVector { public: typedef typename VectorType::iterator iterator; typedef typename VectorType::const_iterator const_iterator; + typedef typename VectorType::reverse_iterator reverse_iterator; + typedef typename VectorType::const_reverse_iterator const_reverse_iterator; - size_type size() const { - return Vector.size(); - } - - iterator begin() { - return Vector.begin(); - } - - const_iterator begin() const { - return Vector.begin(); - } + size_type size() const { return Vector.size(); } - iterator end() { - return Vector.end(); - } + iterator begin() { return Vector.begin(); } + const_iterator begin() const { return Vector.begin(); } + iterator end() { return Vector.end(); } + const_iterator end() const { return Vector.end(); } - const_iterator end() const { - return Vector.end(); - } + reverse_iterator rbegin() { return Vector.rbegin(); } + const_reverse_iterator rbegin() const { return Vector.rbegin(); } + reverse_iterator rend() { return Vector.rend(); } + const_reverse_iterator rend() const { return Vector.rend(); } bool empty() const { return Vector.empty(); @@ -125,15 +119,68 @@ public: } /// \brief Remove the element given by Iterator. + /// /// Returns an iterator to the element following the one which was removed, /// which may be end(). + /// + /// \note This is a deceivingly expensive operation (linear time). It's + /// usually better to use \a remove_if() if possible. typename VectorType::iterator erase(typename VectorType::iterator Iterator) { - typename MapType::iterator MapIterator = Map.find(Iterator->first); - Map.erase(MapIterator); - return Vector.erase(Iterator); + Map.erase(Iterator->first); + auto Next = Vector.erase(Iterator); + if (Next == Vector.end()) + return Next; + + // Update indices in the map. + size_t Index = Next - Vector.begin(); + for (auto &I : Map) { + assert(I.second != Index && "Index was already erased!"); + if (I.second > Index) + --I.second; + } + return Next; } + + /// \brief Remove all elements with the key value Key. + /// + /// Returns the number of elements removed. + size_type erase(const KeyT &Key) { + auto Iterator = find(Key); + if (Iterator == end()) + return 0; + erase(Iterator); + return 1; + } + + /// \brief Remove the elements that match the predicate. + /// + /// Erase all elements that match \c Pred in a single pass. Takes linear + /// time. + template <class Predicate> void remove_if(Predicate Pred); }; +template <typename KeyT, typename ValueT, typename MapType, typename VectorType> +template <class Function> +void MapVector<KeyT, ValueT, MapType, VectorType>::remove_if(Function Pred) { + auto O = Vector.begin(); + for (auto I = O, E = Vector.end(); I != E; ++I) { + if (Pred(*I)) { + // Erase from the map. + Map.erase(I->first); + continue; + } + + if (I != O) { + // Move the value and update the index in the map. + *O = std::move(*I); + Map[O->first] = O - Vector.begin(); + } + ++O; + } + // Erase trailing entries in the vector. + Vector.erase(O, Vector.end()); } +} // end namespace llvm + #endif |