C++ Data Structures

C++ provides a variety of data structures, ranging from basic ones such as arrays, structs, and classes, to advanced STL containers such asvector、mapandunordered_mapetc.

The following details the commonly used data structures in C++, along with their characteristics and usage.

1. Array

Arrays are the most basic data structures, used to store a set of data of the same type.

Features：

  • Fixed size; once declared, the size cannot be changed.
  • Direct element access with a time complexity of O(1).
  • Suitable for handling collections of known size with identical element types.

Example

int arr[5] = {1, 2, 3, 4, 5};
cout << arr[0]; // Output the first element

Advantages and Disadvantages：

  • Advantage: Fast access speed, compact memory usage.
  • Disadvantages: fixed size, cannot be dynamically expanded, not suitable for datasets of uncertain size.

2. Struct

Structs allow combining different types of data to form a custom data type.

Features：

  • Can contain member variables of different types.
  • Provides basic encapsulation of data, but with limited functionality.

Example：

Example

struct Person {
    string name;
    int age;
};
Person p = {"Alice", 25};
cout << p.name << endl; // Output Alice

3. Class

Classes are the core structure for object-oriented programming in C++, allowing definition of member variables and member functions. Compared withstructSimilar, but more powerful, supporting features such as inheritance, encapsulation, and polymorphism.

Features：

  • Can include member variables, member functions, constructors, and destructors.
  • Supports object-oriented features such as encapsulation, inheritance, and polymorphism.

Example

class Person {
private:
    string name;
    int age;
public:
    Person(string n, int a) : name(n), age(a) {}
    void printInfo() {
        cout << "Name: " << name << ", Age: " << age << endl;
    }
};
Person p("Bob", 30);
p.printInfo(); // Output: Name: Bob, Age: 30

4. Linked List

A linked list is a dynamic data structure composed of a series of nodes, each containing data and a pointer to the next node.

Features：

  • Dynamically resizes, no need to predefine capacity.
  • Insertion and deletion operations are efficient, with a time complexity of O(1) (when operating at the head or tail of the list).
  • Linear search with a time complexity of O(n).

Instance (Singly Linked List)

struct Node {
    int data;
    Node* next;
};
Node* head = nullptr;
Node* newNode = new Node{10, nullptr};
head = newNode; // Insert new node

Advantages and Disadvantages：

  • Advantages: dynamic size, suitable for scenarios with frequent insertions and deletions.
  • Disadvantages: inefficient random access, not as fast as direct array access.

5. Stack

A stack is a Last In First Out (LIFO) data structure, commonly used in scenarios such as recursion and depth-first search.

Features：

  • Only allows insertion and deletion operations at the top of the stack.
  • Time complexity is O(1).

Example

stack<int> s;
s.push(1);
s.push(2);
cout << s.top(); // Output 2
s.pop();

Advantages and Disadvantages：

  • Advantage: Simple operations, high efficiency.
  • Disadvantages: operations can only be performed at the top, accessing other elements requires popping the top element.

6. Queue

A queue is a First In First Out (FIFO) data structure, commonly used in scenarios such as breadth-first search and task scheduling.

Features：

  • Insertion operations occur at the tail of the queue, and deletion operations occur at the head.
  • Time complexity is O(1).

Example

queue<int> q;
q.push(1);
q.push(2);
cout << q.front(); // Output 1
q.pop();

Advantages and Disadvantages：

  • Advantages: suitable for scenarios that process data in order, such as task scheduling.
  • Disadvantage: Cannot randomly access elements.

7. Double-ended Queue (Deque)

A deque allows insertion and deletion operations at both ends, combining the features of a stack and a queue.

Features：

  • Allows insertion and deletion at both ends.
  • Time complexity is O(1).

Example

deque<int> dq;
dq.push_back(1);
dq.push_front(2);
cout << dq.front(); // Output 2
dq.pop_front();

Advantages and Disadvantages：

  • Advantage: Flexible bidirectional operations.
  • Disadvantages: larger space usage, suitable for scenarios requiring frequent operations at both ends.

8. Hash Table

A hash table is a data structure that stores data via key-value pairs, supporting fast lookup, insertion, and deletion operations. In C++,unordered_mapAn implementation of a hash table.

Features：

  • Uses a hash function to quickly locate elements, with a time complexity of O(1).
  • Does not guarantee the order of elements.

Example

unordered_map<string, int> hashTable;
hashTable["apple"] = 10;
cout << hashTable["apple"]; // Output 10

Advantages and Disadvantages：

  • Advantages: high efficiency in lookup, insertion, and deletion operations.
  • Disadvantages: cannot guarantee element order, and performance degrades when hash collisions occur.

9. Map

mapIt is an ordered key-value pair container, implemented using a red-black tree. Compared withunordered_mapDifferent, it guarantees the order of keys, with time complexities of O(log n) for lookup, insertion, and deletion.

Features：

  • Guarantees elements are arranged in order of their keys.
  • Implemented using a binary search tree.

Example

map<string, int> myMap;
myMap["apple"] = 10;
cout << myMap["apple"]; // Output 10

Advantages and Disadvantages：

  • Advantages: elements are ordered, suitable for scenarios that need to process data in order.
  • Disadvantage: Lower operational efficiency thanunordered_mapSlightly lower.

10. Set

setIt is an ordered set for storing unique elements, implemented using a red-black tree as well. It ensures elements are non-duplicate and ordered.

Features：

  • Guarantees the uniqueness of elements.
  • Elements are automatically arranged in ascending order.
  • Time complexity is O(log n).

Example

set<int> s;
s.insert(1);
s.insert(2);
cout << *s.begin(); // Output 1

Advantages and Disadvantages：

  • Advantage: Automatic sorting and uniqueness guarantee.
  • Disadvantages: insertion and deletion efficiency is lower than that of unordered sets.

11. Dynamic Array (Vector)

vectorIt is a dynamic array implementation provided by the C++ standard library, which can dynamically expand capacity and supports random access.

Features：

  • Dynamic resizing.
  • Supports random access with a time complexity of O(1).
  • When capacity is insufficient, it dynamically expands, with an amortized time complexity of O(1).

Example

vector<int> v;
v.push_back(1);
v.push_back(2);
cout << v[0]; // Output 1

Advantages and Disadvantages：

  • Advantages: supports random access and dynamic expansion.
  • Disadvantages: low efficiency when inserting or deleting elements in the middle.
other extensions