YouTip

C++ provides a variety of data structures, ranging from basic ones like arrays, structs, and classes to advanced STL containers such as `vector`, `map`, and `unordered_map`. Below is a detailed introduction to commonly used data structures in C++, along with their characteristics and usage. ### 1. **Array** An array is the most fundamental data structure, used to store a collection of elements of the same type. **Characteristics**: * Fixed size; once declared, the size cannot be changed. * Direct element access with O(1) time complexity. * Suitable for collections where the size is known and elements are of the same type. ## Example int arr={1, 2, 3, 4, 5}; cout<< arr;// Output the first element **Pros and Cons**: * Pros: Fast access, compact memory usage. * Cons: Fixed size, cannot dynamically expand; not suitable for datasets with uncertain sizes. ### 2. **Struct** A struct allows combining different types of data into a custom data type. **Characteristics**: * 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** A class is the core structure for object-oriented programming in C++, allowing the definition of member variables and member functions. Similar to `struct`, but more powerful, supporting inheritance, encapsulation, polymorphism, etc. **Characteristics**: * Can contain 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. **Characteristics**: * Dynamically adjusts size; no need to define capacity in advance. * Efficient insertion and deletion operations with O(1) time complexity (at the head or tail of the list). * Linear search with O(n) time complexity. ## Example (Singly Linked List) struct Node { int data; Node* next; }; Node* head = nullptr; Node* newNode =new Node{10, nullptr}; head = newNode;// Insert new node **Pros and Cons**: * Pros: Dynamic size, suitable for scenarios with frequent insertions and deletions. * Cons: 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 recursion, depth-first search, and similar scenarios. **Characteristics**: * Insertion and deletion are only allowed at the top of the stack. * O(1) time complexity. ## Example stack s; s.push(1); s.push(2); cout<< s.top();// Output 2 s.pop(); **Pros and Cons**: * Pros: Simple operations, high efficiency. * Cons: Can only operate at the top of the stack; accessing other elements requires popping the top element. ### 6. **Queue** A queue is a First In First Out (FIFO) data structure, commonly used in breadth-first search, task scheduling, and similar scenarios. **Characteristics**: * Insertion occurs at the rear, and deletion occurs at the front. * O(1) time complexity. ## Example queue q; q.push(1); q.push(2); cout<< q.front();// Output 1 q.pop(); **Pros and Cons**: * Pros: Suitable for scenarios where data is processed in order, such as task scheduling. * Cons: Cannot randomly access elements. ### 7. **Deque (Double-ended Queue)** A deque allows insertion and deletion at both ends, combining the features of a stack and a queue. **Characteristics**: * Allows insertion and deletion at both ends. * O(1) time complexity. ## Example deque dq; dq.push_back(1); dq.push_front(2); cout<< dq.front();// Output 2 dq.pop_front(); **Pros and Cons**: * Pros: Flexible bidirectional operations. * Cons: Larger space overhead; suitable for scenarios requiring frequent operations at both ends. ### 8. **Hash Table** A hash table is a data structure that stores data in key-value pairs, supporting fast lookup, insertion, and deletion operations. In C++, `unordered_map` is the implementation of a hash table. **Characteristics**: * Uses a hash function to quickly locate elements with O(1) time complexity. * Does not guarantee element order. ## Example unordered_map hashTable; hashTable=10; cout<< hashTable;// Output 10 **Pros and Cons**: * Pros: High efficiency for lookup, insertion, and deletion operations. * Cons: Cannot guarantee element order; performance may degrade due to hash collisions. ### 9. **Map** `map` is an ordered key-value pair container implemented with a red-black tree underneath. Unlike `unordered_map`, it guarantees key ordering, with O(log n) time complexity for lookup, insertion, and deletion. **Characteristics**: * Guarantees elements are sorted by key. * Implemented using a binary search tree. ## Example map myMap; myMap=10; cout<< myMap;// Output 10 **Pros and Cons**: * Pros: Elements are ordered, suitable for scenarios requiring sequential data processing. * Cons: Slightly lower operation efficiency compared to `unordered_map`. ### 10. **Set** `set` is an ordered collection used to store unique elements, also implemented with a red-black tree underneath. It guarantees no duplicate elements and maintains order. **Characteristics**: * Guarantees uniqueness of elements. * Elements are automatically sorted in ascending order. * O(log n) time complexity. ## Example set s; s.insert(1); s.insert(2); cout<<*s.begin();// Output 1 **Pros and Cons**: * Pros: Automatic sorting and uniqueness guarantee. * Cons: Insertion and deletion efficiency is lower than that of unordered sets. ### 11. **Dynamic Array (Vector)** `vector` is a dynamic array implementation provided by the C++ standard library. It can dynamically expand its capacity and supports random access. **Characteristics**: * Dynamically adjusts size. * Supports random access with O(1) time complexity. * Dynamically expands when capacity is insufficient, with amortized O(1) time complexity. ## Example vector v; v.push_back(1); v.push_back(2); cout<< v;// Output 1 **Pros and Cons**: * Pros: Supports random access and dynamic expansion. * Cons: Lower efficiency for inserting and deleting elements in the middle.