码医森

C++ 第 17 次课：迭代器与容器的应用

1. 迭代器简介

迭代器提供了一种访问容器元素的通用方法，类似于指针，但更加抽象和安全。它们允许我们遍历容器中的元素，而无需了解容器底层的具体实现。

代码示例 (使用迭代器遍历 vector):

cpp

#include <iostream>
#include <vector>

int main() {
  std::vector<int> numbers = {1, 2, 3, 4, 5};

  // 使用迭代器遍历 vector
  for (std::vector<int>::iterator it = numbers.begin(); it != numbers.end(); ++it) {
    std::cout << *it << " ";
  }
  std::cout << std::endl;

  return 0;
}

2. vector

vector 是一个动态数组，可以根据需要自动调整大小。

2.1 添加元素:

push_back(value): 在 vector 末尾添加元素。

代码示例:

cpp

#include <iostream>
#include <vector>

int main() {
  std::vector<int> numbers;
  numbers.push_back(1);
  numbers.push_back(2);
  numbers.push_back(3);

  for (int i = 0; i < numbers.size(); ++i) {
    std::cout << numbers[i] << " ";
  }
  std::cout << std::endl;

  return 0;
}

insert(iterator, value): 在指定迭代器位置插入元素。

代码示例:

cpp

#include <iostream>
#include <vector>

int main() {
  std::vector<int> numbers = {1, 3, 4};
  std::vector<int>::iterator it = numbers.begin() + 1; // 指向第二个元素 (3)
  numbers.insert(it, 2);

  for (int i = 0; i < numbers.size(); ++i) {
    std::cout << numbers[i] << " ";
  }
  std::cout << std::endl;

  return 0;
}

2.2 删除元素:

pop_back(): 删除 vector 末尾的元素。

代码示例:

cpp

#include <iostream>
#include <vector>

int main() {
  std::vector<int> numbers = {1, 2, 3};
  numbers.pop_back();

  for (int i = 0; i < numbers.size(); ++i) {
    std::cout << numbers[i] << " ";
  }
  std::cout << std::endl;

  return 0;
}

erase(iterator): 删除指定迭代器位置的元素。

代码示例:

cpp

#include <iostream>
#include <vector>

int main() {
  std::vector<int> numbers = {1, 2, 3, 4};
  std::vector<int>::iterator it = numbers.begin() + 1; // 指向第二个元素 (2)
  numbers.erase(it);

  for (int i = 0; i < numbers.size(); ++i) {
    std::cout << numbers[i] << " ";
  }
  std::cout << std::endl;

  return 0;
}

2.3 修改元素:

可以使用迭代器直接访问和修改元素。

代码示例:

cpp

#include <iostream>
#include <vector>

int main() {
  std::vector<int> numbers = {1, 2, 3};
  std::vector<int>::iterator it = numbers.begin() + 1; // 指向第二个元素 (2)
  *it = 5;

  for (int i = 0; i < numbers.size(); ++i) {
    std::cout << numbers[i] << " ";
  }
  std::cout << std::endl;

  return 0;
}

2.4 查询元素:

可以使用迭代器遍历 vector 并查找特定元素。

代码示例:

cpp

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
  std::vector<int> numbers = {1, 2, 3, 4, 5};
  std::vector<int>::iterator it = std::find(numbers.begin(), numbers.end(), 3);

  if (it != numbers.end()) {
    std::cout << "Found 3 at index: " << std::distance(numbers.begin(), it) << std::endl;
  } else {
    std::cout << "3 not found." << std::endl;
  }

  return 0;
}

3. list

list 是一个双向链表，允许在任何位置快速插入和删除元素。

3.1 添加元素:

push_back(value): 在 list 末尾添加元素。
push_front(value): 在 list 开头添加元素。
insert(iterator, value): 在指定迭代器位置插入元素。

代码示例 (在 list 开头插入元素):

cpp

#include <iostream>
#include <list>

int main() {
  std::list<int> numbers = {2, 3};
  numbers.push_front(1);

  for (std::list<int>::iterator it = numbers.begin(); it != numbers.end(); ++it) {
    std::cout << *it << " ";
  }
  std::cout << std::endl;

  return 0;
}

3.2 删除元素:

pop_back(): 删除 list 末尾的元素。
pop_front(): 删除 list 开头的元素。
erase(iterator): 删除指定迭代器位置的元素。
remove(value): 删除所有值为 value 的元素。

代码示例 (删除 list 中所有值为 2 的元素):

cpp

#include <iostream>
#include <list>

int main() {
  std::list<int> numbers = {1, 2, 3, 2, 4};
  numbers.remove(2);

  for (std::list<int>::iterator it = numbers.begin(); it != numbers.end(); ++it) {
    std::cout << *it << " ";
  }
  std::cout << std::endl;

  return 0;
}

3.3 修改元素:

可以使用迭代器直接访问和修改元素。

代码示例:

cpp

#include <iostream>
#include <list>

int main() {
  std::list<int> numbers = {1, 2, 3};
  std::list<int>::iterator it = numbers.begin();
  std::advance(it, 1); // 移动迭代器到第二个元素 (2)
  *it = 5;

  for (std::list<int>::iterator iter = numbers.begin(); iter != numbers.end(); ++iter) {
    std::cout << *iter << " ";
  }
  std::cout << std::endl;

  return 0;
}

3.4 查询元素:

可以使用迭代器遍历 list 并查找特定元素。

代码示例:

cpp

#include <iostream>
#include <list>
#include <algorithm>

int main() {
  std::list<int> numbers = {1, 2, 3, 4, 5};
  std::list<int>::iterator it = std::find(numbers.begin(), numbers.end(), 3);

  if (it != numbers.end()) {
    std::cout << "Found 3" << std::endl;
  } else {
    std::cout << "3 not found." << std::endl;
  }

  return 0;
}

4. forward_list

forward_list 是一个单向链表，只允许向前遍历。

4.1 添加元素:

push_front(value): 在 forward_list 开头添加元素。
insert_after(iterator, value): 在指定迭代器位置之后插入元素.

代码示例 (在 forward_list 开头插入元素):

cpp

#include <iostream>
#include <forward_list>

int main() {
  std::forward_list<int> numbers = {2, 3};
  numbers.push_front(1);

  for (std::forward_list<int>::iterator it = numbers.begin(); it != numbers.end(); ++it) {
    std::cout << *it << " ";
  }
  std::cout << std::endl;

  return 0;
}

4.2 删除元素:

pop_front(): 删除 forward_list 开头的元素。
erase_after(iterator): 删除指定迭代器位置之后的元素。
remove(value): 删除所有值为 value 的元素。

代码示例 (删除 forward_list 开头的元素):

cpp

#include <iostream>
#include <forward_list>

int main() {
  std::forward_list<int> numbers = {1, 2, 3};
  numbers.pop_front();

  for (std::forward_list<int>::iterator it = numbers.begin(); it != numbers.end(); ++it) {
    std::cout << *it << " ";
  }
  std::cout << std::endl;

  return 0;
}

4.3 修改元素:

可以使用迭代器直接访问和修改元素。

代码示例:

cpp

#include <iostream>
#include <forward_list>

int main() {
  std::forward_list<int> numbers = {1, 2, 3};
  std::forward_list<int>::iterator it = numbers.begin();
  std::advance(it, 1); // 移动迭代器到第二个元素 (2)
  *it = 5;

  for (std::forward_list<int>::iterator iter = numbers.begin(); iter != numbers.end(); ++iter) {
    std::cout << *iter << " ";
  }
  std::cout << std::endl;

  return 0;
}

4.4 查询元素:

可以使用迭代器遍历 forward_list 并查找特定元素。

代码示例:

cpp

#include <iostream>
#include <forward_list>
#include <algorithm>

int main() {
  std::forward_list<int> numbers = {1, 2, 3, 4, 5};
  std::forward_list<int>::iterator it = std::find(numbers.begin(), numbers.end(), 3);

  if (it != numbers.end()) {
    std::cout << "Found 3" << std::endl;
  } else {
    std::cout << "3 not found." << std::endl;
  }

  return 0;
}

5. deque

deque 是一个双端队列，允许在两端快速插入和删除元素。

5.1 添加元素:

push_back(value): 在 deque 末尾添加元素。
push_front(value): 在 deque 开头添加元素。
insert(iterator, value): 在指定迭代器位置插入元素。

代码示例 (在 deque 开头插入元素):

cpp

#include <iostream>
#include <deque>

int main() {
  std::deque<int> numbers = {2, 3};
  numbers.push_front(1);

  for (std::deque<int>::iterator it = numbers.begin(); it != numbers.end(); ++it) {
    std::cout << *it << " ";
  }
  std::cout << std::endl;

  return 0;
}

5.2 删除元素:

pop_back(): 删除 deque 末尾的元素。
pop_front(): 删除 deque 开头的元素。
erase(iterator): 删除指定迭代器位置的元素。

代码示例 (删除 deque 开头的元素):

cpp

#include <iostream>
#include <deque>

int main() {
  std::deque<int> numbers = {1, 2, 3};
  numbers.pop_front();

  for (std::deque<int>::iterator it = numbers.begin(); it != numbers.end(); ++it) {
    std::cout << *it << " ";
  }
  std::cout << std::endl;

  return 0;
}

5.3 修改元素:

可以使用迭代器直接访问和修改元素。

代码示例:

cpp

#include <iostream>
#include <deque>

int main() {
  std::deque<int> numbers = {1, 2, 3};
  std::deque<int>::iterator it = numbers.begin();
  std::advance(it, 1); // 移动迭代器到第二个元素 (2)
  *it = 5;

  for (std::deque<int>::iterator iter = numbers.begin(); iter != numbers.end(); ++iter) {
    std::cout << *iter << " ";
  }
  std::cout << std::endl;

  return 0;
}

5.4 查询元素:

可以使用迭代器遍历 deque 并查找特定元素。

代码示例:

cpp

#include <iostream>
#include <deque>
#include <algorithm>

int main() {
  std::deque<int> numbers = {1, 2, 3, 4, 5};
  std::deque<int>::iterator it = std::find(numbers.begin(), numbers.end(), 3);

  if (it != numbers.end()) {
    std::cout << "Found 3" << std::endl;
  } else {
    std::cout << "3 not found." << std::endl;
  }

  return 0;
}

6. queue

queue 是一个队列，遵循 FIFO (先进先出) 原则。

6.1 添加元素:

push(value): 在队列末尾添加元素。

代码示例:

cpp

#include <iostream>
#include <queue>

int main() {
  std::queue<int> numbers;
  numbers.push(1);
  numbers.push(2);
  numbers.push(3);

  while (!numbers.empty()) {
    std::cout << numbers.front() << " ";
    numbers.pop();
  }
  std::cout << std::endl;

  return 0;
}

6.2 删除元素:

pop(): 删除队列开头的元素。

代码示例 (参考 6.1)

6.3 访问元素:

front(): 访问队列开头的元素。
back(): 访问队列末尾的元素。

代码示例 (参考 6.1)

注意: queue 不支持迭代器遍历。

7. set

set 是一个有序集合，不允许重复元素。

7.1 添加元素:

insert(value): 在 set 中插入元素。

代码示例:

cpp

#include <iostream>
#include <set>

int main() {
  std::set<int> numbers;
  numbers.insert(3);
  numbers.insert(1);
  numbers.insert(2);
  numbers.insert(2); // 重复元素，不会被插入

  for (std::set<int>::iterator it = numbers.begin(); it != numbers.end(); ++it) {
    std::cout << *it << " ";
  }
  std::cout << std::endl;

  return 0;
}

7.2 删除元素:

erase(iterator): 删除指定迭代器位置的元素。
erase(value): 删除值为 value 的元素。

代码示例 (删除值为 2 的元素):

cpp

#include <iostream>
#include <set>

int main() {
  std::set<int> numbers = {1, 2, 3};
  numbers.erase(2);

  for (std::set<int>::iterator it = numbers.begin(); it != numbers.end(); ++it) {
    std::cout << *it << " ";
  }
  std::cout << std::endl;

  return 0;
}

7.3 查询元素:

find(value): 查找值为 value 的元素，返回指向该元素的迭代器，如果未找到则返回 end()。

代码示例:

cpp

#include <iostream>
#include <set>

int main() {
  std::set<int> numbers = {1, 2, 3, 4, 5};
  std::set<int>::iterator it = numbers.find(3);

  if (it != numbers.end()) {
    std::cout << "Found 3" << std::endl;
  } else {
    std::cout << "3 not found." << std::endl;
  }

  return 0;
}

注意: set 中的元素是 const 的，不能通过迭代器修改。

8. map

map 是一个键值对的集合，键是唯一的。

8.1 添加元素:

insert(std::pair<key, value>): 插入一个键值对。
[key] = value: 通过键访问并赋值。

代码示例:

cpp

#include <iostream>
#include <map>

int main() {
  std::map<std::string, int> ages;
  ages.insert(std::pair<std::string, int>("Alice", 25));
  ages["Bob"] = 30;

  for (std::map<std::string, int>::iterator it = ages.begin(); it != ages.end(); ++it) {
    std::cout << it->first << ": " << it->second << std::endl;
  }

  return 0;
}

8.2 删除元素:

erase(iterator): 删除指定迭代器位置的元素。
erase(key): 删除键为 key 的元素。

代码示例 (删除键为 "Bob" 的元素):

cpp

#include <iostream>
#include <map>

int main() {
  std::map<std::string, int> ages;
  ages["Alice"] = 25;
  ages["Bob"] = 30;

  ages.erase("Bob");

  for (std::map<std::string, int>::iterator it = ages.begin(); it != ages.end(); ++it) {
    std::cout << it->first << ": " << it->second << std::endl;
  }

  return 0;
}

8.3 修改元素:

可以使用迭代器或键访问并修改值。

代码示例 (修改 "Alice" 的年龄):

cpp

#include <iostream>
#include <map>

int main() {
  std::map<std::string, int> ages;
  ages["Alice"] = 25;
  ages["Bob"] = 30;

  ages["Alice"] = 26;

  for (std::map<std::string, int>::iterator it = ages.begin(); it != ages.end(); ++it) {
    std::cout << it->first << ": " << it->second << std::endl;
  }

  return 0;
}

8.4 查询元素:

find(key): 查找键为 key 的元素，返回指向该元素的迭代器，如果未找到则返回 end()。

代码示例:

cpp

#include <iostream>
#include <map>

int main() {
  std::map<std::string, int> ages;
  ages["Alice"] = 25;
  ages["Bob"] = 30;

  std::map<std::string, int>::iterator it = ages.find("Bob");

  if (it != ages.end()) {
    std::cout << "Bob's age: " << it->second << std::endl;
  } else {
    std::cout << "Bob not found." << std::endl;
  }

  return 0;
}

作业

请自行选择内部数据结构设计一个 stack 的模板类

C++

template <typename T>
struct MyStack {
    MyStack() {
    }
    void push(const T& t) {
        stack_inside_.push_back(t);
    }

    T top() {
        return stack_inside_.back();
    }

    void pop() {
        return stack_inside_.pop_back();
    }

    bool empty() {
        return stack_inside_.empty();
    }

    std::vector<T> stack_inside_;
};

c++

int main() {

      MyStack<int> stack;

      Stack.push(1);

      stack.push(2);

      if (!stack.empty()) {

		std::cout << stack.top() << std::endl;

      }

      Stack.pop();


}

C++ 第 17 次课：迭代器与容器的应用 ​

1. 迭代器简介 ​

2. vector ​

3. list ​

4. forward_list ​

5. deque ​

6. queue ​

7. set ​

8. map ​

作业 ​

C++ 第 17 次课：迭代器与容器的应用

1. 迭代器简介

2. vector

3. list

4. forward_list

5. deque

6. queue

7. set

8. map

作业