文章首发于本人CSDN账号:https://blog.csdn.net/tefuirnever
由于微信不允许外部链接,你需要点击页尾左下角的“阅读原文”,才能访问文中的链接。
因为是初学者,如果有写的不对的地方,还请各位不吝赐教。
以下是学习笔记总目录(更新中ing),和关于容器的章节习题。
1、C++库引用(Import C++ Library)
众所周知,常用的库引用如下:
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
有些太多,所以有了一个新奇的方法:
#include <bits/stdc++.h>
一行代码解决一系列代码,方便!
其中 bits/stdc++.h
源码如下:
// C++ includes used for precompiling -*- C++ -*-
// Copyright (C) 2003-2014 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.
// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
// <http://www.gnu.org/licenses/>.
/** @file stdc++.h
* This is an implementation file for a precompiled header.
*/
// 17.4.1.2 Headers
// C
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
不过 VS
会报错,网上解决办法一大堆,这里就不过多赘述了。
2、STL(Standard Template Library)
STL有六大组件(容器(containers)
、迭代器(iterators)
、空间配置器(allocator)
、配接器(adapters)
、算法(algorithms)
、仿函数(functors)
)。
但主要是容器、迭代器和算法三个部分:
STL 的基本观念就是将数据和操作分离。
3、容器(Containers)
一个容器就是一些特定类型对象的集合,是用来管理某类对象的,从C++11标准以来,C++中STL定义的几种容器的效率非常高,优化的非常好,完全没有必要自己去定义类似的数据结构,了解使用它们,可以满足90%的日常编程需要!本文是 基于C++11标准,基于《C++primer》参考 完成的。
常用的STL基本容器类型分为四类:
<
运算符来进行比较操作。==
运算符组织元素。在关键字类型的元素没有明显的序关系的情况下,无序容器是非常有用的。在某些应用中,维护元素的序代价非常高昂, 此时无序容器也很有用。使用无序容器通常更为简单(通常也会有更好的性能) 。其中,STL 提供的 最常用的:
四个 顺序容器:
四个 关联容器:
三种 适配器:
四种 无序容器:
容器类自动申请和释放内存,因此无需new和delete操作。
4、顺序容器(Sequence containers)
向容器中添加或删除元素可能会使指向容器元素的指针、引用或迭代器失效。失效的指针、引用或迭代器不再表示任何元素,使用它们是一种严重的程序设计错误。
vector
或 string
类型,且存储空间被重新分配,则指向容器的迭代器、指针和引用都会失效。如果存储空间未重新分配,指向插入位置之前元素的迭代器、指针和引用仍然有效,但指向插入位置之后元素的迭代器、指针和引用都会失效。deque
类型,添加到除首尾之外的任何位置都会使迭代器、指针和引用失效。如果添加到首尾位置,则迭代器会失效,而指针和引用不会失效。list
或 forward_list
类型,指向容器的迭代器、指针和引用仍然有效。list
或 forward_list
类型,指向容器其他位置的迭代器、指针和引用仍然有效。deque
类型,删除除首尾之外的任何元素都会使迭代器、指针和引用失效。如果删除尾元素,则尾后迭代器失效,其他迭代器、指针和引用不受影响。如果删除首元素,这些也不会受影响。vector
或 string
类型,指向删除位置之前元素的迭代器、指针和引用仍然有效。但尾后迭代器总会失效。vector(向量):事实上和数组差不多,但比数组更优越,一般来说数组不能动态拓展,因此在程序运行的时候不是浪费内存,就是造成越界,而 vector
正好弥补了这个缺陷,它的特征是相当于可变大小的数组(动态数组)。由于元素是连续存储的,随机访问快,在末端插入和删除快,但在中间插入和删除慢。
优缺点:
优点:支持随机访问,即
[]
操作和.at()
,查询效率高。 缺点:当向头部或中部,插入或删除元素,插入效率低。
需要导入头文件 #include <vector>
。
在这里插入图片描述
C++标准要求 vector
应该能在运行时高效快速地添加元素,因此定义 vector
对象的大小没有必要,事实上性能可能更差,只有一种例外情况,就是所有元素的值都一样!一旦元素的值有所不同,更有效的办法是先定义一个空的 vector
对象,再在运行时向其中添加具体值。
开始的时候创建空的 vector
对象,在运行时再动态添加元素,这一做法与C语言及其他大多数语言中内置数组类型的用法不同,特别是如果用惯了C或者Java,可以预计在创建 vector
对象时顺便指定其容量是最好的,然而事实上,通常的情况是恰恰相反。
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> ivec1;
for (int i = 0; i<9; i++)
ivec1.push_back(i);
cout << ivec1.size() << endl;
for (int i = 0; i<ivec1.size(); i++)
cout << ivec1[i] << " ";
cout << endl;
system("pause");
return 0;
}
deque(双端队列):是一个更为复杂的数据结构,最大任务就是在这些分段的连续空间上,维护其整体连续的假象,并提供随机存取的接口。与 vector
类似,随机访问快,不过是在两端插入和删除快,但在中间插入和删除慢。
优缺点:
优点:支持随机访问,即
[]
操作和.at()
,查询效率高;当向两端,插入或删除元素,插入效率高。 缺点:当向中部,插入或删除元素,插入效率低。
需要导入头文件 #include <deque>
#include <iostream>
#include <deque>
using namespace std;
int main()
{
deque<int> ideq1;
for (int i = 0; i<9; i++)
ideq1.push_back(i);
cout << ideq1.size() << endl;
for (int i = 0; i<ideq1.size(); i++)
cout << ideq1[i] << " ";
cout << endl;
system("pause");
return 0;
}
list(列表):由 deque
实现而成,元素也存放在堆中。设计目的是令容器任何位置的添加和删除操作都很快速,作为代价不支持元素的随机访问——为了访问一个元素,只能遍历整个容器。
优缺点:
优点:内存不连续,动态操作,可在任意位置插入或删除且效率高。 缺点:不支持随机访问。
需要导入头文件 #include <list>
#include <iostream>
#include <list>
using namespace std;
int main(int argc, char* argv[])
{
list<char> ilist;
for (char c = 'a'; c <= 'z'; ++c)
ilist.push_back(c);
cout << ilist.size() << endl;
while (!ilist.empty())
{
cout << ilist.front() << " ";
ilist.pop_front();
}
system("pause");
return 0;
}
string(字符串):表示可变长的字符序列,事实上和 vector
差不多。由于元素是连续存储的,随机访问快,在末端插入和删除快,但在中间插入和删除慢。
优缺点:
优点:支持随机访问,即
[]
操作和.at()
,查询效率高。 缺点:当向头部或中部,插入或删除元素,插入效率低。
需要导入头文件 #include <string>
。
#include <iostream>
#include <string>
using namespace std;
int main()
{
string ivec1;
for (int i = 0; i<9; i++)
ivec1.push_back('i');
cout << ivec1.size() << endl;
for (int i = 0; i<ivec1.size(); i++)
cout << ivec1[i] << " ";
cout << endl;
system("pause");
return 0;
}
在这里插入图片描述
容器选择原则:
vector
。list
或 forward_list
。vector
或 deque
。deque
。
vector
追加数据,再调用标准库的 sort
函数重排元素,从而避免在中间位置添加元素。list
。输入完成后将 list
中的内容拷贝到 vector
中。vector
和 list
的公共操作:使用迭代器,不使用下标操作,避免随机访问。这样在必要时选择 vector
或 list
都很方便。5、关联容器(Associative containers)
set(集合):由红黑树实现,其中每个元素只包含一个关键字并依据其值自动排序,支持高效的关键字查询操作,每个元素值只能出现一次,不允许重复。插入和删除效率比用其他序列容器高,因为对于关联容器来说,不需要做内存拷贝和内存移动。
multiset(多重集合):唯一的区别是插入的元素可以相同。
优缺点:
优点:关键字查询高效,且元素唯一,以及能自动排序。 缺点:每次插入值的时候,都需要调整红黑树,效率有一定影响。
需要导入头文件 #include <set>
。
#include <iostream>
#include <set>
using namespace std;
int main(int argc, char* argv[])
{
set<int> iset;
iset.insert(3);
iset.insert(1);
iset.insert(2);
iset.insert(1);
set<int>::iterator it;
cout << iset.size() << endl;
for (it = iset.begin(); it != iset.end(); it++)
{
cout << *it << " ";
}
cout << endl;
system("pause");
return 0;
}
map(映射):由红黑树实现,其中每个元素都是一些 键值对(key-value):关键字起索引作用,值表示与索引相关联的数据。每个元素有一个键,是排序准则的基础。每一个键只能出现一次,不允许重复。插入和删除效率比用其他序列容器高,因为对于关联容器来说,不需要做内存拷贝和内存移动。
multimap(多重映射):唯一的区别是插入的元素(值)可以相同,即同一个键可以对应多个值。
优缺点:
优点:关键字查询高效,且元素唯一,以及能自动排序。把一个值映射成另一个值,可以创建字典。 缺点:每次插入值的时候,都需要调整红黑树,效率有一定影响。
需要导入头文件 #include <map>
。
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main(int argc, char* argv[])
{
map<int, string> imap;
imap.insert({ 3, "张三" });
imap.insert({ 4, "李四" });
imap.insert({ 1, "王二麻子" });
imap.insert({ 2, "小淘气" });
map<int, string>::iterator it;
for (it = imap.begin(); it != imap.end(); it++)
{
printf("学号:%d 姓名:%s\n", (*it).first, (*it).second.c_str());
}
system("pause");
return 0;
}
6、适配器(Adaptor)
stack(栈):LIFO(后进先出)。
需要导入头文件 #include <stack>
。
《C++ Primer》习题参考答案:第9章 - 顺序容器 最后一题。
queue(队列):FIFO(先进先出),即普通的缓冲区(buffer)。
priority_queue(优先级队列):基于程序员提供的排序准则定义不同的优先权。
需要导入头文件 #include <queue>
。
7、无序容器(Unordered associative container)
无序容器:在关键字类型的元素没有明显的序关系的情况下,无序容器是非常有用的。在某些应用中,维护元素的序代价非常高昂, 此时无序容器也很有用。事实上使用无序容器通常更为简单(通常也会有更好的性能) 。如果关键字类型固有就是无序的,或者性能测试发现问题可以用哈希技术解决,就可以使用无序容器。
通常可以用一个无序容器替换对应的有序容器,反之亦然。但是输出(通常)会不同。
8、sizeof、size和capacity
sizeof
操作符统计的是容器 vector<int>
的大小;size()
操作符统计的是容器(vector)内元素的大小;capacity
操作符统计的是容器(vector)能存储的容量大小。#include <iostream>
#include <vector>
using namespace std;
int main(int argc, char* argv[])
{
vector<int> ivec;
cout << sizeof(ivec) << endl;
cout << ivec.size() << endl;
cout << ivec.capacity() << endl;
for (int i = 0; i<10; i++)
ivec.push_back(1);
cout << sizeof(ivec) << endl;
cout << ivec.size() << endl;
cout << ivec.capacity() << endl;
system("pause");
return 0;
}
在这里插入图片描述
另外:
reserve()
操作符统计的是指定容器内能存储元素的数量;resize()
操作符统计的是重新指定容器内有效元素的数量;9、总结
最后送你两张图: