C++中容器类是属于标准模板库中的内容,有必要回顾下标准模板库。STL = Standard Template Library,标准模板库,惠普实验室开发的一系列软件的统称。从根本上说,STL是一些“容器”的集合,这些“容器”有list,vector,set,map等,STL也是算法和其他一些组件的集合。

STL被内建在编译系统之内。 

在C++标准中,STL被组织为下面的13个头文件:

<algorithm>、<deque>、<functional>、<iterator>、<vector>、<list>、<map>、<memory>、<numeric>、<queue>、<set>、<stack>和<utility>。


STL的一个重要特点是数据结构和算法的分离。尽管这是个简单的概念,但这种分离确实使得STL变得非常通用。例如,由于STL的sort()函数是完全通用的,你可以用它来操作几乎任何数据集合,包括链表,容器和数组。

STL另一个重要特性是它不是面向对象的。为了具有足够通用性,STL主要依赖于模板而不是封装,继承和虚函数(多态性)——OOP的三个要素。你在STL中找不到任何明显的类继承关系。这好像是一种倒退,但这正好是使得STL的组件具有广泛通用性的底层特征。另外,由于STL是基于模板,内联函数的使用使得生成的代码短小高效。


三个基本的STL组件:

1)    迭代器提供了访问容器中对象的方法。例如,可以使用一对迭代器指定list或vector中的一定范围的对象。迭代器就如同一个指针。事实上,C++的指针也是一种迭代器。但是,迭代器也可以是那些定义了operator*()以及其他类似于指针的操作符地方法的类对象。

2)   容器是一种数据结构,如list,vector,和deques ,以模板类的方法提供。为了访问容器中的数据,可以使用由容器类输出的迭代器。

3)   算法是用来操作容器中的数据的模板函数。例如,STL用sort()来对一个vector中的数据进行排序,用find()来搜索一个list中的对象。函数本身与他们操作的数据的结构和类型无关,因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用。


/*-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------*/


Qt容器类

像MFC一样,Qt provides its own container classes, so for Qt programs we can use both the Qt and the STL containers. The main advantages of the Qt containers are that they behave the same on all platforms and that they are implicitly shared (就是说也可以在Qt中使用STL,但是出了问题不关Qt的事情。).


Qt容器类的好处在于,它提供了平台无关的行为,以及隐式数据共享技术。所谓平台无关,即Qt容器类不因编译器的不同而具有不同的实现;所谓“隐式数据共享”,也可以称作“写时复制copy on write”,这种技术允许在容器类中使用传值参数,而不会发生额外的性能损失。

Qt支持两种风格的迭代器——Java-style和STL-style,Java-style的迭代器更容易使用,而STL-style的迭代器可以同Qt和STL中的算法联合使用,更为强大。

Qt provides the following sequential containers: QList, QLinkedList, QVector, QStack, and QQueue. associative containers: QMap, QMultiMap, QHash, QMultiHash, and QSet.


容器类共享公共的接口,这使标准库更容易学习,只要学会其中一种类型就能运用另一种类型。标准库定义了三种顺序容器类型:vector、list 和 deque(是双端队列“double-ended queue”的简写,发音为“deck”)。它们的差别在于访问元素的方式,以及添加或删除元素相关操作的运行代价。


1,所有的容器都是类模板。要定义某种特殊的容器,必须在容器名后加一对尖括号,尖括号里面提供容器中存放的元素的类型:

vector<string> svec; // empty vector that can hold strings  

list<int> ilist; // empty list that can hold ints  

deque<Sales_item> items; // empty deque that holds Sales_items  

vector 是同一种类型的对象的集合,每个对象都有一个对应的整数索引值。和 string 对象一样,标准库将负责管理与存储元素相关的内存。容器中的所有对象都必须是同一种类型的。vector是标准C++建议替代C数组的动态数组模型,它维护的是一个连续线性空间。特点支持快速随机访问。


List 就是一双向链表,可高效地进行插入删除元素。包括构造、方法等。相对于vector的连续线性空间,list就显得复杂许多,与向量(vector)相比, 它允许快速的插入和删除,且每次插入或删除一个元素,就配置或释放一个元素空间。因此,list对于空间的运用绝对的精准,一点也不浪费。而且,对于任何位置的元素插入或元素移除,list永远是常数时间。特点支持快速插入/删除。

deque容器类,vector是单向开口的连续线性空间,deque则是以中双向开口的连续线性空间。所谓双向开口,意思是可以在头尾两端分别做元素的插入和删除操作。从技术的角度而言,vector当然也可以在头尾两端进行操作,但是其头部操作效率奇差、令人无法接受。deque是由一段一段的定量连续空间构成。


2,这里vector<vector<T> >后面两个尖括号要空格。《C++ Primer 4th》 9.1.1节讲述的有连续容器类的构造函数和一些特殊的构造方法。

  1. C<T> c;  
  2. //创建一个名为 c 的空容器。C 是容器类型名,如 vector,T 是元素类型,如 int 或 string 适用于所有容器。  
  3.   
  4. C c(c2);  
  5. //创建容器 c2 的副本 c;c 和 c2 必须具有相同的容器类型,并存放相同类型的元素。适用于所有容器。  
  6.   
  7.   
  8. C c(b, e);  
  9. //创建 c,其元素是迭代器 b 和 e 标示的范围内元素的副本。适用于所有容器。  
  10.   
  11. C c(n, t);  
  12. //用 n 个值为 t 的元素创建容器 c,其中值 t 必须是容器类型 C 的元素类型的值,或者是可转换为该类型的值。只适用于顺序容器 
  13.   
  14. C c(n);  
  15. //创建有 n 个值初始化(第 3.3.1 节)(value-initialized)元素的容器 c。只适用于顺序容器 

Containers of Containers 容器的容器

注意,在指定容器元素为容器类型时,必须如下使用空格:

  1. vector< vector<string> > lines; // ok: space required between close >  
  2. vector< vector<string>> lines; // error: >> treated as shift operator  

3,大多数类型都可用作容器的元素类型。容器元素类型必须满足以下两个约束:
    1、The element type must support assignment.
    元素类型必须支持赋值运算。
    2、We must be able to copy objects of the element type.
    元素类型的对象必须可以复制。


4,Each sequential container defines a set of useful typedefs and supports operations that let us
每种顺序容器都提供了一组有用的类型定义以及以下操作:
    1,Add elements to the container.           在容器中添加元素。 7
    2,Delete elements from the container.   在容器中删除元素。 10
    3,Determine the size of the container.   设置容器大小。         11
    4,Fetch the first and last elements from the container, if any.(如果有的话)获取容器内的第一个和最后一个元素。


5,容器定义的类型别名 Container Typedefs(或许应该讲迭代器的时候再详述)


6,容器的 begin 和 end 操作 

c.begin()

    Yields an iterator referring to the first element in c

返回一个迭代器,它指向容器 c 的第一个元素

c.rbegin()
Yields a reverse iterator referring to the last element in c

返回一个逆序迭代器,它指向容器 c 的最后一个元素

c.end()  
  
Yields an iterator referring to the one past the last element in c
返回一个迭代器,它指向容器 c 的最后一个元素的下一位置
c.rend()    

Yields a reverse iterator referring one past (i.e., before) the first element in c
返回一个逆序迭代器,它指向容器 c 的第一个元素前面的位置


7,在顺序容器中添加元素
  1)push_back。所有顺序容器都支持 push_back,提供在容器尾部插入一个元素的功能。下面的循环每次读入一个 string 类型的值,并存放在 text_word: 对象中:

  1. // read from standard input putting each word onto the end of container  
  2. string text_word;  
  3. while (cin >> text_word)  
  4.      container.push_back(text_word);  

  2) push_back 运算,list 和 deque 容器类型还提供了类似的操作:push_front。这个操作实现在容器首部插入新元素的功能。例如:

  1. list<int> ilist;  
  2. // add elements at the end of ilist  
  3. for (size_t ix = 0; ix != 4; ++ix)  
  4.      ilist.push_back(ix);  

Key Concept: Container Elements Are Copies
关键概念:容器元素都是副本

  3)insert 操作在容器中指定位置添加元素,insert 操作有三个版本。


I, c.insert(p,t)

Inserts element with value t before the element referred to by iterator p. Returns an iterator referring to the element that was added.
在迭代器 p 所指向的元素前面插入值为 t 的新元素。返回指向新添加元素的迭代器

下面的程序就是使用了这个版本的 insert 函数在容器首部插入新元素:

  1. vector<string> svec;  
  2. list<string> slist;  
  3. string spouse("Beth");  
  4.   
  5. // equivalent to calling slist.push_front (spouse);  
  6. slist.insert(slist.begin(), spouse);  
  7.   
  8. // no push_front on vector but we can insert before begin()  
  9. // warning: inserting anywhere but at the end of a vector is an expensive operation  
  10. svec.insert(svec.begin(), spouse);  


  1. //这个版本的 insert 函数返回指向新插入元素的迭代器。可使用该返回值在容器中的指定位置重复插入元素:  
  2.   
  3.       list<string> lst;  
  4.       list<string>::iterator iter = lst.begin();  
  5.       while (cin >> word)  
  6.          iter = lst.insert(iter, word); // same as calling push_front  


II, c.insert(p,n,t)

Inserts n elements with value t before the element referred to by iterator p. Returns void.
在迭代器 p 所指向的元素前面插入 n 个值为 t 的新元素。返回 void 类型


III, c.insert(p,b,e)
    
Inserts elements in the range denoted by iterators b and e before the element referred to by iterator p. Returns void.
在迭代器 p 所指向的元素前面插入由迭代器 b 和 e 标记的范围内的元素。返回 void 类型。


8, 任何 insert 或 push 操作都可能导致迭代器失效。当编写循环将元素插入到vector 或deque 容器中时,程序必须确保迭代器在每次循环后都得到更新。


9,Accessing Elements访问元素

c.back()
    
Returns a reference to the last element in c. Undefined if c is empty.
返回容器 c 的最后一个元素的引用。如果 c 为空,则该操作未定义
c[n]
    
Returns a reference to the element indexed by n.
返回下标为 n 的元素的引用
Undefined if n <0 or n >= c.size().
如果 n <0 或 n >= c.size(),则该操作未定义
Valid only for vector and deque.
只适用于 vector 和 deque 容器
c.front()
    
Returns a reference to the first element in c. Undefined if c is empty.
返回容器 c 的第一个元素的引用。如果 c 为空,则该操作未定义
c.at(n)
    
Returns a reference to the element indexed by n. If index is out of range, throws out_of_range exception.
返回下标为 n 的元素的引用。如果下标越界,则该操作未定义
Valid only for vector and deque.
只适用于 vector 和 deque 容器

e.g.

  1. // check that there are elements before dereferencing an iterator  
  2. // or calling front or back  
  3. if (!ilist.empty()) {  
  4.      // val and val2 refer to the same element  
  5.     list<int>::reference val = *ilist.begin();  
  6.     list<int>::reference val2 = ilist.front();  
  7.   
  8.      // last and last2 refer to the same element  
  9.      list<int>::reference last = *--ilist.end();  
  10.      list<int>::reference last2 = ilist.back(); }  

10,   Erasing Elements 删除元素

c.erase(p)Removes element referred to by the iterator p.

删除迭代器 p 所指向的元素

Returns an iterator referring to the element after the one deleted, or an off-the-end iterator if p referred to the last element. Undefined if p is an off-the-end iterator.

返回一个迭代器,它指向被删除元素后面的元素。如果 p 指向容器内的最后一个元素,则返回的迭代器指向容器的超出末端的下一位置。如果 p 本身就是指向超出末端的下一位置的迭代器,则该函数未定义
c.erase(b,e)
   


Removes the range of elements denoted by the iterators b and e.

删除迭代器 b 和 e 所标记的范围内所有的元素

Returns an iterator referring after the last one in the range that was deleted, or an off-the-end iterator if e is itself an off-the-end iterator.

返回一个迭代器,它指向被删除元素段后面的元素。如果 e 本身就是指向超出末端的下一位置的迭代器,则返回的迭代器也指向容器的超出末端的下一位置
c.clear()Removes all the elements in c. Returns void.
删除容器 c 内的所有元素。返回 void
c.pop_back()
   
Removes the last element in c. Returns void. Undefined if c is empty.
删除容器 c 的最后一个元素。返回 void。如果 c 为空容器,则该函数未定义
c.pop_front()Removes the first element in c. Returns void. Undefined if c is empty.
删除容器 c 的第一个元素。返回 void。如果 c 为空容器,则该函数未定义
Valid only for list or deque.
只适用于 list 或 deque 容器


e.g.

  1. while (!ilist.empty()) {  
  2.      process(ilist.front()); // do something with the current top of ilist  
  3.      ilist.pop_front();      // done; remove first element  
  4. }  

  1. string searchValue("Quasimodo");  
  2. list<string>::iterator iter =  
  3.         find(slist.begin(), slist.end(), searchValue);  
  4.   
  5. if (iter != slist.end())  
  6.       slist.erase(iter);  


11, Sequential Container Size Operations顺序容器的大小操作

c.size()

Returns the number of elements in c. Return type is c::size_type.

返回容器 c 中的元素个数。返回类型为 c::size_type

c.max_size()

Returns maximum number of elements c can contain. Return type isc::size_type.

返回容器 c 可容纳的最多元素个数,返回类型为 c::size_type

c.empty()

Returns a bool that indicates whether size is 0 or not.

返回标记容器大小是否为 0 的布尔值

c.resize(n)

Resize c so that it has n elements. If N < c.size(), the excess elements are discarded. If new elements must be added, they are value initialized.

调整容器 c 的长度大小,使其能容纳 n 个元素,如果 n < c.size(),则删除多出来的元素;否则,添加采用值初始化的新元素

c.resize(n,t)

Resize c to have n elements. Any elements added have valuet.

调整容器 c 的长度大小,使其能容纳 n 个元素。所有新添加的元素值都为 t

 

e.g.

  1. list<int> ilist(10, 42);   // 10 ints: each has value 42  
  2.   
  3. ilist.resize(15);          // adds 5 elements of value 0 to back of ilist  
  4.   
  5. ilist.resize(25, -1);      // adds 10 elements of value -1 to back of ilist  
  6.   
  7. ilist.resize(5);           // erases 20 elements from the back of ilist  

12, Sequential Container Assignment Operations 顺序容器的赋值操作

c1 = c2

Deletes elements in c1 and copies elements from c2 intoc1.c1 andc2must be the same type.

删除容器 c1 的所有元素,然后将 c2 的元素复制给 c1c1 和c2 的类型(包括容器类型和元素类型)必须相同

c1.swap(c2)

Swaps contents: After the call c1 has elements that were inc2, andc2has elements that were inc1c1 andc2 must be the same type. Execution time usuallymuch faster than copying elements fromc2toc1.

交换内容:调用完该函数后,c1 中存放的是 c2 原来的元素,c2 中存放的则是c1 原来的元素。c1 和c2 的类型必须相同。该函数的执行速度通常要比将c2 复制到c1 的操作快

c.assign(b,e)

Replaces the elements in c by those in the range denoted by iteratorsb ande. The iteratorsb and e must not refer to elements inc.

重新设置 c 的元素:将迭代器 b 和 e 标记的范围内所有的元素复制到c中。b 和e 必须不是指向c 中元素的迭代器

c.assign(n,t)

Replaces the elements in c by n elements with valuet.

将容器 c 重新设置为存储 n 个值为 t 的元素


Qt容器类


1,Qt提供了它自己的一套容器类,这就是说,在Qt的应用程序中,我们可以使用标准C++的STL,也可以使用Qt的容器类。Qt容器类的好处在于,它提供了平台无关的行为,以及隐式数据共享技术。所谓平台无关,即Qt容器类不因编译器的不同而具有不同的实现;所谓“隐式数据共享”,也可以称作“写时复制copy on write”,这种技术允许在容器类中使用传值参数,而不会发生额外的性能损失。Qt容器类提供了类似Java的遍历器语法,同样也提供了类似STL的遍历器语法,以方便用户选择自己习惯的编码方式。最后一点,在一些嵌入式平台,STL往往是不可用的,这时你就只能使用Qt提供的容器类,除非你想自己创建。


2,QVector<T>是一个类似数组的容器,它将数据存储在连续内存区域。同C++数组不同之处在于,QVector<T>知道它自己的长度,并且可以改变大小。对于获取随机位置的数据,或者是在末尾处添加数据,QVector<T>的效率都是很高的,但是,在中间位置插入数据或者删除数据,它的效率并不是很高。在内存中QVector<T>的存储类似下图(出自C++ GUI Programming with Qt4, 2nd Edition):



以给定大小初始化:

  1. QVector<double> vect(3);  
  2. vect[0] = 1.0;  
  3. vect[1] = 0.540302;  
  4. vect[2] = -0.416147;  

初始化后,用append函数添加容器元素:

  1. QVector<double> vect;  
  2. vect.append(1.0);  
  3. vect.append(0.540302);  
  4. vect.append(-0.416147);  

或者instead of append():

	vect << 1.0 << 0.540302 << -0.416147;

One way to iterate over the vector's items is to use [] and count():

	double sum = 0.0;
	for (int i = 0; i < vect.count(); ++i)
    		sum += vect[i];

3,QLinekdList<T>是另外一种顺序存储容器。在数据结构中,这是一个链表,使用指针连接起所有数据。正如数据结构中所描述的那样,QLinkedList<T>的优点是数据的插入和删除很快,但是随机位置值的访问会很慢。与QVector<T>不同,QLinkedList<T>并没有提供重载的[]操作符,你只能使用append()函数,或者<<操作符进行数据的添加,或者你也可以使用遍历器

它的内存分布如下(出自C++ GUI Programming with Qt4, 2nd Edition):

使用迭代器插入元素:

	QLinkedList<QString> list;
	list.append("Clash");
	list.append("Ramones");

	QLinkedList<QString>::iterator i = list.find("Ramones");
	list.insert(i, "Tote Hosen");


4,QList<T>是一个同时拥有QVector<T>和QLinkedList<T>的大多数有点的顺序存储容器类。它像QVector<T>一样支持快速的随机访问,重载了[]操作符,提供了索引访问的方式;它像QLinkedList<T>一样,支持快速的添加、删除操作。除非我们需要进行在很大的集合的中间位置的添加、删除操作,或者是需要所有元素在内存中必须连续存储,否则我们应该一直使用Qlist<T>。


A typical iteration loop looks like this:

	QList<double> list;
	...
	QListIterator<double> i(list);
	while (i.hasNext()) {
    		do_something(i.next());
	}


5,QQueue<T> is one of Qt's generic container classes. It implements a queue data structure for items of a same type.
A queue is a first in, first out (FIFO) structure. Items are added to the tail of the queue using enqueue() and retrieved from the head using dequeue(). The head() function provides access to the head item without removing it.

一个简单例子:

  1. QQueue<int> queue;  
  2. queue.enqueue(1);  
  3. queue.enqueue(2);  
  4. queue.enqueue(3);  
  5. while (!queue.isEmpty())  
  6.     cout << queue.dequeue() << endl;  

6,整理到这里,发现Qt的文档真少。网上很多文章写的要不是翻译,要不是自己的问题解决方法。没有像c++ primer那样系统的总结。先整理到这里吧,只要熟悉STL了,QT的只要看看assistant就可以明了。先不玩了,搞到一个局域网聊天小软件源代码。先看看去


文章为转载,原文链接:点击打开链接

Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐