How implement a custom std collection in C++?

Question

I want to implement a custom collection data structure in std style. There is already a similar question on this site, but this guy is explicitly asking about not using any given std functionality.

The implementation should be compatible with the rest of the standard library and provide the same interface, for example iterators and type traits. Which base class should I inherit from and what does my class have to implement?

To provide information about the actual data structure, it is a hash map which values are stored continuously in memory. Internally, I will use two std::vectors and one std::unordered_map.

There's also this: http://stackoverflow.com/questions/7758580/writing-your-own-stl-container?lq=1 — chris, Mar 10 '14 at 12:02
You'll have to study C++ standard, chapters `[container.requirements.general]` and `[unord.req]` with its subclause. — jrok, Mar 10 '14 at 12:03

score 2 · Accepted Answer · answered Mar 10 '14 at 12:02

Which base class should I inherit from

None. Standard containers are not polymorphic; their interface requirements are informally specified in terms of expressions that must be supported. (In the future, they might be formally specified as "concepts"; but that's not part of the language yet.)

what does my class have to implement?

See the [container.requirements] section of the C++ standard (currently section 23.2 of C++11); in particular the tables specifying the operations that various container types must support. As a hash map, it should support the requirements for "unordered associative containers".

score 1 · Answer 2 · edited May 23 '17 at 11:48

Start with an interface similar to this:

template <
    typename Key,
    typename T,
    class Hash = hash<Key>,
    class Pred = equal_to<Key>,
    class AllocH = allocator< pair<const Key,T> >,  // unordered_map allocator
    class AllocV = allocator<T> > // vector allocator
class hash_map {
public:
  typedef std::pair<Key, T> value_type;

private:
  using first_index = std::vector<T>; // C++11 typedef substitute syntax
  using second_index = std::unordered_map<Key, T>;

public:          
  using first_index_iterator = typename first_index::iterator;
  using second_index_iterator = typename second_index::iterator;      
  //defaults
  using iterator = first_index_iterator;
  using const_iterator = first_index_const_iterator;

  iterator begin();
  const_iterator begin() const;

  iterator end();
  const_iterator end() const;

  bool empty() const;

  iterator find(const Key&);
  const_iterator find(const Key&) const;

  std::pair<iterator, bool> insert(const value_type&);
  void erase(iterator);  
  void clear();    
};

You are not supposed to add your collections to the std namespace, however if you proceed nevertheless, I strongly suggest you use namespace versioning when you publish your library headers:

// hash_map.hpp
namespace std 
{
  namespace ex_v1  // my std namespace extensions v1
  {
      template <...> class hash_map { ... }    
  }

  using namespace ex_v1;
}

and further, consider the new inline versioning feature of C++11:

What are inline namespaces for?

Thanks a lot for your answer. I actually need two iterators. One that contains just the value and simply iterates over the vector, and another containing key and value by looking up the key in a lookup table. Is there a preferred way of providing two iterators? I could either think of adding boolean flags to `begin()` and `end()` or implementing alternatives to these functions under different names. — danijar, Mar 10 '14 at 13:20
@danijar You will probably want to formalise the notion of indices that one can use to access your container, the iterators are merely a derivative. In any event, I've updated the answer with a smallish sample of how it could look like in the simplest of cases, where indices are just direct mappings of the underlying containers. — mockinterface, Mar 11 '14 at 10:55

How implement a custom std collection in C++?

2 Answers2