乐闻世界logo
搜索文章和话题

How to use C++ STL containers and algorithms

2月18日 17:34

C++ STL Containers and Algorithms

The C++ Standard Template Library (STL) provides rich containers and algorithms, which are an important part of C++ programming. Mastering STL can significantly improve development efficiency and code quality.

Sequence Containers

std::vector

  • Dynamic array, contiguous memory storage
  • Supports random access, O(1) time complexity
  • Efficient insertion and deletion at the end O(1), middle insertion/deletion O(n)
  • Automatic expansion, typically doubling capacity
cpp
#include <vector>
#include <iostream>

int main() {
    // Create vector
    std::vector<int> vec = {1, 2, 3, 4, 5};
    
    // Access elements
    std::cout << vec[0] << std::endl;  // 1
    std::cout << vec.at(1) << std::endl;  // 2 (with bounds checking)
    
    // Add elements
    vec.push_back(6);  // Add at end
    vec.emplace_back(7);  // In-place construction
    
    // Insert elements
    vec.insert(vec.begin() + 2, 100);  // Insert at position 2
    
    // Delete elements
    vec.pop_back();  // Delete last
    vec.erase(vec.begin());  // Delete first
    
    // Capacity info
    std::cout << "Size: " << vec.size() << std::endl;
    std::cout << "Capacity: " << vec.capacity() << std::endl;
    
    // Reserve space
    vec.reserve(100);  // Reserve at least 100 elements
    
    // Resize
    vec.resize(50, 0);  // Resize to 50 elements, new elements initialized to 0
    
    return 0;
}

std::deque

  • Double-ended queue, segmented contiguous memory
  • Supports fast insertion and deletion at both ends O(1)
  • Supports random access O(1)
  • Higher memory overhead than vector
cpp
#include <deque>

int main() {
    std::deque<int> dq = {1, 2, 3};
    
    // Operations at both ends
    dq.push_front(0);  // Add at front
    dq.push_back(4);    // Add at back
    
    dq.pop_front();     // Delete from front
    dq.pop_back();      // Delete from back
    
    // Random access
    std::cout << dq[1] << std::endl;
    
    return 0;
}

std::list

  • Doubly linked list, non-contiguous memory
  • Insertion and deletion at any position O(1)
  • Does not support random access
  • Additional memory overhead (two pointers per node)
cpp
#include <list>

int main() {
    std::list<int> lst = {1, 2, 3, 4, 5};
    
    // Insert elements
    auto it = lst.begin();
    std::advance(it, 2);
    lst.insert(it, 100);  // Insert at position 2
    
    // Delete elements
    lst.erase(lst.begin());  // Delete first
    
    // List-specific operations
    lst.splice(lst.end(), lst, lst.begin());  // Move elements
    lst.sort();  // Sort
    lst.unique();  // Remove duplicates
    lst.reverse();  // Reverse
    
    return 0;
}

Associative Containers

std::map

  • Key-value container, sorted by key
  • Based on red-black tree implementation
  • Find, insert, delete O(log n)
  • Unique keys
cpp
#include <map>
#include <string>

int main() {
    std::map<std::string, int> scores;
    
    // Insert elements
    scores["Alice"] = 90;
    scores["Bob"] = 85;
    scores.insert({"Charlie", 95});
    
    // Access elements
    std::cout << scores["Alice"] << std::endl;  // 90
    
    // Find elements
    auto it = scores.find("Bob");
    if (it != scores.end()) {
        std::cout << "Bob's score: " << it->second << std::endl;
    }
    
    // Delete elements
    scores.erase("Alice");
    
    // Iterate
    for (const auto& [name, score] : scores) {
        std::cout << name << ": " << score << std::endl;
    }
    
    return 0;
}

std::unordered_map

  • Key-value container, unordered
  • Based on hash table implementation
  • Average find, insert, delete O(1)
  • Worst case O(n)
cpp
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> cache;
    
    cache["key1"] = 100;
    cache["key2"] = 200;
    
    // Fast lookup
    auto it = cache.find("key1");
    if (it != cache.end()) {
        std::cout << it->second << std::endl;
    }
    
    return 0;
}

std::set

  • Ordered set, unique elements
  • Based on red-black tree implementation
  • Find, insert, delete O(log n)
cpp
#include <set>

int main() {
    std::set<int> s = {5, 3, 1, 4, 2};
    
    // Insert elements
    s.insert(6);
    
    // Find elements
    auto it = s.find(3);
    if (it != s.end()) {
        std::cout << "Found: " << *it << std::endl;
    }
    
    // Delete elements
    s.erase(1);
    
    // Iterate (automatically sorted)
    for (int val : s) {
        std::cout << val << " ";
    }
    
    return 0;
}

Container Adapters

std::stack

  • Last In First Out (LIFO)
  • Based on deque or vector
cpp
#include <stack>

int main() {
    std::stack<int> stk;
    
    stk.push(1);
    stk.push(2);
    stk.push(3);
    
    while (!stk.empty()) {
        std::cout << stk.top() << " ";
        stk.pop();
    }
    
    return 0;
}

std::queue

  • First In First Out (FIFO)
  • Based on deque
cpp
#include <queue>

int main() {
    std::queue<int> q;
    
    q.push(1);
    q.push(2);
    q.push(3);
    
    while (!q.empty()) {
        std::cout << q.front() << " ";
        q.pop();
    }
    
    return 0;
}

std::priority_queue

  • Priority queue
  • Default max-heap
cpp
#include <queue>

int main() {
    std::priority_queue<int> pq;  // Max-heap
    
    pq.push(3);
    pq.push(1);
    pq.push(4);
    pq.push(2);
    
    while (!pq.empty()) {
        std::cout << pq.top() << " ";
        pq.pop();
    }
    
    // Min-heap
    std::priority_queue<int, std::vector<int>, std::greater<int>> minPq;
    
    return 0;
}

STL Algorithms

Sorting algorithms:

cpp
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> vec = {5, 2, 8, 1, 9, 3};
    
    // Sort
    std::sort(vec.begin(), vec.end());
    
    // Partial sort
    std::partial_sort(vec.begin(), vec.begin() + 3, vec.end());
    
    // Nth element
    std::nth_element(vec.begin(), vec.begin() + 2, vec.end());
    
    return 0;
}

Search algorithms:

cpp
int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    
    // Binary search (requires sorted)
    auto it = std::lower_bound(vec.begin(), vec.end(), 3);
    
    // Find
    auto found = std::find(vec.begin(), vec.end(), 3);
    
    // Count
    int count = std::count(vec.begin(), vec.end(), 3);
    
    return 0;
}

Transform algorithms:

cpp
int main() {
    std::vector<int> vec1 = {1, 2, 3};
    std::vector<int> vec2(3);
    
    // Copy
    std::copy(vec1.begin(), vec1.end(), vec2.begin());
    
    // Transform
    std::transform(vec1.begin(), vec1.end(), vec2.begin(),
                  [](int x) { return x * 2; });
    
    // Fill
    std::fill(vec2.begin(), vec2.end(), 0);
    
    // Generate
    std::generate(vec2.begin(), vec2.end(),
                  []() { return rand() % 100; });
    
    return 0;
}

Numeric algorithms:

cpp
#include <numeric>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    
    // Sum
    int sum = std::accumulate(vec.begin(), vec.end(), 0);
    
    // Inner product
    std::vector<int> vec2 = {2, 3, 4, 5, 6};
    int product = std::inner_product(vec.begin(), vec.end(),
                                      vec2.begin(), 0);
    
    // Adjacent difference
    std::vector<int> diff(vec.size());
    std::adjacent_difference(vec.begin(), vec.end(), diff.begin());
    
    return 0;
}

Iterators

Iterator categories:

  • Input iterator: read-only, forward
  • Output iterator: write-only, forward
  • Forward iterator: read-write, forward
  • Bidirectional iterator: read-write, bidirectional
  • Random access iterator: read-write, random access
cpp
int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    
    // Forward iterator
    for (auto it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << " ";
    }
    
    // Reverse iterator
    for (auto it = vec.rbegin(); it != vec.rend(); ++it) {
        std::cout << *it << " ";
    }
    
    // Const iterator
    for (auto it = vec.cbegin(); it != vec.cend(); ++it) {
        std::cout << *it << " ";
    }
    
    return 0;
}

Function Objects and Lambda

Lambda expressions:

cpp
int main() {
    std::vector<int> vec = {5, 2, 8, 1, 9};
    
    // Simple lambda
    std::sort(vec.begin(), vec.end(), [](int a, int b) {
        return a < b;
    });
    
    // Capture variables
    int threshold = 5;
    auto it = std::find_if(vec.begin(), vec.end(),
                           [threshold](int x) {
                               return x > threshold;
                           });
    
    // Mutable lambda
    int sum = 0;
    std::for_each(vec.begin(), vec.end(), [&sum](int x) mutable {
        sum += x;
    });
    
    return 0;
}

std::function:

cpp
#include <functional>

int main() {
    std::function<int(int, int)> add = [](int a, int b) {
        return a + b;
    };
    
    std::cout << add(10, 20) << std::endl;
    
    return 0;
}

Best Practices

1. Choose the right container

cpp
// Need random access, frequent end insertion
std::vector<int> vec;

// Need frequent insertion at both ends
std::deque<int> dq;

// Need frequent middle insertion/deletion
std::list<int> lst;

// Need key-based lookup
std::map<std::string, int> mp;

// Need fast lookup, don't care about order
std::unordered_map<std::string, int> ump;

2. Pre-allocate space

cpp
std::vector<int> vec;
vec.reserve(1000);  // Pre-allocate space to avoid multiple reallocations

3. Use emplace instead of push

cpp
std::vector<std::pair<int, int>> vec;

// Recommended
vec.emplace_back(1, 2);  // In-place construction

// Not recommended
vec.push_back(std::make_pair(1, 2));  // May create temporary objects

4. Use move semantics

cpp
std::vector<std::string> vec;
std::string str = "Hello";

vec.push_back(std::move(str));  // Move instead of copy

5. Use algorithms instead of loops

cpp
std::vector<int> vec = {1, 2, 3, 4, 5};

// Recommended
int sum = std::accumulate(vec.begin(), vec.end(), 0);

// Not recommended
int sum = 0;
for (int val : vec) {
    sum += val;
}

Performance Considerations

Time complexity:

  • vector::push_back: average O(1), worst O(n)
  • list::insert: O(1)
  • map::find: O(log n)
  • unordered_map::find: average O(1), worst O(n)

Space complexity:

  • vector: contiguous memory, no extra overhead
  • list: two extra pointers per node
  • map: three extra pointers per node (red-black tree)
  • unordered_map: one extra pointer per node + hash table overhead

Cache friendliness:

  • vector: best (contiguous memory)
  • deque: medium (segmented contiguous)
  • list: worst (scattered memory)
标签：C++
热门标签
更多
Git(114)C语言(23)C++(15)前端(148)React(32)JavaScript(56)Linux(20)Rust(10)Docker(65)Cypress(4)TypeScript(23)Tailwind CSS(29)Vue(13)CSS(19)网络(12)MySQL(7)TypeORM(31)Next.js(30)