Concurrent data structures IMO are those that take advantage of their concurrency and (subtly) alter their behavior for +performance above and beyond what is po

Concurrent data structures IMO are those that take advantage of their concurrency and (subtly) alter their behavior for +performance above and beyond what is possible with simple locks. For example: Count / size() can be imprecise in the realm of concurrency. No need to exactly count the HashTable. It's impossible to get the size of this table exactly, because the shards are each at best one atomic and no shared lock exists between them. Adding up their individual counts (even if implemented as seq-cst atomics) is incorrect as an atomic is only globally correct within its own atomic operation. And there's no way to atomically gather all the shards sizes without a global lock. Feature complete would similarly be: all the features you'd expect, except those annoying low performance ones.