C++20 STL CookBook 7 Containers(II)

让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 流的字符串类型的输入迭代器。每次我们取消引用此迭代器时，它都会从输入流中返回一个单词。