Hybrid vector / container list?

Question

I need a container that has the properties of both a vector and a list. I need quick random access to items in a container, but I also need to be able to delete items in the middle of the container without moving other items. I should also be able to iterate through all the elements in the container and see at a glance (without iteration) how many elements are in the container.

After some thought, I figured out how to create such a container using the vector as the base container, and wrap the actual stored data in a structure that also contains fields for recording whether the element was valid and pointers to the next / previous valid element in the vector. In combination with some overload, etc., It seems that it should be transparent enough and meet my requirements.

But before I actually work on creating another container, I am curious if anyone knows about an existing library that implements just that? I'd rather use something that works than spend time debugging a custom implementation. I looked at the Boost library (which I already use), but did not find it there.

Answer 1

If the order doesn't matter, I would just use hash table integers for pointers. std::tr1::unordered_map<int, T *> (or std::unordered_map<int, unique_ptr<T>> if C ++ 0x is ok).

Elements of the hash table can move around, so you need to use a pointer, but it will support very fast insert / search / delete. Iteration is also very fast, but the elements will come out in an unspecified order.

Alternatively, I think you can implement your idea as a very simple combination of std::vector and std::list . Just maintain both list<T> my_list and vector<list<T>::iterator> my_vector . To add an object, click on the back of my_list , and then click its iterator on my_vector . (Set the iterator to my_list.end() and scale it down to get an iterator for the last item.) To search, search in the vector and just search for the iterator. To remove, remove from the list (which you can do with an iterator) and set the location in the my_list.end() vector.

std::list ensures that items inside will not move when they are deleted.

[update]

I feel motivated. The first pass during implementation:

 #include <vector> #include <list> template <typename T> class NairouList { public: typedef std::list<T> list_t; typedef typename list_t::iterator iterator; typedef std::vector<iterator> vector_t; NairouList() : my_size(0) { } void push_back(const T &elt) { my_list.push_back(elt); iterator i = my_list.end(); --i; my_vector.push_back(i); ++my_size; } T &operator[](typename vector_t::size_type n) { if (my_vector[n] == my_list.end()) throw "Dave not here, man"; return *(my_vector[n]); } void remove(typename vector_t::size_type n) { my_list.erase(my_vector[n]); my_vector[n] = my_list.end(); --my_size; } size_t size() const { return my_size; } iterator begin() { return my_list.begin(); } iterator end() { return my_list.end(); } private: list_t my_list; vector_t my_vector; size_t my_size; }; 

There is a lack of implementation quality ... How do you probably need additional error checking (what if I delete the same element twice?) And, possibly, some versions of const operator[] , begin() , end() . But this is the beginning.

However, for "several thousand" elements, the map is likely to serve, at least as well. A good rule of thumb is: "Never optimize anything until your profiler tells you."

Answer 2

It looks like you might need std :: deque . Removing an element is not as efficient as std::list , but because deque is usually created using non-contiguous blocks of memory that are controlled via an additional pointer array / vector internal to the container (each "block" will be an array of N elements) An element inside a deque does not result in the same shuffle operation that you see with a vector.

Edit: At the same time, and after looking at some comments, although I think std::deque might work, I think that std::map or std::unordered_map will actually be better for you since it will allow you to index array syntax, but it quickly removes elements.