From d9ebc5991be6fcbaf8231039d7403ff663005fe9 Mon Sep 17 00:00:00 2001 From: "Duncan P. N. Exon Smith" Date: Tue, 15 Jul 2014 18:32:30 +0000 Subject: [PATCH 1/1] ADT: Fix MapVector::erase() Actually update the changed indexes in the map portion of `MapVector` when erasing from the middle. Add a unit test that checks for this. Note that `MapVector::erase()` is a linear time operation (it was and still is). I'll commit a new method in a moment called `MapVector::remove_if()` that deletes multiple entries in linear time, which should be slightly less painful. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@213084 91177308-0d34-0410-b5e6-96231b3b80d8 --- docs/ProgrammersManual.rst | 2 +- include/llvm/ADT/MapVector.h | 20 +++++++++++++++++--- unittests/ADT/MapVectorTest.cpp | 15 +++++++++++++++ 3 files changed, 33 insertions(+), 4 deletions(-) diff --git a/docs/ProgrammersManual.rst b/docs/ProgrammersManual.rst index a7b28b36ca1..e828e6bf501 100644 --- a/docs/ProgrammersManual.rst +++ b/docs/ProgrammersManual.rst @@ -1442,7 +1442,7 @@ iteration over maps of pointers. It is implemented by mapping from key to an index in a vector of key,value pairs. This provides fast lookup and iteration, but has two main drawbacks: The -key is stored twice and it doesn't support removing elements. +key is stored twice and removing elements takes linear time. .. _dss_inteqclasses: diff --git a/include/llvm/ADT/MapVector.h b/include/llvm/ADT/MapVector.h index a89f4a76e44..0fa68245ff4 100644 --- a/include/llvm/ADT/MapVector.h +++ b/include/llvm/ADT/MapVector.h @@ -125,12 +125,26 @@ 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; } }; diff --git a/unittests/ADT/MapVectorTest.cpp b/unittests/ADT/MapVectorTest.cpp index 11178bc15e8..dd84e7ebd13 100644 --- a/unittests/ADT/MapVectorTest.cpp +++ b/unittests/ADT/MapVectorTest.cpp @@ -53,3 +53,18 @@ TEST(MapVectorTest, insert_pop) { EXPECT_EQ(MV[1], 2); EXPECT_EQ(MV[4], 7); } + +TEST(MapVectorTest, erase) { + MapVector MV; + + MV.insert(std::make_pair(1, 2)); + MV.insert(std::make_pair(3, 4)); + MV.insert(std::make_pair(5, 6)); + ASSERT_EQ(MV.size(), 3u); + + MV.erase(MV.find(1)); + ASSERT_EQ(MV.size(), 2u); + ASSERT_EQ(MV.find(1), MV.end()); + ASSERT_EQ(MV[3], 4); + ASSERT_EQ(MV[5], 6); +} -- 2.34.1