ART: Add some utilities for working with containers.

Add utility functions for searching, removing and replacing
existing values in a container, to be used with std::vector
(including the ArenaVector alias) and other containers.

Also move UniqueCPtr<> and MakeUnique() to base/stl_utils.h
and clean up related includes.

Change-Id: I1e61762df91c046866591bda167d42bf8b67a692
diff --git a/runtime/base/stl_util.h b/runtime/base/stl_util.h
index 901f25f..0949619 100644
--- a/runtime/base/stl_util.h
+++ b/runtime/base/stl_util.h
@@ -20,6 +20,8 @@
 #include <algorithm>
 #include <sstream>
 
+#include "base/logging.h"
+
 namespace art {
 
 // Sort and remove duplicates of an STL vector or deque.
@@ -94,6 +96,59 @@
   return os.str();
 }
 
+// Deleter using free() for use with std::unique_ptr<>. See also UniqueCPtr<> below.
+struct FreeDelete {
+  // NOTE: Deleting a const object is valid but free() takes a non-const pointer.
+  void operator()(const void* ptr) const {
+    free(const_cast<void*>(ptr));
+  }
+};
+
+// Alias for std::unique_ptr<> that uses the C function free() to delete objects.
+template <typename T>
+using UniqueCPtr = std::unique_ptr<T, FreeDelete>;
+
+// C++14 from-the-future import (std::make_unique)
+// Invoke the constructor of 'T' with the provided args, and wrap the result in a unique ptr.
+template <typename T, typename ... Args>
+std::unique_ptr<T> MakeUnique(Args&& ... args) {
+  return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
+}
+
+// Find index of the first element with the specified value known to be in the container.
+template <typename Container, typename T>
+size_t IndexOfElement(const Container& container, const T& value) {
+  auto it = std::find(container.begin(), container.end(), value);
+  DCHECK(it != container.end());  // Must exist.
+  return std::distance(container.begin(), it);
+}
+
+// Remove the first element with the specified value known to be in the container.
+template <typename Container, typename T>
+void RemoveElement(Container& container, const T& value) {
+  auto it = std::find(container.begin(), container.end(), value);
+  DCHECK(it != container.end());  // Must exist.
+  container.erase(it);
+}
+
+// Replace the first element with the specified old_value known to be in the container.
+template <typename Container, typename T>
+void ReplaceElement(Container& container, const T& old_value, const T& new_value) {
+  auto it = std::find(container.begin(), container.end(), old_value);
+  DCHECK(it != container.end());  // Must exist.
+  *it = new_value;
+}
+
+// Search for an element with the specified value and return true if it was found, false otherwise.
+template <typename Container, typename T>
+bool ContainsElement(const Container& container, const T& value, size_t start_pos = 0u) {
+  DCHECK_LE(start_pos, container.size());
+  auto start = container.begin();
+  std::advance(start, start_pos);
+  auto it = std::find(start, container.end(), value);
+  return it != container.end();
+}
+
 }  // namespace art
 
 #endif  // ART_RUNTIME_BASE_STL_UTIL_H_
diff --git a/runtime/dex_file.cc b/runtime/dex_file.cc
index 5526883..a2af9d0 100644
--- a/runtime/dex_file.cc
+++ b/runtime/dex_file.cc
@@ -31,6 +31,7 @@
 #include "art_method-inl.h"
 #include "base/hash_map.h"
 #include "base/logging.h"
+#include "base/stl_util.h"
 #include "base/stringprintf.h"
 #include "class_linker-inl.h"
 #include "dex_file-inl.h"
diff --git a/runtime/runtime.cc b/runtime/runtime.cc
index 4797564..3119cce 100644
--- a/runtime/runtime.cc
+++ b/runtime/runtime.cc
@@ -57,6 +57,7 @@
 #include "atomic.h"
 #include "base/arena_allocator.h"
 #include "base/dumpable.h"
+#include "base/stl_util.h"
 #include "base/unix_file/fd_file.h"
 #include "class_linker-inl.h"
 #include "compiler_callbacks.h"
@@ -129,6 +130,7 @@
 #include "thread_list.h"
 #include "trace.h"
 #include "transaction.h"
+#include "utils.h"
 #include "verifier/method_verifier.h"
 #include "well_known_classes.h"
 
diff --git a/runtime/utils.h b/runtime/utils.h
index 16835c2..3e61824 100644
--- a/runtime/utils.h
+++ b/runtime/utils.h
@@ -294,25 +294,6 @@
   buf->push_back((data >> 24) & 0xff);
 }
 
-// Deleter using free() for use with std::unique_ptr<>. See also UniqueCPtr<> below.
-struct FreeDelete {
-  // NOTE: Deleting a const object is valid but free() takes a non-const pointer.
-  void operator()(const void* ptr) const {
-    free(const_cast<void*>(ptr));
-  }
-};
-
-// Alias for std::unique_ptr<> that uses the C function free() to delete objects.
-template <typename T>
-using UniqueCPtr = std::unique_ptr<T, FreeDelete>;
-
-// C++14 from-the-future import (std::make_unique)
-// Invoke the constructor of 'T' with the provided args, and wrap the result in a unique ptr.
-template <typename T, typename ... Args>
-std::unique_ptr<T> MakeUnique(Args&& ... args) {
-  return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
-}
-
 inline bool TestBitmap(size_t idx, const uint8_t* bitmap) {
   return ((bitmap[idx / kBitsPerByte] >> (idx % kBitsPerByte)) & 0x01) != 0;
 }
diff --git a/runtime/verifier/method_verifier.cc b/runtime/verifier/method_verifier.cc
index bba9c5e..1d71c3f 100644
--- a/runtime/verifier/method_verifier.cc
+++ b/runtime/verifier/method_verifier.cc
@@ -22,6 +22,7 @@
 #include "art_method-inl.h"
 #include "base/logging.h"
 #include "base/mutex-inl.h"
+#include "base/stl_util.h"
 #include "base/time_utils.h"
 #include "class_linker.h"
 #include "compiler_callbacks.h"
diff --git a/runtime/verifier/method_verifier.h b/runtime/verifier/method_verifier.h
index b57abf5..0295ef8 100644
--- a/runtime/verifier/method_verifier.h
+++ b/runtime/verifier/method_verifier.h
@@ -18,6 +18,7 @@
 #define ART_RUNTIME_VERIFIER_METHOD_VERIFIER_H_
 
 #include <memory>
+#include <sstream>
 #include <vector>
 
 #include "base/macros.h"
diff --git a/runtime/verifier/reg_type_cache.cc b/runtime/verifier/reg_type_cache.cc
index e14306c..bb756e9 100644
--- a/runtime/verifier/reg_type_cache.cc
+++ b/runtime/verifier/reg_type_cache.cc
@@ -17,6 +17,7 @@
 #include "reg_type_cache-inl.h"
 
 #include "base/casts.h"
+#include "base/stl_util.h"
 #include "class_linker-inl.h"
 #include "dex_file-inl.h"
 #include "mirror/class-inl.h"
diff --git a/runtime/verifier/reg_type_cache.h b/runtime/verifier/reg_type_cache.h
index 8319de6..93948a1 100644
--- a/runtime/verifier/reg_type_cache.h
+++ b/runtime/verifier/reg_type_cache.h
@@ -19,7 +19,6 @@
 
 #include "base/casts.h"
 #include "base/macros.h"
-#include "base/stl_util.h"
 #include "object_callbacks.h"
 #include "reg_type.h"
 #include "runtime.h"