栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

(重新)在非标准容器中使用std :: algorithms

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

(重新)在非标准容器中使用std :: algorithms

我认为类似这样的东西可能符合标准。它使用一些C 11功能来简化语法,但也可以更改为符合C 03 AFAIK。

经过测试并与clang ++ 3.2配合使用

序幕:

#include <vector>#include <string>#include <utility>  // for std::swap#include <iterator>using std::vector;using std::string;// didn't want to insert all those types as nested classes of MyColumnTypenamespace MyColumnType_iterator{    struct all_copy;    struct all_reference;    struct all_iterator;}// just provided `begin` and `end` member functionsstruct MyColumnType {    // data: Each row represents a member of an object.    vector<double> a;   // All vectors are guaranteed to have always    vector<string> b;   // the same length.    vector<int> c;    void copy(int from_pos, int to_pos); // The column type provides an itface    void swap(int pos_a, int pos_b);     // for copying, swapping, ...    void push_back();      // And for resizing the container.    void pop_back();    void insert(int pos);    void remove(int pos);    // The interface can be extended/modified if required    using iterator = MyColumnType_iterator::all_iterator;    iterator begin();    iterator end();};

迭代器类:a

value_type
all_copy
),
reference
类型(
all_reference
)和迭代器类型(
all_iterator
)。迭代是通过保留和更新三个迭代器(每个迭代器一个
vector
)来完成的。不过,我不知道这是否是性能最高的选项。

工作原理:

std::iterator_traits
为迭代器定义几种关联的类型:[iterator.traits] / 1

iterator_traits<Iterator>::difference_type

iterator_traits<Iterator>::value_type

iterator_traits<Iterator>::iterator_category

分别定义为迭代器的差异类型,值类型和迭代器类别。另外,类型
iterator_traits<Iterator>::reference

iterator_traits<Iterator>::pointer

应定义为迭代器的引用和指针类型,即对于迭代器对象a,其类型分别与
*a
和的类型相同。
a->

因此,您可以引入一个struct(

all_reference
),将三个引用作为
reference
类型。此类型是的返回值
*a
,其中
a
是迭代器类型(可能是
const
-qualified)。这需要有所不同,
value_type
因为某些标准库算法(例如)
sort
可能想要创建一个临时变量
*a
(通过复制或移入局部变量)来存储其值的局部变量。在这种情况下,
all_copy
提供此功能。

您不需要

all_copy
在自己的循环中使用它(),因为它可能会影响性能。

namespace MyColumnType_iterator{    struct all_copy;    struct all_reference    {        double& a;        string& b;        int& c;        all_reference() = delete;        // not required for std::sort, but stream output is simpler to write        // with this        all_reference(all_reference const&) = default;        all_reference(double& pa, string& pb, int& pc) : a{pa} , b{pb} , c{pc}        {}        // MoveConstructible required for std::sort        all_reference(all_reference&& other) = default;        // MoveAssignable required for std::sort        all_reference& operator= (all_reference&& other)        { a = std::move(other.a); b = std::move(other.b); c = std::move(other.c); return *this;        }        // swappable required for std::sort        friend void swap(all_reference p0, all_reference p1)        { std::swap(p0.a, p1.a); std::swap(p0.b, p1.b); std::swap(p0.c, p1.c);        }        all_reference& operator= (all_copy const& p) = default;        all_reference& operator= (all_copy&& p) = default;        // strict total ordering required for std::sort        friend bool operator< (all_reference const& lhs,         all_reference const& rhs);        friend bool operator< (all_reference const& lhs, all_copy const& rhs);        friend bool operator< (all_copy const& lhs, all_reference const& rhs);    };    struct all_copy    {        double a;        string b;        int c;        all_copy(all_reference const& p) : a{p.a} , b{p.b} , c{p.c}        {}        all_copy(all_reference&& p) : a{ std::move(p.a) } , b{ std::move(p.b) } , c{ std::move(p.c) }        {}    };

必须具有的比较功能

std::sort
。由于某些原因,我们必须提供所有这三个。

    bool operator< (all_reference const& lhs, all_reference const& rhs)    {        return lhs.c < rhs.c;    }    bool operator< (all_reference const& lhs, all_copy const& rhs)    {        return lhs.c < rhs.c;    }    bool operator< (all_copy const& lhs, all_reference const& rhs)    {        return lhs.c < rhs.c;    }

现在,迭代器类:

    struct all_iterator        : public std::iterator < std::random_access_iterator_tag, all_copy >    {        //+ specific to implementation        private: using ItA = std::vector<double>::iterator; using ItB = std::vector<std::string>::iterator; using ItC = std::vector<int>::iterator; ItA iA; ItB iB; ItC iC;        public: all_iterator(ItA a, ItB b, ItC c)     : iA(a)     , iB(b)     , iC(c) {}        //- specific to implementation        //+ for iterator_traits using reference = all_reference; using pointer = all_reference;        //- for iterator_traits        //+ iterator requirement [iterator.iterators]/1 all_iterator(all_iterator const&) = default; // CopyConstructible all_iterator& operator=(all_iterator const&) = default; // CopyAssignable ~all_iterator() = default;        // Destructible void swap(all_iterator& other)    // lvalues are swappable {     std::swap(iA, other.iA);     std::swap(iB, other.iB);     std::swap(iC, other.iC); }        //- iterator requirements [iterator.iterators]/1        //+ iterator requirement [iterator.iterators]/2 all_reference operator*() {     return {*iA, *iB, *iC}; } all_iterator& operator++() {     ++iA;     ++iB;     ++iC;     return *this; }        //- iterator requirement [iterator.iterators]/2        //+ input iterator requirements [input.iterators]/1 bool operator==(all_iterator const& other) const        // EqualityComparable {     return iA == other.iA;  // should be sufficient (?) }        //- input iterator requirements [input.iterators]/1        //+ input iterator requirements [input.iterators]/2 bool operator!=(all_iterator const& other) const        // "UnEqualityComparable" {     return iA != other.iA;  // should be sufficient (?) } all_reference const operator*() const        // *a {     return {*iA, *iB, *iC}; } all_reference operator->()        // a->m {     return {*iA, *iB, *iC}; } all_reference const operator->() const       // a->m {     return {*iA, *iB, *iC}; } // ++r already satisfied all_iterator operator++(int)      // *++r {     all_iterator temp(*this);     ++(*this);     return temp; }        //- input iterator requirements [input.iterators]/2        //+ output iterator requirements [output.iterators]/1 // *r = o already satisfied // ++r already satisfied // r++ already satisfied // *r++ = o already satisfied        //- output iterator requirements [output.iterators]/1        //+ forward iterator requirements [forward.iterators]/1 all_iterator() = default;         // DefaultConstructible // r++ already satisfied // *r++ already satisfied // multi-pass must be guaranteed        //- forward iterator requirements [forward.iterators]/1        //+ bidirectional iterator requirements [bidirectional.iterators]/1 all_iterator& operator--()        // --r {     --iA;     --iB;     --iC;     return *this; } all_iterator operator--(int)      // r-- {     all_iterator temp(*this);     --(*this);     return temp; } // *r-- already satisfied        //- bidirectional iterator requirements [bidirectional.iterators]/1        //+ random access iterator requirements [random.access.iterators]/1 all_iterator& operator+=(difference_type p)  // r += n {     iA += p;     iB += p;     iC += p;     return *this; } all_iterator operator+(difference_type p) const         // a + n {     all_iterator temp(*this);     temp += p;     return temp; } // doesn't have to be a friend function, but this way, // we can define it here friend all_iterator operator+(difference_type p,        all_iterator temp)         // n + a {     temp += p;     return temp; } all_iterator& operator-=(difference_type p)  // r -= n {     iA -= p;     iB -= p;     iC -= p;     return *this; } all_iterator operator-(difference_type p) const         // a - n {     all_iterator temp(*this);     temp -= p;     return temp; } difference_type operator-(all_iterator const& p)        // b - a {     return iA - p.iA;   // should be sufficient (?) } all_reference operator[](difference_type p)  // a[n] {     return *(*this + p); } all_reference const operator[](difference_type p) const // a[n] {     return *(*this + p); } bool operator<(all_iterator const& p) const  // a < b {     return iA < p.iA;   // should be sufficient (?) } bool operator>(all_iterator const& p) const  // a > b {     return iA > p.iA;   // should be sufficient (?) } bool operator>=(all_iterator const& p) const // a >= b {     return iA >= p.iA;  // should be sufficient (?) } bool operator<=(all_iterator const& p) const // a >= b {     return iA <= p.iA;  // should be sufficient (?) }        //- random access iterator requirements [random.access.iterators]/1    };}//- namespace MyColumnType_iteratorMyColumnType::iterator MyColumnType::begin(){    return { a.begin(), b.begin(), c.begin() };}MyColumnType::iterator MyColumnType::end(){    return { a.end(), b.end(), c.end() };}

用法示例:

#include <iostream>#include <cstddef>#include <algorithm>namespace MyColumnType_iterator{    template < typename char_type, typename char_traits >    std::basic_ostream < char_type, char_traits >&    operator<< (std::basic_ostream < char_type, char_traits >& o,     std::iterator_traits<MyColumnType::iterator>::reference p)    {        return o << p.a << ";" << p.b << ";" << p.c;    }}int main(){    using std::cout;    MyColumnType mct =    {          {1.0, 0.9, 0.8, 0.7, 0.6, 0.5, 0.4, 0.3, 0.2, 0.1}        , {"j", "i", "h", "g", "f", "e", "d", "c", "b", "a"}        , {10,    9,   8,   7,   6,   5,   4,   3,   2,   1}    };    using ref = std::iterator_traits<MyColumnType::iterator>::reference;    std::copy(mct.begin(), mct.end(), std::ostream_iterator<ref>(cout, ", "));    std::cout << std::endl;    std::sort(mct.begin(), mct.end());    std::copy(mct.begin(), mct.end(), std::ostream_iterator<ref>(cout, ", "));    std::cout << std::endl;}

输出:

1; j; 10,0.9; i; 9,0.8; h; 8,0.7; g; 7,0.6; f; 6,0.5; e; 5,0.4; d; 4,0.3; c;
3,0.2; b; 2,0.1; a;
1,0.1; a; 1,0.2; b; 2,0.3; c; 3,0.4; d; 4,0.5; e; 5,0.6; f; 6,0.7; g;
7,0.8; h; 8,0.9; i; 9,1; j; 10,



转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/413737.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号