2

enter image description here

1. If Queue is basically a 'linked list' it should be the Associative type and Deque should be also a Associated type as well, as both these Abstract data types fit in that category. Why is Queue a 'Adapter type' and Deque-'Sequential' type? Why are the types being mixed with other definitions?

2. Why is Stack an Adapter Type? Is it because it follows a Wrapper Pattern and stores flags?

Also If I am not making sense or am technically incorrect can you point it out?

EDIT: My definition of a Associative Type: http://en.wikipedia.org/wiki/Associative_array - Go see Implementation Tab and the first sentence you will see 'linked list' data structures.

Jebathon
  • 4,310
  • 14
  • 57
  • 108
  • What is your definition of Associative type ? – taocp Aug 16 '13 at 18:59
  • You are probably talking about the [C++ standard library, not the STL](http://stackoverflow.com/questions/5205491/whats-this-stl-vs-c-standard-library-fight-all-about/5205571#5205571). –  Aug 16 '13 at 19:00
  • I can explain Queue: in the STL, the "queue" data structure places a wrapper around a different type (by default dequeue) so that you can only add objects to the beginning and remove them from the end. It could be a vector, linked list, or whatever you want. – IdeaHat Aug 16 '13 at 19:00
  • Likewise with std::stack and `std::priority_queue`. – WhozCraig Aug 16 '13 at 19:12
  • @H2CO3: In this particular case he might be talking about the STL, as all the types mentioned here do belong to the STL. – David Rodríguez - dribeas Aug 16 '13 at 19:12

1 Answers1

2

I think you don't know what the word "associative" means. Associative types associate one set of data with another. Like names to people, so you can find a person by looking up their name. deque could be called_similar_ to a linked list, which is just a sequence of objects, so it is a sequential container. There's no object association going on. Also keep in mind, the category is based on the interface, not the implementation.

I disagree with the use of "Adaptor" as a category, realistically, the adaptors give sequential containers a new interface, so that they no longer behave like containers and instead behave like something else entirely. Namely, a queue, priority queue, or a stack. Again, Adaptors do not fulfill the container interface. (Though they can still be considered containers, depending on your definition)

Despite the names, deque and queue have nothing in common. The first is a sequential container that is optimized for pushing and popping at either end, but can do anything a vector can do. queue is an interface for objects in a queue.

As a note, your list is missing the C++11 containers: array and forward_list are new sequential containers, unordered_map, unordered_multimap, unordered_set, and unordered_multiset are new associative containers. There are no new container adaptors.

Mooing Duck
  • 64,318
  • 19
  • 100
  • 158