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
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:
}
/// \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;
}
};
EXPECT_EQ(MV[1], 2);
EXPECT_EQ(MV[4], 7);
}
+
+TEST(MapVectorTest, erase) {
+ MapVector<int, int> 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);
+}