What Data Structure Is Inside Std::Map in C++

What is the underlying structure of an std::map?

1. The underlying data structure is implementation-defined. It is most commonly implemented as a Red-Black tree which is a self-balancing binary search tree. The time complexity for getting an element is O(logn) (see this)

2. I would just read the implementation of std::unordered_map as a starting point. I assume this is learning activity so reading and understanding working STL implementation would be a good exercise. If it's not an exercise then use std::unordered_map

What is the map data structure in C++

std::unordered_map uses hashing to store its objects.

Map like structure in C: use int and struct to determine a value

You'll probably have to make your own structure. The C Programming Language by Kernighan and Ritchie has an example of making an associate map in c, and what I'll detail below is based on what I remember from that.

Basically you'll need a struct Map that contains struct Key and struct Value.

struct Map {
    struct Key key;
    struct Value value;
};

struct Key contains elements that determine the value (in your case 2 points and 2 ints)

struct Key {
    struct point p1;
    struct point p2;
    int i;
    int j;
};

struct Value is whatever you want your key to point to (you didn't say)

You now have a struct Map that associates your four inputs with a value, but a single map isn't that useful. You're going to want a whole array of them.

struct Map map[SIZE_OF_MAP];

If you don't want to linearly search the array for the Map struct you're looking for, you can make a hashing function that will bring you directly to it. Just define a function that takes the key and uses its value to assign it an index in the array. Use the hash to place the Map in the array and retrieve it from the array. (Note: I'm unsure if this is a correct example of hashing, please correct if this is completely wrong)

int get_hash(Key *key)
{
    int result;
    /* combine all inputs in some way */
    result = key->i * key->i + (key->p1.x * key->p1.x) - (key->p2.x * key->p2.x)
    /* make sure result isn't out of bounds of the array */
    return (result % SIZE_OF_MAP);
}

If you use the hashing function you'll have to consider collisions (what happens when two keys give the same result for get_hash). When you use your array of Maps you'll need some form of collision resolution.

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.

Struct containing a Map in a Map? (C++/STL)

I was wondering if it was possible to
create a struct containing a number of
variables and a map in a map

Yes. It is possible to have Map as value inside another map.

If you are particular about the order of insertion and the entries are less for inner map then your data structure can looks like:

typedef std::vector<std::pair<std::string,double> > lawVariables;  

struct ObjectCustomData {   
  std::string objectType;    
  bool global_lock;   
  std::map<std::string, lawVariables> lawData;   
 };

EDIT:
I saw your edit now. If lookup is your primary requirement then go for map.

Example:

 typedef std::map<std::string,double> lawVariables;  

    struct ObjectCustomData {   
      std::string objectType;    
      bool global_lock;   
      std::map<std::string, lawVariables> lawData;   
     };

void test(ObjectCustomData& data)
{
  lawVariables& variable = data.lawData["law_1"];
  variable["var_a"] = 39.3;

}

What is a Map and how would I use one in C++?

If you mean std::map, it stores pairs of values. In each pair, the first value is called the key, and can be used to quickly look up the associated other value.

You can write:

std::map<std::string, int> ages;
ages["Fred"] = 52;
ages["Sue"] = 31;

std::cout << "Fred's age is " << ages["Fred"] << std::endl;

C++ data structure similar to std::map with multiple key levels

I'd suggest Boost MultiIndex with composite_key https://www.boost.org/doc/libs/1_67_0/libs/multi_index/doc/tutorial/key_extraction.html

Here's a recent example I gave using it:

• equal_range in boost::Multi_Indexed_Container Composite key with comparision operator

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.

---

Related Topics