wake-up-neo.com

Wie entferne ich constness von const_iterator?

Als Erweiterung zu dieser Frage Sind const_iterators schneller? , ich habe noch eine Frage zu const_iterators. So entfernen Sie die Konstanz eines const_iterator? Obwohl Iteratoren eine verallgemeinerte Form von Zeigern sind, sind const_iterator und iterator zwei verschiedene Dinge. Daher kann ich meines Erachtens auch nicht const_cast<> verwenden, um von const_iterator zu iterators zu wechseln.

Ein Ansatz könnte sein, dass Sie einen Iterator definieren, der sich bis zu dem Element bewegt, auf das const_iterator zeigt. Dies scheint jedoch ein linearer Zeitalgorithmus zu sein.

Irgendeine Idee, wie dies am besten erreicht werden kann?

40
aJ.

In C++ 11 gibt es eine Lösung mit konstanter zeitlicher Komplexität: Für jeden Sequenz-, assoziativen oder ungeordneten assoziativen Container (einschließlich aller Standardbibliothekscontainer) können Sie die Range-Erase-Member-Funktion mit einem leeren Bereich aufrufen:

template <typename Container, typename ConstIterator>
typename Container::iterator remove_constness(Container& c, ConstIterator it)
{
    return c.erase(it, it);
}

Die Memberfunktionen zum Löschen des Bereichs verfügen über ein Paar von const_iterator-Parametern, geben jedoch eine iterator zurück. Da ein leerer Bereich angegeben ist, ändert der Aufruf zum Löschen nicht den Inhalt des Containers.

Hat Tipp an Howard Hinnant und Jon Kalb für diesen Trick.

64
James McNellis

Leider ist die lineare Zeit der einzige Weg, dies zu tun:

iter i(d.begin());
advance (i,distance<ConstIter>(i,ci));

wobei iter und constIter geeignete typedefs sind und d der Container ist, über den Sie iterieren.

14
PaulJWilliams

In den Antworten auf Ihren vorherigen Beitrag haben einige Personen, einschließlich mir, empfohlen, stattdessen const_iterators zu verwenden, um die Leistung zu beeinträchtigen. Lesbarkeit, Rückverfolgbarkeit vom Design Board bis zum Code ... Die Verwendung von const_iterators, um mutierenden Zugriff auf ein Nicht-const-Element zu ermöglichen, ist viel schlimmer als die Verwendung von const_iterators überhaupt. Sie wandeln Ihren Code in etwas um, das nur Sie verstehen werden, mit einem schlechteren Design und einem echten Problem mit der Wartbarkeit. Es ist viel schlimmer, const nur zu benutzen, um es wegzuwerfen, als const überhaupt nicht zu benutzen.

Wenn Sie sicher sind, dass Sie es wollen, ist der gute/schlechte Teil von C++, dass Sie immer genug Seil bekommen können, um sich aufzuhängen. Wenn Sie const_iterator für Leistungsprobleme verwenden möchten, sollten Sie dies wirklich überdenken, aber wenn Sie trotzdem den Fuß abschießen möchten, kann C++ die Waffe Ihrer Wahl sein.

Erstens das Einfachste: Wenn Ihre Operationen die Argumente als const annehmen (auch wenn Sie const_cast intern anwenden), sollte es meiner Meinung nach in den meisten Implementierungen direkt funktionieren (auch wenn es sich wahrscheinlich um undefiniertes Verhalten handelt).

Wenn Sie die Funktoren nicht ändern können, können Sie das Problem von beiden Seiten lösen: Stellen Sie einen nicht konstanten Iterator-Wrapper um die konstanten Iteratoren oder einen konstanten Funktor-Wrapper um die nicht konstanten Funktoren bereit.

Iteratorfassade, der lange Weg:

template <typename T>
struct remove_const
{
    typedef T type;
};
template <typename T>
struct remove_const<const T>
{
    typedef T type;
};

template <typename T>
class unconst_iterator_type
{
    public:
        typedef std::forward_iterator_tag iterator_category;
        typedef typename remove_const<
                typename std::iterator_traits<T>::value_type
            >::type value_type;
        typedef value_type* pointer;
        typedef value_type& reference;

        unconst_iterator_type( T it )
            : it_( it ) {} // allow implicit conversions
        unconst_iterator_type& operator++() {
            ++it_;
            return *this;
        }
        value_type& operator*() {
            return const_cast<value_type&>( *it_ );
        }
        pointer operator->() {
            return const_cast<pointer>( &(*it_) );
        }
        friend bool operator==( unconst_iterator_type<T> const & lhs,
                unconst_iterator_type<T> const & rhs )
        {
            return lhs.it_ == rhs.it_;
        }
        friend bool operator!=( unconst_iterator_type<T> const & lhs,
                unconst_iterator_type<T> const & rhs )
        {
            return !( lhs == rhs );
        }
    private:
        T it_;  // internal (const) iterator
};

Dies ist möglicherweise nicht die gewünschte Antwort, sondern eine verwandte.

Ich gehe davon aus, dass Sie die Stelle ändern möchten, auf die der Iterator zeigt. Am einfachsten ist es, wenn const_cast stattdessen die zurückgegebene Referenz sendet.

Etwas wie das

const_cast<T&>(*it);

3
leiz

Scott Meyers Artikel über den Vorzug von Iteratoren gegenüber const_iterators beantwortet dies. Die Antwort von Visage ist die einzige sichere Alternative vor C++ 11, entspricht jedoch der konstanten Zeit für gut implementierte Direktzugriffsiteratoren und der linearen Zeit für andere.

3
Pontus Gagge

Ich glaube, diese Konvertierung wird in einem gut gestalteten Programm nicht benötigt.

Versuchen Sie in diesem Fall, den Code neu zu gestalten.

Als Workaround können Sie Folgendes tun:

typedef std::vector< size_t > container_type;
container_type v;
// filling container code 
container_type::const_iterator ci = v.begin() + 3; // set some value 
container_type::iterator i = v.begin();
std::advance( i, std::distance< container_type::const_iterator >( v.begin(), ci ) );

Aber ich denke, dass diese Konvertierung manchmal unmöglich ist, weil Ihre Algorithmen keinen Zugriff auf Container haben.

2
bayda

Sie können den Iterator begin () vom Iterator const_iterator subtrahieren, um die Position zu ermitteln, auf die der Iterator const_iterator zeigt, und dann begin () zurück zu der Position hinzufügen, um einen Iterator ohne const zu erhalten. Ich denke nicht, dass dies für nichtlineare Container sehr effizient sein wird, aber für lineare wie z. B. Vektor wird dies eine konstante Zeit in Anspruch nehmen.

vector<int> v;                                                                                                         
v.Push_back(0);
v.Push_back(1);
v.Push_back(2);
v.Push_back(3);
vector<int>::const_iterator ci = v.begin() + 2;
cout << *ci << endl;
vector<int>::iterator it = v.begin() + (ci - v.begin());
cout << *it << endl;
*it = 20;
cout << *ci << endl;

EDIT: Dies scheint nur für lineare Container (mit wahlfreiem Zugriff) zu funktionieren.

1
marcog

sie können Ihren Konstanten-Iterator-Wertzeiger in einen Nicht-Konstanten-Wertzeiger umwandeln und ihn direkt so verwenden

    vector<int> v;                                                                                                         
v.Push_back(0);
v.Push_back(1);
v.Push_back(2);
v.Push_back(2);
vector<int>::const_iterator ci = v.begin() + 2;
cout << *ci << endl;
*const_cast<int*>(&(*ci)) = 7;
cout << *ci << endl;
0
Ankit

Ich dachte, es würde Spaß machen, eine Lösung dafür zu finden, die für Container funktioniert, die nicht in der Standardbibliothek enthalten sind und die erase () -Methode nicht enthalten.

Der Versuch, dies zu verwenden, führt dazu, dass Visual Studio 2013 beim Kompilieren hängen bleibt. Ich schließe den Testfall nicht ein, da es eine gute Idee ist, ihn Lesern zu überlassen, die die Benutzeroberfläche schnell herausfinden können. Ich weiß nicht, warum dies beim Kompilieren hängt. Dies tritt auch dann auf, wenn const_iterator gleich begin () ist.

// deconst.h

#ifndef _miscTools_deconst
#define _miscTools_deconst

#ifdef _WIN32 
    #include <Windows.h>
#endif

namespace miscTools
{
    template < typename T >
    struct deconst
    {

        static inline typename T::iterator iterator ( typename T::const_iterator*&& target, T*&& subject )
        {
            typename T::iterator && resultant = subject->begin ( );

            bool goodItty = process < 0, T >::step ( std::move ( target ), std::move ( &resultant ), std::move ( subject ) );

        #ifdef _WIN32
             // This is just my habit with test code, and would normally be replaced by an assert
             if ( goodItty == false ) 
             {
                  OutputDebugString ( "     ERROR: deconst::iterator call. Target iterator is not within the bounds of the subject container.\n" ) 
             }
        #endif
            return std::move ( resultant );
        }

    private:

        template < std::size_t i, typename T >
        struct process
        {
            static inline bool step ( typename T::const_iterator*&& target, typename T::iterator*&& variant, T*&& subject )
            {
                if ( ( static_cast <typename T::const_iterator> ( subject->begin () + i ) ) == *target )
                {
                    ( *variant ) += i;
                    return true;
                }
                else
                {
                    if ( ( *variant + i ) < subject->end () )
                    {
                        process < ( i + 1 ), T >::step ( std::move ( target ), std::move ( variant ), std::move ( subject ) );
                    }
                    else { return false; }
                }
            }
        };
    };
}

#endif
0
user2813810