让vector在插入删除的时候仍然保证是有序的
首先，STL的确提供了一种办法来检查我们的目标容器是不是有序的：std::is_sorted - cppreference.com，也就是std::is_sorted。我们当然可以这样做：
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector v{ 1, 4, 3 };
if (std::is_sorted(v.begin(), v.end())) {
std::cout << "Vector is sorted\n";
}else {
std::cout << "Vector is not sorted\n";
}
std::sort(v.begin(), v.end());
if (std::is_sorted(v.begin(), v.end())) {
std::cout << "Vector is sorted\n";
}
else {
std::cout << "Vector is not sorted\n";
}
return 0;
}
结果显而易见：
Vector is not sorted Vector is sorted
当然还可以添加谓词，这里就不再赘述了
我们现在关心的是：如果我们向元素中插入一个新元素（删除如何呢？想一想我们有必要考虑删除的case吗？），我们能不能保证原来的数组还是有序的呢？
答案是，可以做到，但是我们需要组合我们的STL算法完成这个工作！
template<typename C, typename E>
void insert_sorted(C& c, const E& e) {
const auto pos{ std::ranges::lower_bound(c, e) };
c.insert(pos, e);
}
这个算法有一定的通用局限性：这是因为std::sort() 算法（及其派生算法）需要支持随机访问的容器。并非所有 STL 容器都满足此要求（std::list是位列其中的）
高效地将元素插入到映射中
映射类Map是一个关联容器，它包含键值对，其中键在容器内必须是唯一的。这里有多种方法可以填充映射容器。
map<string, string> m;
嗯哼，这就是说我们的Key和Value都是字符串，字符串之间的映射。一般的，我们喜欢使用 [] 运算符添加元素：
m["Miles"] = "Trumpet"
或者使用 insert() 成员函数：
m.insert(pair<string,string>("Hendrix", "Guitar"));
还可以使用 emplace() 成员函数：
m.emplace("Krupa", "Drums");
笔者倾向于使用 emplace() 函数。在 C++11 中引入的 emplace() 使用完美转发来为容器放置（就地创建）新元素。参数直接转发到元素构造函数。这快速、高效且易于编码。
虽然它肯定比其他选项有所改进，但 emplace() 的问题在于，即使不需要，它也会构造一个对象。这涉及调用构造函数、分配内存和移动数据，然后丢弃该临时对象。为了解决这个问题，C++17 提供了新的 try_emplace() 函数，该函数仅在需要时构造值对象。这对于大型对象或许多位置尤其重要。
映射的每个元素都是一个键值对。在对结构中，元素被命名为第一和第二，但它们在映射中的目的是键和值。我倾向于将值对象视为有效载荷，因为这通常是映射的要点。要搜索现有键，try_emplace() 函数必须构造键对象；这是无法避免的。但它不需要构造有效载荷对象，除非需要将其插入到映射中。
高效的修改map中的keys
映射是一种存储键值对的关联容器。容器按键排序。键必须是唯一的，并且是 const 限定的，因此不能更改。例如，如果我填充映射并尝试更改键，则会在编译时收到错误：
std::map<int, string> this_map {
{1, "foo"}, {2, "bar"}, {3, "baz"}
};
auto wanna_change = this_map.begin();
wanna_change->first = 114514;
如果您需要重新排序地图容器，可以使用extract() 方法交换键来实现。作为 C++17 的新增功能，extract() 是地图类及其派生类中的成员函数。它允许从序列中提取地图的元素，而无需触及有效负载。提取后，键不再是 const 限定的，可能会被修改。
下面，我们来演示一下这个extract方法应该如何使用！
using SpecialMap = std::map<int, std::string>;
void printMap(const SpecialMap& m){
std::cout << "Maps are here:> \n";
for(const auto& [aInt, aString] : m)
{
std::print("{} : {}\n", aInt, aString);
}
}
现在您可以测试一下好不好用这个函数。
SpecialMap aMap {
{1, "Charlie"}, {2, "Chen"}, {3, "Qt"}, {4, "C++"}, {5, "Idk what should e be at here:("}
};
printMap(aMap);
下面才是正文，我们交换map两个键值对的key：
template<typename Map, typename Key>
bool swap_key(Map& m, const Key& key1, const Key& key2)
{
// 取出我们的
auto node1 = m.extract(key1);
auto node2 = m.extract(key2);
if (!node1 ||!node2)
{
return false;
}
swap(node1.key(), node2.key());
m.insert(std::move(node2));
m.insert(std::move(node1));
return true;
}
小小的测试一下：
使用带有自定义键的 unordered_map
对于有序映射，键的类型必须是可排序的，这意味着它必须至少支持小于 < 比较运算符。假设您想要使用具有不可排序的自定义类型的关联容器。例如，向量 (0, 1) 不小于或大于 (1, 0)，它只是指向不同的方向。在这种情况下，您仍然可以使用 unordered_map 类型。让我们看看如何做到这一点。
我们现在呢，把Key设置为一个坐标：
struct Position {
int x{};
int y{};
friend bool operator==(const Position& lhs, const Position& rhs){
return lhs.x == rhs.x && lhs.y == rhs.y;
}
};
using PositionMap = std::unordered_map<Position, int>;
我们知道unordered_map还需要第三个模板参数：
template< class Key, class T, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class Allocator = std::allocator< std::pair<const Key, T> > > class unordered_map;
所以，实际上我们还需要提供将Key映射为哈希值的办法。
所以我们需要重载一下...
namespace std {
template<>
struct hash<Coord> {
size_t operator()(const Coord& c) const {
return static_cast<size_t>(c.x)
+ static_cast<size_t>(c.y);
}
};
}
现在我们就可以这样使用我们的Map With self defined Key了。
void printMap(const PositionMap& positionMap)
{
for (const auto& [position, value] : positionMap) {
std::print("({}, {}) = {}\n", position.x, position.y, value);
}
}
使用set来unique我们的输入
集合容器是一种关联容器，其中每个元素都是一个值，用作键。集合中的元素按排序顺序维护，不允许重复的键。集合容器经常被误解，与更通用的容器（例如向量和映射）相比，它的用途更少且更具体。集合的一个常见用途是从一组值中过滤重复项。
作为示例，我们将从标准输入中读取单词并过滤掉重复项。
我们首先为 istream 迭代器定义一个别名。我们将使用它从命令行获取输入。
using input_it = istream_iterator<string>;
在 main() 函数中，我们将为我们的单词定义一个集合：
int main() {
set<string> words;
该集合定义为一组字符串元素。我们定义一对迭代器以与 inserter() 函数一起使用：
input_it it{ cin };
input_it end{};
end 迭代器用其默认构造函数初始化。这称为流结束迭代器。当我们的输入结束时，此迭代器将与 cin 迭代器进行比较。inserter() 函数用于将元素插入到集合容器中：
copy(it, end, inserter(words, words.end()));
我们使用 std::copy() 方便地从输入流中复制单词。现在我们可以打印出我们的集合来查看结果：
for(const string & w : words) {
cout << format("{} ", w);
}
cout << '\n';
我们可以通过将一堆单词传送到其输入来运行该程序：
➜ echo "a a b b b c c c c hello world hello" | .\Modules.exe a b c hello world
现在我们看：该集合已消除重复项并保留了插入的单词的排序列表。
集合容器是核心。它仅包含唯一元素。当您插入重复项时，该插入将失败。因此，您最终会得到每个唯一元素的排序列表。但这不是此配方唯一有趣的部分。istream_iterator 是一个从流中读取对象的输入迭代器。我们像这样实例化输入迭代器：
istream_iterator<string> it{ cin };
现在我们有一个来自 cin 流的字符串类型的输入迭代器。每次我们取消引用此迭代器时，它都会从输入流中返回一个单词。
