C++ data structure and containers and their operation with time complexity

C++ provides a rich set of data structures and containers in its Standard Library, particularly within the <vector>, <list>, <deque>, <set>, <map>, <unordered_set>, and <unordered_map> headers. Here is a summary of some of the key data structures, their operations, and the associated time complexities:

  1. Vector (`std::vector`)
    - Access: O(1) for random access using `operator[]` or `at()`.
    - Insertion/Deletion at End: Amortized O(1) for `push_back()`, O(1) for `pop_back()`.
    - Insertion/Deletion at Beginning or Middle: O(n).
    - Search: O(n) for linear search.

  2. List (`std::list`)
    - Access: O(n) for random access (lists do not support direct access).
    - Insertion/Deletion at Beginning or Middle: O(1) (constant time since it is a doubly linked list).
    - Search: O(n) for linear search.

  3. Deque (`std::deque`)
    - Access: O(1) for random access using `operator[]` or `at()`.
    - Insertion/Deletion at End: O(1) for `push_back()` and `pop_back()`.
    - Insertion/Deletion at Beginning: O(1) for `push_front()` and `pop_front()`.
    - Insertion/Deletion in the Middle: O(n).
    - Search: O(n) for linear search.

  4. Set (`std::set`)
    - Access: O(log n) (sets do not support direct access).
    - Insertion/Deletion: O(log n).
    - Search: O(log n).

  5. Unordered Set (`std::unordered_set`)
    - Access: N/A (unordered sets do not support direct access).
    - Insertion/Deletion: O(1) on average, O(n) in worst case.
    - Search: O(1) on average, O(n) in worst case.

  6. Map (`std::map`)
    - Access: O(log n) using `operator[]` or `at()`.
    - Insertion/Deletion: O(log n).
    - Search: O(log n).

  7. Unordered Map (`std::unordered_map`)
    - Access: O(1) on average using `operator[]` or `at()`, O(n) in worst case.
    - Insertion/Deletion: O(1) on average, O(n) in worst case.
    - Search: O(1) on average, O(n) in worst case.

  8. Stack (`std::stack` - typically implemented using `std::deque` or `std::vector`)
    - Access: N/A (stacks do not support direct access).
    - Push: O(1).
    - Pop: O(1).
    - Top: O(1).

  9. Queue (`std::queue` - typically implemented using `std::deque` or `std::list`)
    - Access: N/A (queues do not support direct access).
    - Push: O(1).
    - Pop: O(1).
    - Front/Back: O(1).

  10. Priority Queue (`std::priority_queue`)
    - Access: O(1) to access the top element.
    - Insertion: O(log n).
    - Deletion (Pop): O(log n).

These time complexities help in choosing the right container for a specific use case, balancing between efficiency of various operations such as access, insertion, deletion, and search.

Comments

Post a Comment

Popular posts from this blog

Copyable and non-copyable Objects in C++

In C++, objects can be categorized as either copyable or non-copyable based on whether they can be copied or assigned using the copy constructor and copy assignment operator. The copyability of an object is determined by the presence or absence of these copy operations. Copyable Objects: Copyable objects can be copied and assigned using the copy constructor and copy assignment operator. By default, user-defined types in C++ are copyable unless specific measures are taken to disable or restrict copying. When an object is copied, a new object is created with the same state as the original object. Example of a copyable class: class Copyable { public: Copyable() {} Copyable(const Copyable& other) {} Copyable& operator=(const Copyable& other) { return *this; } }; Non-Copyable Objects: Non-copyable objects cannot be copied or assigned using the copy constructor and copy assignment operator. This is often intentional when dealing with resources that should not b...
Read more

Prepare for your next C++ interview

Preparing for a C++ interview requires a solid understanding of the language, its features, and common programming concepts. Here are some key areas to focus on: C++ basics: Review the fundamentals of C++, such as variables, data types, operators, control structures (if-else, loops), functions, and classes. Pointers and memory management: Understand how pointers work in C++ and be comfortable with concepts like memory allocation and deallocation, dynamic memory allocation (new/delete), and memory leaks. Adopt Smart Pointers. Understand what are they, How they work and know when to use them. Object-oriented programming (OOP): Review the principles of OOP, including encapsulation , inheritance , and polymorphism . Understand the concepts of classes, objects, constructors, destructors, access specifiers, and virtual functions and virtual classes. Templates and generics: Familiarize yourself with C++ templates, including function templates and class templates. Understand how to use the...
Read more