【C++11】字符串与常用数据结构

学习一门编程语言，考察编程语言支持的基本数据结构是很重要的。如果你以前学的C/C++倾向于自己造轮子，或者你有其他语言背景的话，建议重新了解一下C++11 标准库中的数据结构。

字符串 std::string

你可以用 const char* 也就是字符串字面量来构造 std::string ，也可以从 std::string 中获取 C风格字符串的指针（const char*）。

std::string foo = “foo”;
foo.c_str(); // const char*

1 2	std::string foo = “foo”; foo.c_str(); // const char*

std::string 是可变的，所以你可以修改 std::string 而不用太担心性能

std::string result;
result += “foo”;
result += ‘@’;
result += “example.com”;

std::string result;

result += “foo”;

result += ‘@’;

result += “example.com”;

关于不可变字符串，有很多讨论，这里列举一下想要用不可变的“字符串”话，在不用其他库的情况下可以怎么做

const char* 如果自己分配的字符串数组的话，需要记得delete。字符串字面量的话不用担心。
const std::string& 给 std::string 加const，严格来说这只是防止修改
自己造轮子

std::string 支持 copy 和 move

std::string 的 substr 返回的是 copy 过的子字符串。

C++17开始支持 string_view。在C++17之前想用“字符串视图”的话，你可能要自己构造一个类似下面这种包装结构

struct StringView {
    std::shared_ptr<std::string> str_ptr_;
    size_t start_;
    size_t end_;

    explicit StringView(
        std::shared_ptr<std::string>& str_ptr, 
        size_t start, 
        size_t end): str_ptr_{str_ptr}, start_{start}, end_{end} {
    }
};

struct StringView {

std::shared_ptr<std::string> str_ptr_;

size_t start_;

size_t end_;

explicit StringView(

std::shared_ptr<std::string>& str_ptr,

size_t start,

size_t end): str_ptr_{str_ptr}, start_{start}, end_{end} {

}

};

std::string 的 = 是字符串比较，而不是地址比较。

std::string 提供的相关方法不多，现有的比如查找find/rfind

std::string foo = “foo”;
foo.find(‘f’); // 0
foo.find(‘a’); // not found, std::basic_string::npos

std::string foo = “foo”;

foo.find(‘f’); // 0

foo.find(‘a’); // not found, std::basic_string::npos

需要注意找不到时返回的不是-1，而是npos，一个特殊的值

std::string 提供了两个获取字符的方法，at 和 []，前者加了范围检查，后者没有

支持用迭代器方式遍历字符串

std::string foo = “foo”;
for(const char& ch: foo) {
    // do stuff
}

std::string foo = “foo”;

for(const char& ch: foo) {

// do stuff

}

关于UTF-8字符串，可能和 std::string 没有直接关系，但是C++11中的字符串字面量

“foo”; // 1
u8″foo”; // 2

1 2	“foo”; // 1 u8“foo”; // 2

1是依赖于系统编码的字符串字面量，2是UTF-8编码的字符串字面量。

std::string 没有直接支持UTF-8的方法，size返回的是字节数，如果你用迭代器遍历的话，是按照逐个byte的方式（虽然类型叫char）

自增长数组：std::vector<T>

对于有自增长需求的数组，std::vector 是一个很好的选择，但是在使用C++11引入的initializer_list需要注意复制问题。具体来说

std::vector<int> numbers = {1, 2, 3, 4, 5}; // 1
std::vector<std::string> strings = {“foo”, “bar”, “baz”}; // 2

1 2	std::vector<int> numbers = {1, 2, 3, 4, 5}; // 1 std::vector<std::string> strings = {“foo”, “bar”, “baz”}; // 2

1是没有问题的，基础类型本来就可以随意复制。2会复制字符串。原因在于initializer_list的begin和end返回值有const修饰，vector的构造函数里只能复制。解决方法是

std::vector<std::string> strings;
strings.reserve(3);
strings.emplace_back(“foo”);
strings.emplace_back(“bar”);
strings.emplace_back(“baz”);

std::vector<std::string> strings;

strings.reserve(3);

strings.emplace_back(“foo”);

strings.emplace_back(“bar”);

strings.emplace_back(“baz”);

也就是说，不要使用intializer_list构造T为非基础类型的vector。

上述代码中第二行的reserve是必须的。使用vector的默认构造函数时初始大小为0。那么是否有可以指定初始大小的构造函数？有兴趣的可以看一下 std::vector 的构造函数，回答是可能没有。注意使用数字初始化vector时你会得到指定数量的T的实例，而不是指定数量的空位（nullptr）。

之后调用C++11新增的emplace_back方法。emplace_back比C++11之前的push_back好的地方是不需要move，直接在vector里初始化。这里涉及 std::vector 是内部所有元素的 owner 的要求，所以任何通过 push_back 传入的元素都会被 move，如果不支持 move 那么就 copy。

如果你用上一篇用于测试copy/move的MyString作为T执行上述代码的话，输出只有3次构造函数调用。用push_back的话，会有3次move。不用reverse的话，会有3 + 2 + 1 = 6次move，这是因为内部需要扩容，扩容时会move。如果用initializer_list初始化的话，会有3次copy。

如果你要高效地使用vector的话，请注意上述问题。

构造完了之后，可以通过range-for-loop迭代

for(std::string& str: strings) {
    // do stuff
}

for(std::string& str: strings) {

// do stuff

}

随机访问同样有 at 和 [] 两种选择，前者带范围检查，后者不带。

常规使用，记住以上内容就可以了。

哈希表：std::unordered_map<K, V>

本篇介绍的最后一个常用的数据结构。

#include <iostream>
#include <unordered_map>

struct MyKey {
    int value;

    explicit MyKey(int val) : value{val} {
        std::cout << “MyKey(” << val << “)\n”;
    }

    MyKey(const MyKey &key) : value{key.value} {
        std::cout << “MyKey(copy)\n”;
    }

    MyKey &operator=(const MyKey &) = delete;

    MyKey(MyKey &&key) {
        std::cout << “MyKey(move)\n”;
        value = key.value;
        key.value = 0;
    }

    MyKey &operator=(MyKey &&) = delete;

    friend bool operator==(const MyKey &key1, const MyKey &key2) {
        return key1.value == key2.value;
    }

    ~MyKey() {
        std::cout << “~MyKey()\n”;
    }
};

template<>
struct std::hash<MyKey> {
    size_t operator()(const MyKey &key) const {
        return key.value;
    }
};

int main() {
    std::unordered_map<MyKey, int> map;
    map.emplace(MyKey{1}, 1); // move
    map.insert(std::make_pair(MyKey{2}, 2)); // move, move

    MyKey key3{3};
    map.emplace(key3, 3); // copy

    // std::unordered_map<MyKey, int>::iterator
    auto map_it = map.find(key3); // found
    std::cout << map_it->second << std::endl; // 3

    map_it = map.find(MyKey{4}); // not found
    std::cout << std::boolalpha << (map_it == map.end()) << std::endl; // true

    map.erase(key3); // delete
    std::cout << std::boolalpha << (map.find(key3) == map.end()) << std::endl; // true
    return 0;
}

#include <iostream>

#include <unordered_map>

struct MyKey {

int value;

explicit MyKey(int val) : value{val} {

std::cout << “MyKey(“ << val << “)\n”;

}

MyKey(const MyKey &key) : value{key.value} {

std::cout << “MyKey(copy)\n”;

}

MyKey &operator=(const MyKey &) = delete;

MyKey(MyKey &&key) {

std::cout << “MyKey(move)\n”;

value = key.value;

key.value = 0;

}

MyKey &operator=(MyKey &&) = delete;

friend bool operator==(const MyKey &key1, const MyKey &key2) {

return key1.value == key2.value;

}

~MyKey() {

std::cout << “~MyKey()\n”;

}

};

template<>

struct std::hash<MyKey> {

size_t operator()(const MyKey &key) const {

return key.value;

}

};

int main() {

std::unordered_map<MyKey, int> map;

map.emplace(MyKey{1}, 1); // move

map.insert(std::make_pair(MyKey{2}, 2)); // move, move

MyKey key3{3};

map.emplace(key3, 3); // copy

// std::unordered_map<MyKey, int>::iterator

auto map_it = map.find(key3); // found

std::cout << map_it–>second << std::endl; // 3

map_it = map.find(MyKey{4}); // not found

std::cout << std::boolalpha << (map_it == map.end()) << std::endl; // true

map.erase(key3); // delete

std::cout << std::boolalpha << (map.find(key3) == map.end()) << std::endl; // true

return 0;

}

这里特别演示了自定义K的方式。需要一个std::hash<MyKey>结构和重载==方法。

和 std::vector 一样，这里不使用 initailizer_list 初始化 map 避免比必要的复制。添加KV对的方式有好几种

emplace，rvalue（这里是临时值），一次move
emplace，lvalue（key3），一次copy
insert + make_pair，两次move

和 std::vector 不同的是，考虑到 unordered_map 是专门为查找使用的容器，所以 key 被复制个人认为没有太大问题，上述代码中也看到，查询时需要一个key，存放时又需要保证key被容器所管理，所以copy是无法避免的。

查找时，返回的是一个迭代器，如果不为 map.end() ，表示找到，并且调用 map_it-> second 得到KV对的value。这里 *map_it 的类型是 std::pair。

删除可以用迭代器，也可以用 key，这里演示了用key的方式。

小结

总体来说，C++11的数据结构很基础，还不足以达到其他更高级的编程语言的易用性，所以会有很多自制的 string，比如Qt的QString。

除了这里的vector和unordered_map，C++还有链表list，基于红黑树的有序映射表map等等。如果上面这两个基础的数据结构你会使用了的话，其他的数据结构相信你也知道如何使用。

这里还有一些头文件 <algorithm> 中的方法没有列出来，C++里，使用algorithm里面的方法加lambda可以做一些比较有趣的事情。有机会下次介绍。

作为补充，推荐《C++ Cookbook》。虽然这本书可能有点早，但是对于开发中常见的问题都会直接的解决方案以及解释，很适合作为C++开发的参考。

箱猫日和

【C++11】字符串与常用数据结构

字符串 std::string

自增长数组：std::vector<T>

哈希表：std::unordered_map<K, V>

小结

One response to “【C++11】字符串与常用数据结构”