What Is the Underlying Data Structure of a Stl Set in C++

What is the underlying data structure of a STL set in C++?

You could implement a binary search tree by first defining a Node struct:

struct Node
{
  void *nodeData;
  Node *leftChild;
  Node *rightChild;
}

Then, you could define a root of the tree with another Node *rootNode;

The Wikipedia entry on Binary Search Tree has a pretty good example of how to implement an insert method, so I would also recommend checking that out.

In terms of duplicates, they are generally not allowed in sets, so you could either just discard that input, throw an exception, etc, depending on your specification.

what is underlying data structure of STL list, vector and set?

Based on comments, to clarify, these are the most common choices, but based on desired complexity and other factors, the backing of these implementations may vary:

Vector = dynamically resizing array

List = Doubly Linked List

Set = Red/Black Tree (balanced Binary Search Tree)

I think you might possibly be mixing up Heaps and BSTs. A heap is visualized as a tree, but it's actually built on top of an indexable list structure (e.g. array or vector). C++ provides heap functions via the algorithm header in the STL . BSTs are more of a key/value based structure used for efficient lookup (which is what you generally want for a set).

How is the STL set/map internally sorted?

For both std::map and std::set, it is implementation defined how the sorting is being done. The underlying data structure should sort the elements somehow:

Internally, the elements in a map are always sorted by its key following a specific strict weak ordering criterion indicated by its internal comparison object (of type Compare).

(same holds for set.)

A typical data structure for these containers is red black tree or a binary search tree.

Data structures equivalents of STL containers

Concering the C++ standard library containers, the standard itself tries not to say too much about implementation. However, the very specific constraints on complexity of insertion, removal, look-up, range insertion and so on, mean that most implementations use the same types of data structures for the containers. Concerning some of your examples:

• std::list : doubly linked list
• std::set, std::multiset, std::map, std::multimap: self-balancing
  binary trees, typically red-blacktrees.
• hash_*: C++11 provides unordered_set, unordered_map and multi
  siblings. These are hash tables.
• bitset: fixed-size array

I believe the STL follows these implementations.

What is the set-like data structure in c++

There is a standard library container called std::set... I don't know delphi, but a simple element in set operation would be implemented by using the find method and comparing the result with end:

std::set<int> s;
s.insert( 5 );
if ( s.find( 5 ) != s.end() ) {
   // 5 is in the set
}

Other operations might be implemented as algorithms in the standard library (std::union, std::difference... )

C++ STL set implementation

Because C++ sets are ordered by the T's comparison operator, which makes it possible to iterate over the members in a predictable way. If you know that all you will do with the set is insert, test membership, and/or remove elements, then std::unordered_set, which implements a hashset, exists for that since C++11.

---

Related Topics