c++ STL容器总结之:vertor与list的应用

STL提供六大组件,彼此可以组合套用

1、容器(containers):各种数据结构,如vertor,list,deque,set,map.从实现的角度来看,STL容器是一种class template

2、算法(algorithms):各种算法如sort,search,copy,earse。STL算法是一种 function template。

3、迭代器(iterators):扮演容器与算法之间的胶合剂,是所谓的“泛型指针”。所有STL容器都有自己的专属的迭代器。

4、仿函数(functors):行为类似函数,可以作为算法的某些策略。从实现的角度来看,仿函数是一种重载了operator()的class或class template。

5、配接器(adapters):一种用来修饰容器或仿函数或迭代器借口的东西。例如queue和stack

6、配置器(allocators):负责空间的配置与管理。配置器是一个实现了动态空间分配、空间管理、空间释放的class template。

STL是建立在泛化之上的。数组泛化为容器,参数化了所包含的对象的类型。函数泛化为算法,参数化了所用的迭代器的类型。指针泛化为迭代器,参数化了所指向的对象的类型。

vector、string、deque和list被称为标准序列容器,

set、multiset、map和multimap是标准关联容器。

非标准序列容器slist和rope。slist是一个单向链表,rope本质上是一个重型字符串。

非标准关联容器hash_set、hash_multiset、hash_map和hash_multimap。

标准非STL容器,包括数组、bitset、valarray、stack、queue和priority_queue。

迭代器被分成五个种类:

输入迭代器是每个迭代位置只能被读一次的只读迭代器。

输出迭代器是每个迭代位置只能被写一次的只写迭代器。

输入和输出迭代器被塑造为读和写输入和输出流(例如,文件)。

前向迭代器有输入和输出迭代器的能力,但是它们可以反复读或写一个位置。

双向迭代器就像前向迭代器,除了它们的后退可以像前进一样容易。标准关联容器都提供双向迭代器。list也有。

连续内存容器(也叫做基于数组的容器)在一个或多个(动态分配)的内存块中保存它们的元素。如果一个新元素被查入或者已存元素被删除,其他在同一个内存块的元素就必须向上或者向下移动来为新元素提供空间或者填充原来被删除的元素所占的空间。这种移动影响了效率和异常安全。标准的连续内存容器是vector、string和deque。非标准的rope也是连续内存容器。

基于节点的容器在每个内存块(动态分配)中只保存一个元素。容器元素的插入或删除只影响指向节点的指针,而不是节点自己的内容。所以当有东西插入或删除时,元素值不需要移动。表现为链表的容器——比如list和slist——是基于节点的,所有的标准关联容器也是(它们的典型实现是平衡树)。非标准的散列容器使用不同的基于节点的实现。

1、vector

vector和数组类似,它拥有一段连续的内存空间,并且起始地址不变,因此它能非常好的支持随机存取(即使用[]操作符访问其中的元素),但由于它的内存空间是连续的,所以在中间进行插入和删除会造成内存块的拷贝(复杂度是O(n)),另外,当该数组后的内存空间不够时,需要重新申请一块足够大的内存并进行内存的拷贝。这些都大大影响了vector的效率。

vector不是一种数据类型,而只是一个类模板,可用来定义任意多种数据类型。vector类型的每一种都指定了其保存元素的类型。因此,vector<int>和vector <string>都是数据类型。

vector对象的定义和初始化













vector<T>  v1;

vector保存类型为T的对象。默认构造函数v1为空。

vector<T> v2(v1);

v2是v1的一个副本。

vector<T> v3(n, i);

v3包含n个值为i的元素。

vector<int> ivec4(10, -1);     // 10 elements, each initialized to -1

vector<string> svec(10, "hi!"); // 10 strings, each initialized to "hi!"

vector的操作

























v.empty()

如果v为空,则返回true,否则返回false。

v.size()

返回v中元素的个数。

v.push_back(t)

在v的末尾增加一个值为t的元素。

v[n]

返回v中位置为n的元素。

v1 = v2

把v1的元素替换为v2中元素的副本。

v1 == v2

如果v1与v2相等,则返回true。

!=, <, <=, >, >=

保持这些操作符惯有的含义。

向vector添加元素:


代码如下:

string word;

vector<string> text;        // empty vector

while (cin >> word) {

text.push_back(word);  // append word to text

}
  vector的下标操作:

for (vector<int>::size_type ix = 0; ix != ivec.size(); ++ix)

ivec[ix] = 0;

vector迭代器

每种容器都定义了一对命名为begin和end的函数,用于返回迭代器。如果容器中有元素的话,由begin返回的迭代器指向第一个元素:


代码如下:

vector<int>::iterator iter = ivec.begin();

由end操作返回的迭代器指向vector的“末端元素的下一个”。通常称为超出末端迭代器(off-the-end iterator),表明它指向了一个不存在的元素。如果vector为空,begin返回的迭代器与end返回的迭代器相同。


代码如下:

for (vector<int>::iterator iter = ivec.begin(); iter != ivec.end(); ++iter)

*iter = 0;  // set element to which iter refers to 0

const_iterator

前面的程序用vector::iterator改变vector中的元素值。每种容器类型还定义了一种名为const_iterator的类型,该类型只能访问容器内元素,但不能改变其值。


代码如下:

for (vector<string>::const_iterator iter = text.begin();  iter != text.end(); ++ iter)

*iter = " ";     // error: *iter is const

2、list

list是由数据结构中的双向链表实现的,因此它的内存空间可以是不连续的。因此只能通过指针来进行数据的访问,这个特点使得它的随机存取变的非常没有效率,需要遍历中间的元素,搜索复杂度O(n),因此它没有提供[]操作符的重载。但由于链表的特点,它可以以很好的效率支持任意地方的删除和插入。

list::iterator与vector::iterator的一些不同:


代码如下:

#include <iostream>
#include <vector>
#include <list>
using namespace std;

int main( void )
{
        vector<int> v; 
        list<int> l;

for (int i=0; i<8; i++)     //往v和l中分别添加元素
        {
                v.push_back(i);
                l.push_back(i);
        }

cout << "v[2] = " << v[2] << endl;
        //cout << "l[2] = " << l[2] << endl;       //编译错误,list没有重载[]
        cout << (v.begin() < v.end()) << endl;
        //cout << (l.begin() < l.end()) << endl;   //编译错误,list::iterator没有重载<或>
        cout << *(v.begin() + 1) << endl;

vector<int>::iterator itv = v.begin();
        list<int>::iterator itl = l.begin();
        itv = itv + 2;
        //itl = itl + 2;                  //编译错误,list::iterator没有重载+
        itl++;itl++;                    //list::iterator中重载了++,只能使用++进行迭代访问。
        cout << *itv << endl;
        cout << *itl << endl;

return 0;
}

由于vector拥有一段连续的内存空间,能非常好的支持随机存取,因此vector<int>::iterator支持“+”、“+=”、“<”等操作符。

而list的内存空间可以是不连续,它不支持随机访问,因此list<int>::iterator则不支持“+”、“+=”、“<”等操作符运算,因此代码20、26行会有编译错误。只能使用“++”进行迭代,例如代码27行,使用两次itl++来移动itl。还有list也不支持[]运算符,因此代码18行出现编译错误。

总之,如果需要高效的随即存取,而不在乎插入和删除的效率,使用vector;如果需要大量的插入和删除,而不关心随即存取,则应使用list。

vector拥有一段连续的内存空间,因此支持随机存取,如果需要高效的随即存取,而不在乎插入和删除的效率,使用vector。

list拥有一段不连续的内存空间,因此支持随机存取,如果需要大量的插入和删除,而不关心随即存取,则应使用list。当大部分插入和删除发生在序列的头或尾时可以选择deque这种数据结构。

(0)

相关推荐

  • C++ STL入门教程(7) multimap、multiset的使用

    一.multimap(一对多索引) C++ multimap和map所支持的操作相同(除了multimap不支持下标运算),但是multimap允许重复的元素. 完整程序代码: /*请务必运行以下程序后对照阅读*/ ///头文件依旧是map #include <map> #include <string> #include <iostream> using namespace std; int main() { ///1. 初始化 multimap<int, st

  • C++ STL list 遍历删除出错解决方案

    C++ STL list 遍历删除崩溃 错误用法一 下面这种用法会在for的地方崩溃,分析 第一次for循环的时候 it=0,当t.erase(it)执行完成之后 it就变成了 -17891602 表明it不能再作为迭代器进行运算,自然会报错. #include <map> #include <list> using namespace std; typedef std::list<int > TESTLIST; int _tmain(int argc, _TCHAR*

  • C++ STL入门教程(6) set(集合)的使用方法

    一.简介 集合(Set)是一种包含已排序对象的关联容器,不允许有重复元素. 二.完整程序代码 /*请务必运行以下程序后对照阅读*/ #include <set> #include <iostream> using namespace std; int main() { ///1. 初始化 set<int> num; set<int>::iterator iter; cout << num.max_size() << endl;///s

  • 浅谈c++中的stl中的map用法详解

    Map是STL的一个关联容器,它提供一对一(其中第一个可以称为关键字,每个关键字只能在map中出现一次,第二个可能称为该关键字的值)的数据处理能力,由于这个特性,它完成有可能在我们处理一对一数据的时候,在编程上提供快速通道.这里说下map内部数据的组织,map内部自建一颗红黑树(一种非严格意义上的平衡二叉树),这颗树具有对数据自动排序的功能,所以在map内部所有的数据都是有序的,后边我们会见识到有序的好处. 下面举例说明什么是一对一的数据映射.比如一个班级中,每个学生的学号跟他的姓名就存在着一一

  • C++ STL入门教程(1) vector向量容器使用方法

    一.简介 Vectors 包含着一系列连续存储的元素,其行为和数组类似. 访问Vector中的任意元素或从末尾添加元素都可以在O(1)内完成,而查找特定值的元素所处的位置或是在Vector中插入元素则是O(N). 二.完整程序代码 /*请务必运行以下程序后对照阅读*/ #include <vector> #include <iostream> #include <algorithm> #include <stdexcept> using namespace

  • C++在成员函数中使用STL的find_if函数实例

    本文实例讲述了C++在成员函数中使用STL的find_if函数的方法.分享给大家供大家参考.具体方法分析如下: 一般来说,STL的find_if函数功能很强大,可以使用输入的函数替代等于操作符执行查找功能(这个网上有很多资料,我这里就不多说了). 比如查找一个数组中的奇数,可以用如下代码完成(具体参考这里:http://www.cplusplus.com/reference/algorithm/find_if/): #include <iostream> #include <algori

  • C++ 关于STL中sort()对struct排序的方法

    前言 一直没有系统去看过c++,因为懂得一些c的基本语法,在实际编程中用到c++,只能用到哪些看哪些,发现这样虽然能够完成大部分工作,但是有时候效率实在太低,比如说这节要讲的Std::sort()函数的使用,调了半天才调通.开通c/c++序列博客是记录在使用c++中一些难题,避免以后重犯错,当然以后会尽量挤出时间来较系统学习下c++. 开发环境:QtCreator2.5.1+OpenCV2.4.3 实验基础 首先来看看std中的快速排序算法sort的使用方法: template <class R

  • C++ STL入门教程(3) deque双向队列使用方法

    一.简介 deque(Double Ended Queues,双向队列)和向量很相似,但是它允许在容器头部快速插入和删除(就像在尾部一样). 二.完整程序代码 /*请务必运行以下程序后对照阅读*/ #include <deque> #include <iostream> #include <algorithm> #include <stdexcept> using namespace std; void print(int num) { cout <&

  • 深入解析C++ STL中的常用容器

    STL是C/C++开发中一个非常重要的模板,而其中定义的各种容器也是非常方便我们大家使用.下面,我们就浅谈某些常用的容器.这里我们不涉及容器的基本操作之类,只是要讨论一下各个容器其各自的特点.STL中的常用容器包括:顺序性容器(vector.deque.list).关联容器(map.set).容器适配器(queue.stac). 1.顺序性容器 (1)vectorvector是一种动态数组,在内存中具有连续的存储空间,支持快速随机访问.由于具有连续的存储空间,所以在插入和删除操作方面,效率比较慢

  • C++ STL入门教程(2) list双向链表使用方法(附程序代码)

    一.简介 "Unlike other standard sequence containers, list and forward_list objects are specifically designed to be efficient inserting and removing elements in any position, even in the middle of the sequence." Lists将元素按顺序储存在链表中.与向量(vector)相比, 它允许快速

随机推荐