精华内容
下载资源
问答
  • 18.java 容器都有哪些

    千次阅读 2020-07-27 18:34:52
    JAVA容器类概述 1.常用容器分类 JAVA中的容器类主要分为两大类,一类是Map类,一类是Collections类,他们有一个共同的父接口Iterator,它提供基本的遍历,删除元素操作。Iterator还有一个子接口LinkIterator,它...

    JAVA容器类概述

    1.常用容器分类

    在这里插入图片描述
    JAVA中的容器类主要分为两大类,一类是Map类,一类是Collection类,他们有一个共同的父接口Iterator,它提供基本的遍历,删除元素操作。Iterator还有一个子接口LinkIterator,它提供双向的遍历操作。

    Collection是一个独立元素的序列,这些元素都服从一条或多条规则,它有三个子接口List,Set和Queue。其中List必须按照插入的顺序保存元素、Set不能有重复的元素、Queue按照排队规则来确定对象的产生顺序(通常也是和插入顺序相同)

    Map是一组成对的值键对对象,允许用键来查找值。它允许我们使用一个对象来查找某个对象,也被称为关联数组,或者叫做字典。它主要包括HashMap类和TreeMap类。Map在实际开发中使用非常广,特别是HashMap,想象一下我们要保存一个对象中某些元素的值,如果我们在创建一个对象显得有点麻烦,这个时候我们就可以用上Map了,HashMap采用是散列函数所以查询的效率是比较高的,如果我们需要一个有序的我们就可以考虑使用TreeMap。

    2.Iterator类

    迭代器是一种设计模式,它是一个对象,它可以遍历并选择序列中的对象,而开发人员不需要了解该序列的底层结构。迭代器通常被称为“轻量级”对象,因为创建它的代价小。

    Java中的Iterator功能比较简单,并且只能单向移动:

    (1) 使用方法iterator()要求容器返回一个Iterator。第一次调用Iterator的next()方法时,它返回序列的第一个元素。注意:iterator()方法是java.lang.Iterable接口,被Collection继承。

    (2) 使用next()获得序列中的下一个元素。

    (3) 使用hasNext()检查序列中是否还有元素。

    (4) 使用remove()将迭代器新返回的元素删除。

    接口代码如下:

    public interface Iterator<E> {    
    public boolean hasNext();    
    public E next();    
    public void remove();}
    

    Iterator可以不用管底层数据具体是怎样存储的,都能够通过next()遍历整个容器,那么它是如何实现的呢?我们来具体分析下Java里AbstractList实现Iterator的源代码:

    public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> { 
    // List接口实现了Collection<E>, Iterable<E> 
      
        protected AbstractList() {  
        }  
        
        ...  
      
        public Iterator<E> iterator() {  
        return new Itr();  // 这里返回一个迭代器
        }  
      
        private class Itr implements Iterator<E> {  // 内部类Itr实现迭代器
           
        int cursor = 0;  
        int lastRet = -1;  
        int expectedModCount = modCount;  
      
       public boolean hasNext() {  // 实现hasNext方法
               return cursor != size();  
        }  
      
        public E next() {  // 实现next方法
                checkForComodification();  
            try {  
            E next = get(cursor);  
            lastRet = cursor++;  
            return next;  
            } catch (IndexOutOfBoundsException e) {  
            checkForComodification();  
           throw new NoSuchElementException();  
            }  
        }  
      
        public void remove() {  // 实现remove方法
            if (lastRet == -1)  
            throw new IllegalStateException();  
                checkForComodification();  
      
            try {  
            AbstractList.this.remove(lastRet);  
            if (lastRet < cursor)  
                cursor--;  
            lastRet = -1;  
            expectedModCount = modCount;  
           } catch (IndexOutOfBoundsException e) {  
           throw new ConcurrentModificationException();  
            }  
        }  
      
        final void checkForComodification() {  
            if (modCount != expectedModCount)  
            throw new ConcurrentModificationException();  
        }  
        }  
    }
    

    可以看到,实现next()是通过get(cursor),然后cursor++,通过这样实现遍历。

    这部分代码不难看懂,唯一难懂的是remove操作里涉及到的expectedModCount = modCount;

    在网上查到说这是集合迭代中的一种“快速失败”机制,这种机制提供迭代过程中集合的安全性。

    从源代码里可以看到增删操作都会使modCount++,通过和expectedModCount的对比,迭代器可以快速的知道迭代过程中是否存在list.add()类似的操作,存在的话快速失败!

    参考文章1
    参考文章2
    参考文章3
    参考文章4
    参考文章5
    参考文章6
    参考文章7

    参考文章8

    展开全文
  • 容器类实现的电话本

    2012-09-09 20:31:11
    实现电话号码本的管理和查询功能。号码本内预先存储了若干条联系人记录,记录内容包括联系人姓名和电话号码。...必须使用容器类作为内部数据结构,可自行选择合适的容器类; 必须把联系人记录定义成一个类;
  • java 容器都有哪些

    万次阅读 多人点赞 2019-07-27 18:36:57
    容器可以说是Java Core中比较重要的一部分了。 数组,String,java.util下的集合容器 ============================================================================== 数组长度限制为 Integer.Integer.MAX_...

    容器可以说是Java Core中比较重要的一部分了。

    数组,String,java.util下的集合容器

    ==============================================================================

    数组长度限制为 Integer.Integer.MAX_VALUE;

    String的长度限制: 底层是char 数组 长度 Integer.MAX_VALUE 线程安全的

    java.util下的集合容器

    这一块之所以重要是因为,各个接口的特性不同。下面说一下我对这些类的理解。

    Set下各种实现类对比

    HashSet基于哈希表实现,有以下特点:

              1.不允许重复

               2.允许值为null,但是只能有一个

               3.无序的。

               4.没有索引,所以不包含索引操作的方法

    LinkedHashSet跟HashSet一样都是基于哈希表实现。只不过linkedHashSet在hashSet的基础上多了一个链表,这个链表就是用来维护容器中每个元素的顺序的。有以下特点:

               1.不允许重复

               2.允许值为null,但是只能有一个

               3.有序的。

               4.没有索引,所以不包含索引操作的方法

    TreeSet是SortedSet接口的唯一实现类,是基于二叉树实现的。TreeSet可以确保集合元素处于排序状态。TreeSet支持两种排序方式,自然排序 和定制排序,其中自然排序为默认的排序方式。向TreeSet中加入的应该是同一个类的对象。有以下特点:

               1.不允许重复

               2.不允许null值

               3.没有索引,所以不包含索引操作的方法

    List下各种实现类对比。(这几个类都是有序的,允许重复的)

    ArrayList是基于数组实现的,其特点是查询快,增删慢。

            查询快是因为数组的空间是连续的,查询时只要通过首地址和下标很快就能找到元素。

            增删慢是因为数组是不能扩容的,一旦增加或者删除元素,内部操作就是新开辟一个数组把元素copy到新的数组,老的数   组等待被垃圾回收。

    以元素增加为例,我们看一下内部实现的源码:

    LinkedList是基于链表实现的。相比于ArrayList其特点是查询慢,增删快。

    查询慢:因为链表在内存中开辟的空间不一定是连续的(基本上不可能是连续的)所以链表实现的方式是每个元素节点都会存放自己的地址,数据以及下一个节点的地址,这样把所有的元素连接起来。所以当要查询元素时只能一个一个的往下找,相比于数组的首地址加下标会慢上不少。

    下面是链表的数据存储方式:假设有三个元素

    Vector也是基于数组实现的,相比于arrayList它是线程安全的。如果不考虑线程安全它,ArrayList性能更优。

    Map是双列集合的超类。也就是键值对形式。

    HashMap和Hashtable都实现了Map接口,但决定用哪一个之前先要弄清楚它们之间的分别。主要的区别有:线程安全性,同步(synchronization),以及速度。

    • HashMap几乎可以等价于Hashtable,除了HashMap是非synchronized的,并可以接受null(HashMap可以接受为null的键值(key)和值(value),而Hashtable则不行)。
    • HashMap是非synchronized,而Hashtable是synchronized,这意味着Hashtable是线程安全的,多个线程可以共享一个Hashtable;而如果没有正确的同步的话,多个线程是不能共享HashMap的。Java 5提供了ConcurrentHashMap,它是HashTable的替代,比HashTable的扩展性更好。
    • 另一个区别是HashMap的迭代器(Iterator)是fail-fast迭代器,而Hashtable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构(增加或者移除元素),将会抛出ConcurrentModificationException,但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并不是一个一定发生的行为,要看JVM。这条同样也是Enumeration和Iterator的区别。
    • 由于Hashtable是线程安全的也是synchronized,所以在单线程环境下它比HashMap要慢。如果你不需要同步,只需要单一线程,那么使用HashMap性能要好过Hashtable。
    • HashMap不能保证随着时间的推移Map中的元素次序是不变的。

    LinkedHashMap和hashMap的区别在于多维护了一个链表,用来存储每一个元素的顺序,就跟HashSet和LinkedHashSet差不多。

    HashMap通常比TreeMap快一点(树和哈希表的数据结构使然),建议多使用HashMap,在需要排序的Map时候才用TreeMap。

    相关面试题可以查看      面试题系列

    展开全文
  • Java容器类详解

    万次阅读 2018-04-18 21:26:36
    但是数组具有固定的尺寸,而通常来说,程序总是在运行时根据条件来创建对象,我们无法预知将要创建对象的个数以及类型,所以Java推出了容器类来解决这一问题。 Java容器的基本概念 Java容器类库是用来保存对象的,...

    Java的容器

    在Java中,我们想要保存对象可以使用很多种手段。最简单的就是数组。但是数组具有固定的尺寸,而通常来说,程序总是在运行时根据条件来创建对象,我们无法预知将要创建对象的个数以及类型,所以Java推出了容器类来解决这一问题。

    Java容器的基本概念

    Java容器类库是用来保存对象的,他有两种不同的概念:

    1. Collection,独立元素的序列,这些元素都服从一条或多条规则。List、Set以及Queue都是Collection的一种,List必须按照顺序保存元素,而Set不能有重复元素,Queue需要按照排队规则来确定对象的顺序。
    2. Map,Map是键值对类型,允许用户通过键来查找对象。Hash表允许我们使用另一个对象来查找某个对象。

    Collection和Map

    在Java容器中一共定义了2种集合, 顶层接口分别是Collection和Map。但是这2个接口都不能直接被实现使用,分别代表两种不同类型的容器。

    简单来看,Collection代表的是单个元素对象的序列,(可以有序/无序,可重复/不可重复 等,具体依据具体的子接口Set,List,Queue等);Map代表的是“键值对”对象的集合(同样可以有序/无序 等依据具体实现)

    Collection接口

    Collection是最基本的集合接口。Java SDK不提供直接继承自Collection的类,Java SDK提供的类都是继承自Collection的“子接口”。所有实现Collection接口的类都必须提供两个标准的构造函数:无参数的构造函数用于创建一个空的Collection,有一个 Collection参数的构造函数用于创建一个新的Collection,这个新的Collection与传入的Collection有相同的元素。后一个构造函数允许用户复制一个Collection。

    看一下Collection的部分源码 

       /** 
         * @return collection包含元素的个数 
         */
    int size();    
        /** 
         * @return 判断collection是否为空,为空返回true,不为空返回false 
         */  
    boolean isEmpty();  
        /** 
         *如果指定的元素的类型与这个集合不兼容,则抛出类型转换异常 
         *@return 判断collection是否包含元素与o相等,假如 o != null,判断set中是否有元素与o相等,
         * 有返回true,没有返回false。假如o == null,抛出空指针异常
         */  
     	boolean contains(Object o);  
     /** 
         * 返回包含ollection所有元素的Iterator 
         */ 
        Iterator<E> iterator();  
         /** 
         * 返回collection所有包含元素的array 
         */  
        Object[] toArray();  
       /** 
         * 返回一个包含collection元素的指定类型的数组 
         */ 
        <T> T[] toArray(T[] a);  
         /** 
         * 插入元素,假如当前collection中存在元素与e相等,那么保持原collection不改变,返回false, 
         * 否则插入元素,并返回true 
         */  
        boolean add(E e);  
          /** 
         * remove类似于这样的元素(o == null? e == null : o.equals(e)),并返回true 
         */  
        boolean remove(Object o);  
        boolean containsAll(Collection<?> c);  
        boolean addAll(Collection<? extends E> c);  
        boolean retainAll(Collection<?> c);  
        boolean removeAll(Collection<?> c);  
        void clear();  
        boolean equals(Object o);  
        int hashCode();  
    }

    Map接口

    Map也是一个接口,一个map不能包含重复的key,每个key只能映射唯一一个value。Map接口是用来取代Dictionary抽象类的。Map接口提供三个集合视图,1.key的集合 2.value的集合 3.key-value的集合。map内元素的顺序取决于Iterator的具体实现,获取集合视图其实是获取一个迭代器,实现对遍历元素细节的隐藏。

    同样,map的实现类应该提供两个“标准”构造器,一个无参构造器用来创建一个空map,一个只有一个参数,参数类型是map的构造器,用来创建一个新的和传入参数有一样key-value映射的map。实际上,后者允许复制任何一个map,这仅仅是一个建议,并没有强制要求,因为接口是无法包含构造器的,不过这个建议在JDK被遵守。

    如果一个方法的操作是不被支持的,这个方法指定抛出UnsupportedOperationException异常。如果这个操作对map是没有影响的,那么也可以不抛出UnsupportedOperationException异常。例如,在一个不能被修改的map调用putAll(Map)方法,如果该map的映射是空的,就不要求抛出UnsupportedOperationException异常。

    看一下部分源码:

    /**
    *返回map中key-value映射的数量
    */
    int size();
    /**
    *如果map中没有key-value映射返回true
    */
    boolean isEmpty();
    
    /**
    *如果map不含key映射,返回false,当key的类型不符合,抛出ClassCastException,当key是
    *null且该map不支持key的值是null时,抛出NullPointerException
    */
    boolean containsKey(Object key);
    
    /**
    *如果map含有一个以上的key映射的参数value,返回true,异常抛出的情况和containKey一样
    */
    boolean containsValue(Object value);
    
    /**
    *根据key得到对应的value,如果没有对应的映射,返回null,如果map允许value为null,返回
    *null可能是有一对key-null的映射或没有对应的映射
    */
    V get(Object key);
    
    /**
    *往map放入一对key-value映射
    */
    V put(K key, V value);
    
    /**
    *根据key删除对应映射
    */
    V remove(Object key);
    
    /**
    *复制一份与参数一样的map
    */
    void putAll(Map<? extends K, ? extends V> m);
    
    /**
    *清空map中所有的映射
    */
    void clear();
    
    /**
    *返回map中所有key的集合
    */
    Set<K> keySet();
    
    /**
    *返回map中所有value的集合
    */
    Collection<V> values();
    
    /**
    *返回key-value的集合
    */
    Set<Map.Entry<K, V>> entrySet();
    
    /**
    *比较调用者与参数是否相等
    */
    boolean equals(Object o);
    
    /**
    *计算map的hash code
    */
    int hashCode();
    }

    粗略的了解一下,我们在接下来的文章再好好研究

     

    参考:

    http://blog.csdn.net/u014136713/article/details/52089156

    https://www.tianmaying.com/tutorial/java_collection

    https://www.jianshu.com/p/047e33fdefd2

    https://www.cnblogs.com/13jhzeng/p/5560676.html

    https://www.jianshu.com/p/047e33fdefd2

    http://tool.oschina.net/apidocs/apidoc?api=jdk-zh

    https://blog.csdn.net/qq_37910658/article/details/73835078

    https://blog.csdn.net/ns_code/article/details/35564663

    展开全文
  • Qt中的常用容器类

    万次阅读 2017-03-26 19:47:49
    在Qt库中为我们提供了一系列的基于模板的容器类。这些类可以被用来存储特定类型的项。例如,如果你需要一个大小可以变得QString数组,那么可以使用QVector。

    在Qt库中为我们提供了一系列的基于模板的容器类。这些类可以被用来存储特定类型的项。例如,如果你需要一个大小可以变得QString数组,那么可以使用QVector<QString>。

    这些容器类都是隐式共享的,可重入的,并且在速度上进行了优化,内存占用少,内联代码扩展少,从而可以产生更小的可执行文件。此外,当他们被用作只读容器时,还是线程安全的。对于遍历这些容器来说,可以使用两种类型的迭代器:Java风格的迭代器和STL风格的迭代器。其中,Java风格的迭代器更容易使用,特别是对于Java工作人员来说,它提供了高层次的函数;然而,STL风格的迭代器会更高效,并且可以和Qt和STL的通用算法结合使用。另外,Qt还提供了一个foreach关键字,使遍历容器中的每一项更容易了。

    Qt中的容器和STL中的类似,也分为序列式容器和关联式容器。其中,序列式容器有:QList,QLinkedList,QVector,QStack,QQueue。对大部分应用程序来说,QList都是一个很好的选择。尽管它在底层被实现为一个array-list,但它为我们提供了非常快速的添加操作,包括在头部添加和在尾部添加。如果你确实需要一个linked-list,可以使用QLinkedList;如果你想确保你的元素占用连续的内存空间,可以使用QVector。而QStack和QQueue是两个提供了LIFO和FIFO语义的方便类。

    除了序列式容器,Qt中还提供了关联式容器:QMap,QMultiMap,QHash,QMultiHash,QSet。这些容器中存储的都是key-value对。其中,"Multi"容器又支持一个key可以关联多个value。"Hash"容器通过使用一个hash函数而不是二分搜索提供了更快速的查找操作。

    我们将这些容器类的总结在下表中:

    QList<T>这是最通用的一个容器类。它里面存储了给定类型T的一个列表,这个列表可以使用下标来访问。其实,在底层QList被实现为一个数组,
    确保基于下标的访问非常快速。可以使用QList::append()和QList::prepend()向链表的两端添加元素,或者使用QList::insert()在链表的中间插入元素。
    并且,和其他容器相比,更重要的是,QList在可执行文件中展开的代码量是非常少的,是经过高度优化的。QStringList就继承自QList<QString>。
    QLinkedList<T>这个容器类类似于QList,只不过它是使用迭代器来访问,而不是下标。当从中间插入时,它的效率比QList还要高。并且,它有更好的迭代器语义。
    即指向QLinkedList中某个元素的迭代器,只有该元素存在就会一直保持有效,而指向QList中某元素的迭代器,在向QList进行任意插入或删除时都会导致
    该迭代器失效。
    QVector<T>这个容器类会在一块相邻的内存中存储一个给定类型的值的数组。在一个vector的前端或中间插入是非常慢的,因为这会导致大量现存的元素移动以为新的
    元素腾出位置。
    QStack<T>这个容器类继承自QVector,提供了“先入后出”的语义。
    QQueue<T>这个容器类继承自QList,提供了“先入先出”的语义。
    QSet<T>这个容器类提供了不允许有重复值的集合,提供快速的查找效率。
    QMap<Key, T>这个容器类提供了一个字典形式的容器,它会将Key类型的值映射到T类型的value上。通常情况下,每一个key只关联一个值。并且,QMap会按Key的顺序存储
    相应的值;所以,如果不关心元素的存储顺序,QHash是一个更好的选择。
    QMaultiMap<Key, T>这个容器类继承自QMap,提供了多值的字典,也就是说,该容器中的一个key可以关联多个值。
    QHash<Key, T>这个容器类的API和QMap几乎一样,但它提供了更快速的查找操作。并且,该类会按任意的顺序存储值。
    QMultiHash<Key, T>这个容器类继承自QHash,提供了多值hash表。

    容器是可以嵌套使用的。例如,可以使用QMap<QString, QList<int>>这种类型,其key的类型是QString,值类型是QList<int>。

    上面提到的这些容器分别被定义在各自的、名称和容器名一样的头文件中。例如,<QLinkedList>。

    这些容器中存储的值可以是任何能被赋值的数据类型,即该类型必须提供一个默认的构造函数、一个拷贝构造函数、一个赋值运算符。这样的数据类型涵盖了大部分你可以存储的类型,包括基本类型入int和double,指针类型,Qt的数据类型QString,QDate,QTime,但不包括QObject或其子类(QWidget,QDialog,QTimer等等)。如果你尝试构建一个QList<QWidget>类型的变量,编译器就会提示你QWidget类的拷贝构造函数和赋值操作符是被禁用的。如果你想存储这些类的对象,可以存储它们的指针类型,例如QList<QWidget*>。

    一个可以存储在容器中的可赋值数据类型,类似于下面这个自定义类型:

      class Employee
      {
      public:
          Employee() {}
          Employee(const Employee &other);
    
          Employee &operator=(const Employee &other);
    
      private:
          QString myName;
          QDate myDateOfBirth;
      };

    如果我们不提供一个拷贝构造函数或赋值运算符,C++提供的默认实现是逐成员拷贝。在上面的例子中,这种默认构造函数也是足够的。同样,如果你没有提供构造函数,C++为我们提供的默认构造函数会使用成员变量所对应数据类型的默认值进行各个成员的初始化。所以,下面这种自定义数据类型虽然没有提供显式的构造函数或赋值运算符,它也可以被存储到容器中:

      struct Movie
      {
          int id;
          QString title;
          QDate releaseDate;
      };


    而对于其他的容器可能还有特殊的要求。例如,QMap<Key, T>的Key类型必须提供operator<()。这些特定的要求在容器类的文档中都有详细说明。一般,如果某个要求没被满足,编译器就会报错。

    Qt的容器还提供了operator<<() 和 operator>>() 以使它们可以方便的使用QDataStream类读取或写入数据。这也意味着存储在容器中的数据类型必须支持这两种操作。提供这种支持是很简单的。比如,下面的例子,是我们为上面声明的Movie结构体提供的 << 和 >>运算符:

      QDataStream &operator<<(QDataStream &out, const Movie &movie)
      {
          out << (quint32)movie.id << movie.title
              << movie.releaseDate;
          return out;
      }
    
      QDataStream &operator>>(QDataStream &in, Movie &movie)
      {
          quint32 id;
          QDate date;
    
          in >> id >> movie.title >> date;
          movie.id = (int)id;
          movie.releaseDate = date;
          return in;
      }


    大部分容器类的说明文档中都提到了“默认值”。例如,QVector会自动的使用默认构造函数的值初始化它的元素,QMap::value()方法在指定的key不存在的情况下会返回一个默认构造函数产生的值。对大部分数据类型来说,这只是意味着默认构造函数创建了一个值,例如,QString的默认构造函数会创建出一个空字符串。但是,对于int和double这类的基本类型,和指针类型,C++语言并不会指定任何初始化。在这种情况下,Qt的容器会自动的用0对它们进行初始化。

    至于对容器的操作,和stl一样,通常是使用迭代器。迭代器为访问容器中的元素提供了一个统一的方式。Qt中的容器类提供了两类迭代器:Java风格的迭代器和STL风格的迭代器。但是,当容器中的数据被修改后或由于调用了non-const成员函数导致其脱离了隐式共享,那么这两种迭代器都会失效。

    Java风格的迭代器:

    Java风格的迭代器在Qt4中被引入,成功Qt应用程序的标准组件。它们比STL风格的迭代器更好用,带代价是效率更低。这些迭代器都是特定的类,所以其具体使用方法在每个类的文档中有详细说明。另外,每一个容器类都又提供了两种类型的Java风格的迭代器:一种是只读迭代器,一种是读写迭代器。详细类型说明如下表:

    ContainersRead-only iteratorRead-write iterator
    QList<T>, QQueue<T>QListIterator<T>QMutableListIterator<T>
    QLinkedList<T>QLinkedListIterator<T>QMutableLinkedListIterator<t>
    QVector<T>, QStack<T>QVectorIterator<T>QMutableVectorIterator<T>
    QSet<T>QSetIterator<T>QMutableSetIterator<T>
    QMap<Key, T>, QMultiMap<Key, T>QMapIterator<Key, T>QMutableMapIterator<Key, T>
    QHash<Key, T>, QMultiHash<Key, T>QHashIterator<Key, T>QMutableHashIterator<Key, T>

    在下面的讨论中,我们主要集中于QList和QMap。QLinkedList,QVector,QSet的迭代器接口和QList完全一样;同样,QHash的迭代器接口和QMap一样。

    不像STL风格的迭代器,Java风格的迭代器指向两个元素之间,而不是直接指向某个具体的元素。由于这个原因,这些迭代器要么指向第一个元素前面,要么指向最后一个元素后面,要么在某两个元素之间。下面的图示显示了对于一个链表来说,有效的迭代器指向:


    下面的代码展示了,使用Java风格的迭代器遍历一个QList的典型做法:

      QList<QString> list;
      list << "A" << "B" << "C" << "D";
    
      QListIterator<QString> i(list);
      while (i.hasNext())
          qDebug() << i.next();

    该代码的执行原理是:将要遍历的QList传给QListIterator的构造函数。此时,迭代器就指向了链表中第一个元素的前面,即"A"的前面。接着,我们调用hasNext()方法来判断在当前迭代器后面是否有一个元素。如果有,我们就调用next()函数来跳过那个元素。并且,next()函数会返回它跳过的那个元素。在这个例子中就是返回一个QString字符串。

    下面的代码展示了怎么从后向前遍历一个QList:

      QListIterator<QString> i(list);
      i.toBack();
      while (i.hasPrevious())
          qDebug() << i.previous();

    该代码和向前遍历的代码类似,除了我们在一开始调用了toBack()函数将迭代器移到最后一个元素的后面。

    下面的图示说明了电影next() 和 previous()的作用:



    下表中列出了QListIterator类的API及其作用:

    toFront()移动迭代器到第一个元素之前
    toBack()移动迭代器到最后一个元素之后
    hasNext()如果迭代器还未遍历到列表的最后,返回true
    next()返回下一个元素,并将迭代器向前移动一个位置。
    peekNext()返回下一个元素,不移动迭代器。
    hasPrevious()如果迭代器还未遍历到列表的前端,返回true。
    previous()返回前一个元素,并将迭代器向后移动一个位置。
    peekPrevious()返回前一个元素,不移动迭代器。

    另外,上面我们就说过,QListIterator是只读迭代器,所以,我们无法使用该迭代器在遍历的过程中进行插入或删除操作。要使用这种功能,必须使用QMutableListIterator。下面的例子展示了使用QMutableListIterator来删除QList中所有的奇数:

      QMutableListIterator<int> i(list);
      while (i.hasNext()) {
          if (i.next() % 2 != 0)
              i.remove();
      }

    在上面的循环中,每次循环都调用了next()函数。这会跳过列表中的下一个元素。remove()函数会从链表中删除我们之前跳过的那个元素。并且,remove()函数不会使迭代器失效,我们可以安全的继续使用它。对于,从后向前遍历也是一样,如下代码所示:

      QMutableListIterator<int> i(list);
      i.toBack();
      while (i.hasPrevious()) {
          if (i.previous() % 2 != 0)
              i.remove();
      }

    如果我们只是想修改一个现存的元素,我们可以使用setValue()函数。如下面的代码,我们用128替换容器中大于128的元素:

      QMutableListIterator<int> i(list);
      while (i.hasNext()) {
          if (i.next() > 128)
              i.setValue(128);
      }
    类似于remove()函数,setValue()也是工作在我们刚跳过的元素上。如果我们是向前遍历,该元素就是当前迭代器之前的那个元素;如果我们是向后遍历,该元素就是当前迭代器之后的那个元素。

    其实,next()函数会返回一个元素的非常量引用。所以,对应简单的操作,我们不需要调用setValue()函数,而是直接进行相应修改即可。如下代码:

      QMutableListIterator<int> i(list);
      while (i.hasNext())
          i.next() *= 2;

    我们上面提到过,QLinkedList,QVector,QSet的迭代器操作和QList完全一下。那么,下面我们就来看一下QMapIterator,因为该迭代器是工作在key-value对上,所以和上面讲的有点不同。

    类似于QListIterator,QMapIterator也提供了toFront(),toBack(),hasNext(),next(),peekNext(),hasPrevious(),peekPrevious()。至于具体的key和value,我们可以调用key() 和 value() 函数,从next(),peekNext(),previous()或者peekPrevious()返回的对象中提取。

    下面的例子中,我们从map中删除所有capital以"City" 结尾的(capital,country)对:

      QMap<QString, QString> map;
      map.insert("Paris", "France");
      map.insert("Guatemala City", "Guatemala");
      map.insert("Mexico City", "Mexico");
      map.insert("Moscow", "Russia");
      ...
    
      QMutableMapIterator<QString, QString> i(map);
      while (i.hasNext()) {
          if (i.next().key().endsWith("City"))
              i.remove();
      }
    其实,QMapIterator也提供了相应的key() 和 value() 函数,可以直接作用于迭代器本身,返回上次跳过的元素的键和值。例如,下面的代码将QMap的元素拷贝到QHash:

      QMap<int, QWidget *> map;
      QHash<int, QWidget *> hash;
    
      QMapIterator<int, QWidget *> i(map);
      while (i.hasNext()) {
          i.next();
          hash.insert(i.key(), i.value());
      }
    如果你想迭代所有具有特定值的元素,可以使用findNext()或findPrevious()。在下面的例子中,我们从容器中删除具有特定值的所有项:

      QMutableMapIterator<int, QWidget *> i(map);
      while (i.findNext(widget))
          i.remove();


    STL风格的迭代器:

    STL风格的迭代器,在Qt 2 中就存在了。它们兼容于Qt和STL的通用算法,并且在访问速度上进行了优化。

    同样,每一种容器也都提供了两种类型的STL风格迭代器:只读迭代器和读写迭代器。我们应尽量使用只读迭代器,因为它们更快。

    我们同样用一张表来列举每一种STL风格的迭代器:

    ContainersRead-only iteratorRead-write iterator
    QList<T>, QQueue<T>QList<T>::const_iteratorQList<T>::iterator
    QLinkedList<T>QLinkedList<T>::const_iteratorQLinkedList<T>::iterator
    QVector<T>, QStack<T>QVector<T>::const_iteratorQVector<T>::iterator
    QSet<T>QSet<T>::const_iteratorQSet<T>::iterator
    QMap<Key, T>, QMultiMap<Key, T>QMap<Key, T>::const_iteratorQMap<Key, T>::iterator
    QHash<Key, T>, QMultiHash<Key, T>QHash<Key, T>::const_iteratorQHash<Key, T>::iterator

    STL迭代器的API在每一个类中也都有详细的说明。比如,++运算符会将迭代器前进到下一个元素,*运算符返回迭代器所指向的元素。事实上,对QVector和QStack来说,由于它们的元素都是存储在连续的内存中,所以它们的迭代器类型就是T*,它们的只读迭代器类型就是const T*。下面,我们还是以QList和QMap为例还说明stl风格的迭代器的使用方法。

    下面的例子代码,是使用STL风格的迭代器遍历QList的典型方式:

      QList<QString> list;
      list << "A" << "B" << "C" << "D";
    
      QList<QString>::iterator i;
      for (i = list.begin(); i != list.end(); ++i)
          *i = (*i).toLower();
    不同于Java风格的迭代器,STL风格的迭代器直接指向具体的元素。容器的begin() 方法返回一个指向容器中第一个元素的迭代器。end() 方法返回一个指向容器中最后一个元素的下一个位置的迭代器。end()标识了一个无效的位置,绝不应该对它解引用。它经常被用来在一个循环中做为结束条件。如果链表为空,begin()就等于end()。下面的图示说明了在一个容器中对STL风格的迭代器来说,有效的迭代器位置:



    同样,使用STL风格的迭代器做反向遍历的代码如下:

      QList<QString> list;
      list << "A" << "B" << "C" << "D";
    
      QList<QString>::reverse_iterator i;
      for (i = list.rbegin(); i != list.rend(); ++i)
          *i = i->toLower();
      }
    到目前为止,我们在代码中都是使用一元运算符*来提取某个迭代器位置的元素内容,然后调用QString;:toLower()。其实,大部分c++编译器还允许我们使用i->toLower()的形式。对于只读迭代器,可以使用const_iterator,例如:

      QList<QString>::const_iterator i;
      for (i = list.constBegin(); i != list.constEnd(); ++i)
          qDebug() << *i;
    接下来,我们也用一张表来总结一下stl风格的迭代器的相关操作:

    *i返回当前元素
    ++i步进迭代器到下一个元素位置
    i += n将迭代器向前步进n个元素
    --i步进迭代器到前一个位置
    i -= n将迭代器向前步进n个位置
    i - j返回 迭代器 i 和 j之间的元素个数

    对于++和--操作,既支持前++,也支持后++,--也一样。至于这两者的区别,我相信大家都能理解,在此就不解释了。

    对于非const迭代器类型,*运算符返回的值可以被当做左值来使用。

    对于QMap和QHash来说,*运算符返回一个元素的value部分。如果你想获得key,可以在迭代器上调用key() 方法。而处于对称性,迭代器还提供了value() 方法来获得value()值。例如,下面的代码说明了怎么打印出QMap中的所有元素:

      QMap<int, int> map;
      ...
      QMap<int, int>::const_iterator i;
      for (i = map.constBegin(); i != map.constEnd(); ++i)
          qDebug() << i.key() << ':' << i.value();
    并且,由于 “隐式共享”,一个函数返回一个容器的代价并不高。在Qt的API中,包含了很多返回QList或QStringList的函数,比如QSplitter::sizes()。如果你想使用STL风格的迭代器来迭代这些容器,你应该先拿到该容器的一份拷贝,然后遍历这份拷贝。例如:

      // RIGHT
      const QList<int> sizes = splitter->sizes();
      QList<int>::const_iterator i;
      for (i = sizes.begin(); i != sizes.end(); ++i)
          ...
    
      // WRONG
      QList<int>::const_iterator i;
      for (i = splitter->sizes().begin();
              i != splitter->sizes().end(); ++i)
          ...


    foreach 关键字

    如果你只是想顺序的变量容器中的所以元素,可以使用Qt的foreach关键字。这个关键字是Qt特定的,是使用预处理器实现的。

    它的语法是:foreach(variable, container) statement。例如,下面的代码说明了怎么使用foreach来迭代QLinkedList<QString>:

      QLinkedList<QString> list;
      ...
      QString str;
      foreach (str, list)
          qDebug() << str;
    使用foreach的代码,通常都会比使用迭代器写出的代码更短:

      QLinkedList<QString> list;
      ...
      QLinkedListIterator<QString> i(list);
      while (i.hasNext())
          qDebug() << i.next();
    如果容器中的数据类型不包括逗号,那么,我们还可以将遍历容器所用的变量定义在foreach内部。如下所示:

      QLinkedList<QString> list;
      ...
      foreach (const QString &str, list)
          qDebug() << str;
    同样,类似于c++的for循环,当有多条语句时,也可以使用花括号和break关键字:

      QLinkedList<QString> list;
      ...
      foreach (const QString &str, list) {
          if (str.isEmpty())
              break;
          qDebug() << str;
      }
    而对于QMap和QHash来说,foreach会访问其中存储的key-value对的value部分。如果你想同时获得key和value,可以使用迭代器,或者先获得其中的key,在通过key取到对应的值。如下代码所示:

      QMap<QString, int> map;
      ...
      foreach (const QString &str, map.keys())
          qDebug() << str << ':' << map.value(str);
    而对于多值关联的map来说,可以使用两个foreach,如下方式访问:

      QMultiMap<QString, int> map;
      ...
      foreach (const QString &str, map.uniqueKeys()) {
          foreach (int i, map.values(str))
              qDebug() << str << ':' << i;
      }
    在进入一个foreach循环时,Qt会自动拿到容器的一个拷贝。所以,如果你在foreach的过程中,修改了容器,并不会影响这个循环。
    而因为foreach会创建出一份容器的拷贝,所以使用一个非常量引用并不会使你能够修改原始容器。而仅仅会影响到拷贝,这可能不是你想要的结果。

    所以,相对于Qt的foreach,一个可选的方案是C++11中的基于范围的for循环。但是,要注意的是,基于范围的for循环可以会强制一个Qt容器脱离隐式共享,而foreach不会。但是,使用foreach总是会拷贝容器,这个代价对STL的容器来说,通常是昂贵的。所以,一般,我们可以对Qt容器使用foreach关键字,而对于STL的容器使用基于范围的for循环。而除了上面的foreach之外,Qt还为无限循环提供了一个伪关键字:forever。使用如下:

      forever {
          //一直执行的代码
      }
    当然,如果你担心这些Qt特定的关键字会导致名称空间的污染,也可以禁用跌这些宏。只需在.pro文件中添加如下一句即可:

    CONFIG += no_keywords


    其他的类容器类

    Qt中包含三个模板类,其在某些方面类似于容器。但这些类不提供迭代器,也不能用于foreach关键字。

    • QVarLengthArray<T, Prealloc>:该类提供了一个低级的变长数组。在某些非常看重访问速度的情况下,可以使用该类替代QVector。
    • QCache<Key, T>:该类提供了一个存储key-value对的缓存
    • QContiguousCache<T>:该类提供了一种高效的缓存数据的方式,其是使用连续的内存进行访问。
    • QPair<T1, T2>:用来存储元素对。


    算法复杂度

    算法复杂度是当容器中的元素增多时每一个函数的运行速度是多块或多慢。例如,在QLinkedList的中间插入一个元素是一个非常快速的操作,而不管当前链表中有多少元素。另一方面,在QVector的中间插入一个元素效率就是非常低下的,特别是当QVector中已经有了大量的元素,因为,这个操作会导致QVector中一半的元素都要在内存中移动一个位置。

    为了描述算法复杂度,我们使用以下几个术语,基于"big O":

    • 常量时间:O(1)。若无论容器中有多少元素,一个函数总能在相同的时间内执行完,那么这个函数就是常量时间复杂度的。例如,QLinkedList::insert()。
    • 对数时间:O(log n)。一个函数以对数时间运行,是说它的运行时间是和容器中的元素的个数成对数相关的。例如,二分查找qBinaryFind()。
    • 线性时间:O(n)。一个函数以线性时间运行,是说它的运行时间和容器中存储的元素个数成正相关。例如QVector::insert()。
    • 线性对数时间:O(nlog n)。一个函数以线性对数时间运行,是说它的运行会随着容器中元素个数的增多逐渐慢于线性时间函数,但快于二次方复杂度的函数。
    • 二次方时间:O(n2)。一个函数以二次方时间复杂度运行,是说它的运行时间和容器中元素的个数的二次方成正相关。
    下面这个表格,总结了Qt中的序列容器的算法复杂度:
     Index lookupInsertionPrependingAppending
    QLinkedList<T>O(n)O(1)O(1)O(1)
    QList<T>O(1)O(n)Amort. O(1)Amort. O(1)
    QVector<T>O(1)O(n)O(n)Amort. O(1)

    "Amort.  O(1)"意思是如果你只调用函数一次,复杂度可能是O(n) ,但是如果你多次调用函数,平均复杂度则为O(1)。

    下面的表格总结了Qt中的关联容器的算法复杂度:

    对于QVector,QHash,和QSet,追加一个元素的性能平均是O(n)。不过,我们可以在真正插入元素之前,使用将要存储的元素数目来调用QVector::reserve(),QHash::reserve()或者QSet::reserve()把这个复杂度降低到O(1)。

    生长策略

    QVector<T>,QString,和QByteArray会将它们的内容存储在连续的内存区中。QList<T>维护一个指向所存储元素的指针数组,以此提供快速的基于下标的访问(除非T是一个 指针类型或一个大小等于指针大小的基本类型,在这种情况下,元素本身会被存储在数组里面。);QHash<Key, T>保存一个hash表,其大小和元素的个数有关。同时,为了避免每次添加元素都导致内存的重新分配,这个容器类通常会分配比实际情况更多的内存。

    考虑下面的代码段,其从一个QString构建了一个QString:

      QString onlyLetters(const QString &in)
      {
          QString out;
          for (int j = 0; j < in.size(); ++j) {
              if (in[j].isLetter())
                  out += in[j];
          }
          return out;
      }
    我们动态的构建了一个QString out对象,使用一次追加一个字符的方式。我们先假定要向QString追加15000个字符。在此过程中会进行18次内存的重新分配(而不是15000次),分别是:4,8,16,20,52,116,244,500,1012,2036,4084,6132,8180,10288,12276,14324,16372。到最后,QString对象有16372个Unicode字符空间被分配,其中的15000个被占用。

    上面的这些内存数值可能很奇怪,但下面有一些指导原则:

    • QString会一次分配4个字符,直到其大小达到20。
    • 从20到4084,按每次扩大一倍的方式增长。更准确的说,它增长到下一个2的n次方,在减去12。20=2^5-12,52=2^6-12,等等。(减去12是因为有些内存分配器需要 使用一些字节为每个内存块做簿记。)
    • 从4048开始,每次增加2048个字符(4096个字节)。这是有意义的,因为现代的操作系统在重新分配一个buffer时并不会拷贝所有的数据;只是物理内存页的简单排序,只有位于第一页和最后一页的数据需要拷贝。
    QByteArray和QList使用的分配算法和QString类似。
    至于QVector,当其中存储的数据类型是可以使用memcpy()函数在内存移动时(包括C++基本类型,指针类型,Qt的共享类),也使用和QString类似的分配算法。但当其中存储的类型只有通过调用构造函数和析构函数才能在内存中移动时,会使用不同的分配算法。因为在这种情况下,内存重分配的代价很高,QVector会在内存用尽后总是增长一倍的内存,从而减少内存重分配的次数。
    QHash<Ket, T>是完全不同的情况。QHash内部的哈希表已2的次方增长,并且每次增长时,其中的元素会被重新分配到一个新的桶中,计算方式为qHash(key) % QHash::capacity()(桶的数量)。这个方式也应用于QSet和QCache。

    对大部分应用程序来说,Qt提供的默认生长算法就足够了。如果你需要更多的控制,QVector,QHash,QSet,QString和QByteArray提供了三个函数,允许你去检查和指定你需要多少内存去存储元素:
    • capacity():基于已分配的内存,返回元素的个数(对QHash和QSet来说,就是哈希表中桶的数量)
    • reserve(size):显式的预分配size个元素的内存
    • squeeze():释放为存储元素的多余内存。
    如果你知道大约将在容器中存储多少个元素,你可以在开始插入元素前调用reserve(),预分配好需要的空间;然后,在完全插入元素后,可以调用squeeze()来释放多余的内存。











    展开全文
  • 同步类容器和并发类容器

    万次阅读 多人点赞 2019-07-31 19:22:20
    注意Collection和Map是顶层接口,而List、Set、Queue接口则分别继承了Collection接口,分别代表数组、集合和队列这三大类容器。 像ArrayList、LinkedList都是实现了List接口,HashSet实现了Set接口,而Deque(双向...
  • Java容器哪些哪些是同步容器,哪些是并发容器?一、基本概念新的改变功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格...
  • Java常见的容器类及其区别

    万次阅读 2018-06-29 12:07:49
     Set容器类主要有HashSet和TreeSet等。  共同点:  元素不重复  实现了Java.util.Set接口。    1)HashSet类    -> 不保证集合中元素的顺序   ->允许包含值为null的元素,但最多只能有一个...
  • STL 定义的具体容器类

    2016-10-28 16:00:46
    STL 定义的三类容器所包含的具体容器类。解析容器间的差别,每个类型的优缺点。对容器的理解和使用,有一定的好处
  • C++ 中的容器类详解

    万次阅读 多人点赞 2018-08-23 12:00:12
    C++中的容器类包括“顺序存储结构”和“关联存储结构”,前者包括vector,list,deque等;后者包括set,map,multiset,multimap等。若需要存储的元素数在编译器间就可以确定,可以使用数组来存储,否则,就需要用到...
  • 关于容器类的总结

    千次阅读 2017-09-19 00:23:17
    关于容器类的总结C++中的容器类包括“顺序存储结构”和“关联存储结构”,前者包括vector,list,deque等;后者包括set,map,multiset,multimap等。若需要存储的元素数在编译器间就可以确定,可以使用数组来存储,...
  • C++中的容器类详解

    万次阅读 多人点赞 2015-12-18 15:05:55
    C++中的容器类包括“顺序存储结构”和“关联存储结构”,前者包括vector,list,deque等;后者包括set,map,multiset,multimap等。若需要存储的元素数在编译器间就可以确定,可以使用数组来存储,否则,就需要用到...
  • Java容器可以说是增强程序员编程能力的基本工具,本系列将带您深入理解容器类。 容器的用途 如果对象的数量与生命周期都是固定的,自然我们也就不需要很复杂的数据结构。 我们可以通过创建引用来持有对象,如 ...
  • 自定义spring容器类使用的jar包,包括dom4j,spring等
  • C++常见容器类使用详解

    千次阅读 2018-04-13 21:11:47
    C++中有两种类型的容器:顺序容器和关联容器。 顺序容器主要有vector、list、deque。其中vector表示一段连续的内存,基于数组实现;list表示非连续的内存,基于链表实现;deque与vector类似,但是对首元素提供插入...
  • Qt容器类详解

    千次阅读 2016-12-25 22:08:47
    QT不仅支持C++的STL模板库,同时自己也定义了一套容器类和与之操作的算法类,使用QT定义的这一套库,可以使在各个平台的表现相同。QT的这些容器被设计为更轻便,更安全和更容易使用。容器类是隐含共享(implicitly)的...
  • c++容器类

    万次阅读 多人点赞 2012-12-21 09:43:14
    很简单,容器就是保存其它对象的对象,当然这是一个朴素的理解,这种“对象”还包含了一系列处理“其它对象”的方法,因为这些方法在程序的设计上会经常被用到,所以容器也体现了一个好处,就是“容器类是一种对特定...
  • 同步容器与并发容器类简介

    千次阅读 2018-09-02 11:03:56
      同步容器类包括Vector和HashTable,二者都是早期JDK的一部分,此外还包括在JDK1.2当中添加的一些功能相似的类,这些同步的封装类是由Collections.synchronizedXxx等工厂方法创建的。这些类实现线程安全的方式是...
  • c++容器类&QT;容器

    2012-10-23 17:00:22
    C++中的容器类包括“顺序存储结构”和“关联存储结构”,前者包括vector,list,deque等;后者包括set,map,multiset,multimap等。 常用函数介绍等. 若需要存储的元素数在编译器间就可以确定,可以使用数组来...
  • STL中容器的介绍及分类

    千次阅读 2020-09-14 09:52:26
      C++ STL (Standard Template Library标准模板库) 是通用模板和算法的集合,它提供给程序员一些标准的数据结构的实现,称为容器,如 queues(队列)、lists(链表)、和 stacks(栈)等。 一、容器介绍   STL容器是...
  • java容器都有哪些?

    万次阅读 2019-09-03 20:50:29
    java容器类类库的用途是"保存对象"。摘自: “Thinking in Java”. Java集合类是一种特别有用的工具类,可以用于存储数量不等的对象,并可以实现常用的数据结构,如栈,队列等.Java集合就像一种容器,可以把多个对象(实际...
  • QT容器类

    万次阅读 2013-01-17 18:53:32
    QT不仅支持C++的STL模板库,同时自己也定义了一套容器类和与之操作的算法类,使用QT定义的这一套库,可以使在各个平台的表现相同。QT的这些容器被设计为更轻便,更安全和更容易使用。容器类是隐含共享(implicitly)的...
  • C++容器类和Qt容器类的对比

    千次阅读 2015-06-05 15:16:55
    C++中容器类是属于标准模板库中的内容,有必要回顾下标准模板库。STL = Standard Template Library,标准模板库,惠普实验室开发的一系列软件的统称。从根本上说,STL是一些“容器”的集合,这些“容器”有list,...
  • Qt容器类整理

    千次阅读 2015-08-03 17:17:45
    Qt既提供了诸如QVector、QLinkedList和QList等的连续容器,也提供了诸如QMap和QHash等的关联容器。连续容器存储连续值,关联容器存储键值对。 Qt还提供了在任意容器上执行相关操作的通用算法。例如,qSort()算法对一...
  • java容器类

    万次阅读 2009-02-25 16:35:00
    Java容器类Collection、List、ArrayList、Vector及map、HashTable、HashMap区别 Collection是List和Set两个接口的基接口 List在Collection之上增加了"有序" Set在Collection之上增加了"唯一" 而ArrayList是实现List...
  • 标准C++中的STL容器类简介

    千次阅读 2015-09-02 10:54:45
    容器的概念 所谓STL容器,即是将最常运用的一些数据结构(data structures...根据数据在容器中排列的特性,容器可概分为序列式(sequence)和关联式(associative)两种。 迭代器是一种检查容器内元素并遍历元
  • 里我们不涉及容器的基本操作之,只是要讨论一下各个容器其各自的特点。STL中的常用容器包括:顺序性容器(vector、deque、list)、关联容器(map、set)、容器适配器(queue、stac)

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 593,631
精华内容 237,452
关键字:

容器类包括哪些