Kritik für URL Encoder erbeten



  • Danke. Das hatte mich auch schon gewundert, dass das schnell sein soll. Ist es den Wirklich so, dass das anhängen an einen String besonder schnell ist? Muss da nicht sehr viel Speicher neu angefordert und kopiert werden?



  • Nein, std::string reserviert normalerweise exponentiell Speicher, heißt wenn du an einen String mit 64 Elementen eins dran hängst, und kein Platz mehr frei ist, reserviert er z.B. gleich 128 byte. Siehe auch .capacity() Kopiert werden muss natürlich. 😉



  • cooky451 schrieb:

    Nein, std::string reserviert normalerweise exponentiell Speicher, heißt wenn du an einen String mit 64 Elementen eins dran hängst, und kein Platz mehr frei ist, reserviert er z.B. gleich 128 byte. Siehe auch .capacity() Kopiert werden muss natürlich. 😉

    Ich kenne das jetzt nur von std::vector. Die String Implementation von libcxx scheint das auch nicht zu machen wenn ich das richtig sehe: http://llvm.org/svn/llvm-project/libcxx/trunk/include/string



  • TNA schrieb:

    Die String Implementation von libcxx scheint das auch nicht zu machen wenn ich das richtig sehe: http://llvm.org/svn/llvm-project/libcxx/trunk/include/string

    Wo siehst du das? Ich sehe was anderes

    // in: basic_string<_CharT, _Traits, _Allocator>::push_back(value_type __c)
    
        if (__sz == __cap)
        {
            __grow_by(__cap, 1, __sz, __sz, 0);
            __is_short = !__is_long();
        }
    

    Heisst: "Wenn neue size()==capacity(), mach capacity() += capacity()".

    stringstream macht das genau gleich, nur hat der einen enormen Overhead pro operator<<.



  • encoder schrieb:

    Wo siehst du das? Ich sehe was anderes

    Ups, ich hatte nicht berücksichtigt, dass du einen char anhängst und keinen String. Wäre es aber nicht trotzdem sinnvoll, ein

    escaped.reserve(value.size());
    

    zu machen?



  • Sorry, hab mich verguckt, es wird nur um 1 vergrössert. Scheint so, als wäre std::string da noch refcounted, also gar nicht mehr C++11-konform.

    Dann nimm solange halt vector<char>.



  • Soweit ich weiß wurde libcxx extra für c++11 designed und der string ist nicht refcounted. Mir ist allerdings noch die Idee gekommen, einfach am Anfang genug Speicher mit reserve() zu reservieren und nachher ein shrink_to_fit() zu machen. Würde da etwas gegen sprechen?



  • @encoder:

    static std::array<bool, 256> unreserved;
    
      if( !unreserved['A'] )
        for (unsigned char c : "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_.~") 
          unreserved[c] = true;
    

    ?

    infach am Anfang genug Speicher mit reserve() zu reservieren und nachher ein shrink_to_fit() zu machen. Würde da etwas gegen sprechen?

    Nein, genau so sind diese Funktionen gedacht, damit würde das hin- und her kopieren eliminiert.



  • std::string url_encode(const std::string &value) { 
      static std::array<bool, 256> unreserved = []{ 
        std::array<bool, 256> a{{}}; 
        for (unsigned char c : "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_.~") 
          a[c] = true; 
        return a; 
      }(); 
      std::string escaped;
      escaped.reserve(value.size()*3);
      for (unsigned char c : value) { 
        if (unreserved[c]) 
          escaped += c; 
        else { 
          escaped += '%'; 
          escaped += "0123456789ABCDEF"[(c/0xF)&0xF]; 
          escaped += "0123456789ABCDEF"[(c&0xF)]; 
        } 
      }
      escaped.shrink_to_fit();
      return escaped; 
    }
    


  • #include <string>
    #include <array>
    #include <bitset>
    #include <cassert>
    
    std::string url_encode(const std::string &value) {
      static std::array<bool, 256> unreserved = []{
        std::array<bool, 256> a{{}};
        for (unsigned char c : "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_.~")
          a[c] = true;
        return a;
      }();
      std::string escaped;
      escaped.reserve(value.size()*3);
      for (unsigned char c : value) {
        if (unreserved[c])
          escaped += c;
        else {
          escaped += '%';
          escaped += "0123456789ABCDEF"[(c/16)&0xF]; //hier stand 15 statt 16
          escaped += "0123456789ABCDEF"[(c&0xF)];
        }
      }
      escaped.shrink_to_fit();
      return escaped;
    }
    
    namespace generalized
    {
    	bool needs_escape(char c)
    	{
    		static std::bitset<256> const flags = []()
    		{
    			std::bitset<256> result;
    			for (unsigned char c : "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_.~")
    			{
    				result.set(c);
    			}
    			return result;
    		}();
    		return ! flags.test(static_cast<unsigned char>(c));
    	}
    
    	template <class OutputIterator>
    	OutputIterator escape(char c, OutputIterator dest)
    	{
    		*dest++ = '%';
    		unsigned const uc = static_cast<unsigned char>(c);
    		char const * const digits = "0123456789ABCDEF";
    		*dest++ = digits[uc / 16];
    		*dest++ = digits[uc & 15];
    		return dest;
    	}
    
    	template <class InputIterator, class OutputIterator>
    	OutputIterator
    	url_encode(InputIterator source_begin,
    			   InputIterator source_end,
    			   OutputIterator dest)
    	{
    		for (; source_begin != source_end; ++source_begin)
    		{
    			char const c = *source_begin;
    			if (needs_escape(c))
    			{
    				dest = escape(c, dest);
    			}
    			else
    			{
    				*dest++ = c;
    			}
    		}
    		return dest;
    	}
    
    	template <class InputIterator>
    	std::size_t size_when_encoded(InputIterator begin, InputIterator end)
    	{
    		std::size_t size = 0;
    		for (; begin != end; ++begin)
    		{
    			if (needs_escape(*begin))
    			{
    				size += 3;
    			}
    			else
    			{
    				size += 1;
    			}
    		}
    		return size;
    	}
    
    	///Fordert zuerst die mindestens benötigte Menge Speicher an und vergrößert
    	///dann bei Bedarf mit string::push_back. Die Kapazität des Ergebnisses ist
    	///möglicherweise höher als die Länge.
    	std::string url_encode_to_string(std::string const &value)
    	{
    		std::string encoded;
    		encoded.reserve(value.size());
    		url_encode(begin(value), end(value), std::back_inserter(encoded));
    		return encoded;
    	}
    
    	///Berechnet die Länge des Ergebnisses und fordert genau so viel Speicher an.
    	///Es gibt maximal eine dynamische Speicheranforderung.
    	///Die Kapazität des Ergebnisses entspricht in der Regel der Länge.
    	std::string url_encode_to_string_fit(std::string const &value)
    	{
    		std::string encoded;
    		encoded.resize(size_when_encoded(begin(value), end(value)));
    		url_encode(begin(value), end(value), begin(encoded));
    		return encoded;
    	}
    }
    
    template <class UrlEncode>
    void test_url_encode(UrlEncode const &encode)
    {
    	assert(encode("") == "");
    	assert(encode("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_.~") ==
    	              "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_.~");
    	assert(encode(" \xff") == "%20%FF");
    }
    
    int main()
    {
    	test_url_encode(url_encode);
    	test_url_encode(generalized::url_encode_to_string);
    	test_url_encode(generalized::url_encode_to_string_fit);
    }
    


  • encoder schrieb:

    Sorry, hab mich verguckt, es wird nur um 1 vergrössert.

    Ich glaube du hast dich doppelt verguckt, so dass die ursprüngliche Aussage wieder stimmt:

    template <class _CharT, class _Traits, class _Allocator>
    void
    basic_string<_CharT, _Traits, _Allocator>::__grow_by(size_type __old_cap, size_type __delta_cap, size_type __old_sz,
                                                         size_type __n_copy,  size_type __n_del,     size_type __n_add)
    {
        size_type __ms = max_size();
        if (__delta_cap > __ms - __old_cap - 1)
            this->__throw_length_error();
        pointer __old_p = __get_pointer();
        size_type __cap = __old_cap < __ms / 2 - __alignment ?             // vvvvvvvvvvvvv -- HIER
                              __recommend(_VSTD::max(__old_cap + __delta_cap, 2 * __old_cap)) :
                              __ms - 1;
        pointer __p = __alloc_traits::allocate(__alloc(), __cap+1);
        __invalidate_all_iterators();
        if (__n_copy != 0)
            traits_type::copy(_VSTD::__to_raw_pointer(__p),
                              _VSTD::__to_raw_pointer(__old_p), __n_copy);
        size_type __sec_cp_sz = __old_sz - __n_del - __n_copy;
        if (__sec_cp_sz != 0)
            traits_type::copy(_VSTD::__to_raw_pointer(__p) + __n_copy + __n_add,
                              _VSTD::__to_raw_pointer(__old_p) + __n_copy + __n_del,
                              __sec_cp_sz);
        if (__old_cap+1 != __min_cap)
            __alloc_traits::deallocate(__alloc(), __old_p, __old_cap+1);
        __set_long_pointer(__p);
        __set_long_cap(__cap+1);
    }
    

    Heisst: wenn __old_cap noch verdoppelt werden kann, dann wird immer mindestens verdoppelt. Und nur falls __delta_cap > __old_cap spielt __delta_cap eine Rolle -- in dem Fall wird dann mehr als verdoppelt.

    => Fragwürdiger name. __min_grow_amount wäre mMn. ein besserer Name. Hätte zumindest bei mir gleich den Verdacht geweckt dass vermutlich oft mehr "gegrowd" wird als man da übergibt.

    encoder schrieb:

    Scheint so, als wäre std::string da noch refcounted, also gar nicht mehr C++11-konform.

    Wo scheint das so 😕
    Ich seh' da nur ne Small-String-Optimization.



  • Ich habe noch eine Frage zum Ausdruck

    (c/0xF)&0xF
    

    c/0xF ist doch ein "trickreicher" Rechtsshift oder? Warum ist das besser als x >> 4 ? Wozu muss man danach noch maskieren? Sollten in den ersten 4 Bits nicht ohnehin Nullen drin stehen?



  • c/0xF ist doch ein "trickreicher" Rechtsshift oder?

    Nein.
    http://ideone.com/YuHfoS
    Also ich sehe nicht das selbe Bitmuster nur ein wenig weiter rechts....



  • TNA schrieb:

    Ich habe noch eine Frage zum Ausdruck

    (c/0xF)&0xF
    

    c/0xF ist doch ein "trickreicher" Rechtsshift oder? Warum ist das besser als x >> 4 ? Wozu muss man danach noch maskieren? Sollten in den ersten 4 Bits nicht ohnehin Nullen drin stehen?

    15 ist einfach die falsche Zahl. Es müsste 16 heißen, damit die Division einen Rechts-Shift um 4 bewirkt.
    Das Maskieren ist in der Tat überflüssig, wenn ein char genau 8 Bits hat oder die Werte unter 256 liegen.



  • TyRoXx schrieb:

    15 ist einfach die falsche Zahl. Es müsste 16 heißen, damit die Division einen Rechts-Shift um 4 bewirkt.

    Hätte mir auch auffallen sollen, dass das keine Zweierpotenz ist. Genau darum würde ich x >> 4 bevorzugen, weil man da sofort sieht was gemeint ist und der Compiler wahrscheinlich ohnehin den schnellstmöglichen Code generiert.


Anmelden zum Antworten