cc: Add RandomAccessListContainer, which has more restricted API.

cc/base/list_container.h

Index: cc/base/list_container.h
diff --git a/cc/base/list_container.h b/cc/base/list_container.h
index c5952a1a2bf8a77c4121d98caadcb48e7241d9cc..5f8bbfa41f5813bfba00ecbc0aecc88d37464f8b 100644
--- a/cc/base/list_container.h
+++ b/cc/base/list_container.h
@@ -5,6 +5,8 @@
 #ifndef CC_BASE_LIST_CONTAINER_H_
 #define CC_BASE_LIST_CONTAINER_H_
 
+#include <deque>
+
 #include "base/logging.h"
 #include "base/macros.h"
 #include "base/memory/scoped_ptr.h"
@@ -29,6 +31,9 @@ class CC_EXPORT ListContainerHelper {
   template <typename T>
   friend class CC_EXPORT ListContainer;
 
+  template <typename T>
+  friend class CC_EXPORT RandomAccessListContainer;
+
   explicit ListContainerHelper(size_t max_size_for_derived_class);
   ListContainerHelper(size_t max_size_for_derived_class,
                       size_t num_of_elements_to_reserve_for);
@@ -501,6 +506,73 @@ class CC_EXPORT ListContainer {
   ListContainerHelper helper_;
 };
 
+template <class BaseElementType>
+class CC_EXPORT RandomAccessListContainer {
+ public:
+  // BaseElementType is the type of raw pointers this class hands out; however,
+  // its derived classes might require different memory sizes.
+  // max_size_for_derived_class the largest memory size required for all the
+  // derived classes to use for allocation.
+  explicit RandomAccessListContainer(size_t max_size_for_derived_class)
+      : helper_(max_size_for_derived_class) {}
+
+  // This constructor omits input variable for max_size_for_derived_class. This
+  // is used when there is no derived classes from BaseElementType we need to
+  // worry about, and allocation size is just sizeof(BaseElementType).
+  RandomAccessListContainer() : helper_(sizeof(BaseElementType)) {}
+
+  // This constructor reserves the requested memory up front so only single
+  // allocation is needed. When num_of_elements_to_reserve_for is zero, use the
+  // default size.
+  RandomAccessListContainer(size_t max_size_for_derived_class,
+                            size_t num_of_elements_to_reserve_for)
+      : helper_(max_size_for_derived_class, num_of_elements_to_reserve_for) {}
+
+  ~RandomAccessListContainer() {
+    for (BaseElementType* item : items_)
+      item->~BaseElementType();
+  }
+
+  void clear() {
+    for (BaseElementType* item : items_)
+      item->~BaseElementType();
+    helper_.clear();
+    items_.clear();
+  }
+
+  bool empty() const { return helper_.empty(); }
+  size_t size() const { return helper_.size(); }
+  size_t GetCapacityInBytes() const { return helper_.GetCapacityInBytes(); }
+
+  template <typename DerivedElementType>
+  DerivedElementType* AllocateAndConstruct() {
+    auto* value =
+        new (helper_.Allocate(sizeof(DerivedElementType))) DerivedElementType;
+    items_.push_back(value);
+    return value;
+  }
+
+  void RemoveLast() {
+    items_.back()->~BaseElementType();
+    items_.pop_back();
+    helper_.RemoveLast();
+  }
+
+  const BaseElementType* operator[](size_t index) const {

[weiliangc, 2015/09/14 20:02:47]

Can you also add at()? Or explain in comment this class doesn't support at?

[vmpstr, 2015/09/15 00:17:48]

I'm not sure why we need at() as well. I assume you mean something similar to
vector::at, which is equivalent to operator[] except it does bounds checking. I
do bounds checking with dchecks in operator[] here. 

+    DCHECK_GE(index, 0u);
+    DCHECK_LT(index, items_.size());
+    return items_[index];
+  }
+
+  using ConstIterator = typename std::deque<BaseElementType*>::const_iterator;

[weiliangc, 2015/09/14 20:02:47]

Seems like only have const access, is this intended? Can you add it to comment?

[vmpstr, 2015/09/15 00:17:48]

Hmm. The const access is to the iterator whose value_type is a BaseElementType*
const, so you technically can still change the value pointed to, you just can't
change the deque directly... That is,

*it = new_ptr; // error
(*it)->base_value = new_base_value; // ok
**it = new_object; // also ok

This is by design, but maybe this mimics more of the non-const ListContainer
iterators?

FWIW, For ListContainers, both const and non-const iterators don't allow *it =
new_ptr;

+  ConstIterator begin() const { return items_.begin(); }
+  ConstIterator end() const { return items_.end(); }
+
+ private:
+  ListContainerHelper helper_;
+  std::deque<BaseElementType*> items_;
+};
+
 }  // namespace cc
 
 #endif  // CC_BASE_LIST_CONTAINER_H_