Is there a C++ container for unique values that supports strict size checking?

Question

I'm looking for a C++ container to store pointers to objects which also meets the following requirements.

A container that keeps the order of elements (sequence container, so std::set is not suitable)
A container that has a member function which return the actual size (As std::array::size() always returns the fixed size, std::array is not suitable)
A container that supports random accesses such as operator [].

This is my code snippet and I'd like to remove the assertions used for checking size and uniqueness of elements.

#include <vector>
#include <set>
#include "assert.h"

class Foo {
  public:
    void DoSomething() {
    }
};

int main() {
  // a variable used to check whether a container is properly assigned
  const uint8_t size_ = 2; 

  Foo foo1;
  Foo foo2;

  // Needs a kind of sequential containers to keep the order
  // used std::vector instead of std::array to use member function size()
  const std::vector<Foo*> vec = {
    &foo1,
    &foo2
  };

  std::set<Foo*> set_(vec.begin(), vec.end()); 
  assert(vec.size() == size_); // size checking against pre-defined value
  assert(vec.size() == set_.size()); // check for elements uniqueness

  // Needs to access elements using [] operator
  for (auto i = 0; i < size_; i++) {
    vec[i]->DoSomething();
  }

  return 0;
}

Is there a C++ container which doesn't need two assertions used in my code snippet? Or should I need to make my own class which encapsulates one of STL containers?

So an [*unordered* set](http://en.cppreference.com/w/cpp/container/unordered_set) perhaps? — Some programmer dude, Dec 13 '17 at 11:25
You want `std::map`: it keeps order, is dynamic, has unique elements and is sequential by iteration. — Jodocus, Dec 13 '17 at 11:26
I also suggest you take some time to read [about the XY problem](https://meta.stackexchange.com/questions/66377/what-is-the-xy-problem), and reflect about how this question might be one, and how you could improve it. — Some programmer dude, Dec 13 '17 at 11:26
Ah, I guess it is the uniqueness of the entries that is the issue? Unfortunately, that was only in the title, so easily missed. Use a hash to manage the uniqueness alongside a vector to manage the indexing. Wrap it all up in an object that exposes the set insert method, but vector for everything else. Possibly derive from vector to get the exposure. — Gem Taylor, Dec 13 '17 at 11:32
Your claim that `std::array` does not meet your requirements seems ..... artificial. `std::array` doesn't need an assertion concerning size, since the size is specified at compile time. It's size method returns the actual size. And it won't change order of elements unless you force it to (e.g. by use of an algorithm that changes order). And it supports random access using `[]`. Similar comments can also be made about `std::vector`. — Peter, Dec 13 '17 at 11:35
@Rene As I have to use a bunch of this kind of containers for various kinds of object, I want to avoid using repetitive assertions. — Han, Dec 13 '17 at 11:48
@Someprogrammerdude As far as I know, [std::unordered_set](http://en.cppreference.com/w/cpp/container/unordered_set) stores elements in arbitrary order, I want one that I can specify the order. — Han, Dec 13 '17 at 11:52
@Peter The _actual size_ I meant was some kind of occupancies. `std::array::size()` doesn't check whether the array is tightly fits. I want some kinds of methods to check a container is filled without invalid elements. — Han, Dec 13 '17 at 12:03
Looks like what you want is something that wraps a vector, with a `push_back`, `[] operator` and anything else you need - and it performs the unique check itself; or wraps a set, and then performs the random access operations itself — UKMonkey, Dec 13 '17 at 12:03
@UKMonkey Yes, that is what I need. Actually, I don't need `push_back()` since I will use it as constant. — Han, Dec 13 '17 at 12:07
@Han - what do you mean byu "array is tightly fits"? If you want to check if a container contains (or doesn't contain) invalid elements, then you need to (1) specify what makes an element invalid and (2) code the check of the array manually. It would probably be better to prevent "invalid" elements being added. No standard container has a concept of an element which is invalid - either it has a specified size (in which case all elements are "valid") or it doesn't. Whether you wrap such checks of validity of elements in a class or not is an implementation choice. — Peter, Dec 13 '17 at 12:08
@Han doesn't exist in the stl; the best I can think of is a set that has a comparison operator based on the order the item was added to the set (and the rest of the data); but it's nasty because you're building knowledge of the container into the object that will be contained. Best just make your own class — UKMonkey, Dec 13 '17 at 12:09
@Jodocus As you pointed out elements of `std::map` are unique but it doesn't evaluate the values are unique. — Han, Dec 13 '17 at 12:19
Thank you all for your comments. I think all these confusions come from my ambiguous expressions. Sorry for the confusion, and I will edit the post if anyone suggests. — Han, Dec 13 '17 at 12:23
@Han, there is no confusion, you are looking for std::vector. If you want it sorted, use std::upper_bound() to get the insertion spot for element when pushing. — Michaël Roy, Dec 13 '17 at 12:35
I don't think the STL provides a decent solution to your problem, you should try to implement your own based on two members (integer, set). — Vivick, Dec 13 '17 at 15:29

score 0 · Answer 1 · answered Dec 13 '17 at 15:10

So a class that acts like a vector except if you insert, it rejects duplicates like a set or a map.

One option might be the Boost.Bimap with indices of T* and sequence_index. Your vector-like indexing would be via the sequence_index. You might even be willing to live with holes in the sequence after an element is erased.

Sticking with STLyou could implement a bidirectional map using 2 maps, or the following uses a map and a vector:

Note that by inheriting from vector I get all the vector methods for free, but I also risk the user downcasting to the vector.
One way round that without remodelling with a wrapper (a la queue vs list) is to make it protected inheritance and then explicitly using all the methods back to public. This is actually safer as it ensures you haven't inadvertently left some vector modification method live that would take the two containers out of step.

Note also that you would need to roll your own initializer_list constructor if you wanted one to filter out any duplicates. And you would have to do a bit of work to get this thread-safe.

template <class T>
class uniqvec : public std::vector<T*>
{
private:
    typedef typename std::vector<T*> Base;
    enum {push_back, pop_back, emplace_back, emplace}; //add anything else you don't like from vector
std::map <T*, size_t> uniquifier;
public:

    std::pair<typename Base::iterator, bool> insert(T* t)
    {
        auto rv1 = uniquifier.insert(std::make_pair(t, Base::size()));
        if (rv1.second)
        {
            Base::push_back(t);
        }
        return std::make_pair(Base::begin()+rv1.first.second, rv1.second);
    }
    void erase(T* t)
    {
        auto found = uniquifier.find(t);
        if (found != uniquifier.end())
        {
            auto index = found->second;
            uniquifier.erase(found);
            Base::erase(Base::begin()+index);
            for (auto& u : uniquifier)
                if (u.second > index)
                    u.second--;
        }
    }
    // Note that c++11 returns the next safe iterator,
    // but I don't know if that should be in vector order or set order.
    void erase(typename Base::iterator i)
    {
        return erase(*i);
    }
};

score 0 · Answer 2 · answered Dec 13 '17 at 15:35

As others have mentioned, your particular questions seems like the XY problem (you are down in the weeds about a particular solution instead of focusing on the original problem). There was an extremely useful flowchart provided here a number of years ago (credit to @MikaelPersson) that will help you choose a particular STL container to best fit your needs. You can find the original question here In which scenario do I use a particular STL container?.

Is there a C++ container for unique values that supports strict size checking?

2 Answers2